bright

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(x,y):
            if x < 0 or y < 0 or x>= len(grid) or y>= len(grid[0]) : 
                return False 
            
            if grid[x][y] == "1" :
                grid[x][y] = 0 
                
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y+1)
                dfs(x,y-1)
                
                return True
            return False 
        
        cnt = 0 
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if dfs(x,y) == True:
                    cnt += 1 
        return cnt

음료수 얼려 먹기 문제와 거의 유사한 dfs 문제이다. 

입력 받는 방식이 조금 특이하다. 

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

leetcode.com/problems/number-of-islands/

from collections import deque

n, m = map(int,input().split())
graph = []
for i in range(n) :
  graph.append(list(map(int,input())))

# 상 하 좌 우  x 가 세로 y 가 가로 
dx = [ -1, 1 , 0 , 0 ]
dy = [  0, 0, -1,  1 ] 

def bfs( x, y ) : 
  queue = deque()
  queue.append((x,y))

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or ny < 0 or nx >= n or ny >= m : 
        continue 
      
      if graph[nx][ny] == 0 : 
        continue 
      
      if graph[nx][ny] == 1 : 
        graph[nx][ny] = graph[x][y] +1 
        queue.append((nx,ny))
  
  return graph[n-1][m-1]

print( bfs(0,0) )

1. 해결 : 그래프의 최단거리를 찾는 문제는 보통 bfs 를 사용해서 푼다. 

2. point : 

- bfs 를 사용할 것이므로 큐를 이용해서 구현한다. 효율성을 위해 deque 를 선언하고 사용했다. 

- 차례대로 큐에 집어 넣고 그 와 가까운 노드들을 방문하여 처리한다는 느낌으로 이해한다. 

www.acmicpc.net/problem/2178

1. 표준 라이브러리 

특정한 프로그래밍 언어에서 자주 사용되는 표준 소스 코드를 미리 구현해 놓은 라이브러리 

docs.python.org/ko/3/library/index.html

2. 내장함수 

- sum()

- print()

- min()

- max()

- eval()  : 수식이 문자열 형식으로 들어오면 계산해서 결과를 반환 

- sorted() 

3. itertools 

- permutations() :  순열 계산 ( 순서 신경 o ) 

- combinations() :  조합 계산 ( 순서 신경 x ) 

4. heapq 

python 에서 heap 기능을 위해 사용한다. 다익스트라 최단 경로 알고리즘 등에서 우선순위 큐를 구현하고자 할 때 사용된다. 파이썬에서는 힙을 최소 힙으로만 구성함을 기억한다. ( 최대 힙으로 만들고 싶으면 파라미터에 - 를 붙여 활용 ) 

- heapq.heappush() : 힙에 원소 삽입 

- heapq.heappop()  : 힙에서 원소 꺼냄 

5. bisect 

이진탐색을 쉽게 구현할 수 있도록 제공되는 라이브러리로, 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. 

- bisect_left (a, x )  :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 왼쪽 인덱스를 찾아줌. 

- bisect_right(a, x ) :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 오른쪽 인덱스를 찾아줌.

6. collections 

유용한 자료구조를 제공하는 표준 라이브러리

- deque   :  큐를 구현하는데 사용함. popleft, pop, appendleft, append 로 원소 배치. 

- Counter :  등장 횟수를 세는 기능을 제공. 리스트 같은 iterable 객체에서 원소가 몇 번 등장했는지 알려줌. 

7. math

자주 사용되는 수학적인 기능을 포함하는 라이브러리

- factorial()

- sqrt()   : 제곱근 

- gcd()   : 최대 공약수 

- pi 

- e 

1. 개념 

식별자 없이 실행 가능한 일회성 함수. 

def 의 함수 선언 없이도 하나의 식으로 함수를 단순하게 표현할 수 있음. 

2. 사용 예시 

1) 리스트 정렬 시, key 값으로 전달 // 정렬의 우선 순위를 부여하는 경우에 사용하면 매우 편리 

s = [ ( 'A', 1 ) , ( 'Z', 2 ) , ( 'N', 9 ) , ( 'B', 3 ), ( 'H', 3 ) ] 을  숫자 기준 내림차순 , 문자 기준 오름차순으로 정렬하시오. 

s.sort( key = lambda x: ( -x[1], x[0] ) ) 

결과 : [('N', 9), ('B', 3), ('H', 3), ('Z', 2), ('A', 1)]

문자 순으로 정렬하되, 문자가 동일한 경우에는 식별자 순으로 나열하라. 

logs = ["let1 art ","let2 own","let3 art", "let4 cat", "let5 book"]

logs.sort( key = lambda x: ( x.split()[1:] , x.split()[0] ) ) 

결과 : ['let1 art ', 'let3 art', 'let5 book', 'let4 cat', 'let2 own']

3. 주의 사항 

map, filter 등과 함께 사용하면 가독성이 매우 떨어질 수 있으므로 주의해서 사용한다. 

또한, 꼭 필요한 경우가 아닐 때는 람다 표현식 보다는 리스트 컴프리핸션이 더 많이 사용된다. 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 
        
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]
                
        return result 

쌀 때 사서 비쌀 때 팔아 가장 높은 수익을 얻는 문제.

그리디 알고리즘을 사용하여 풀면 간단하다. 

만약, 현재보다 다음 값이 오른다면 사고 판다. 

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/