재귀
완전탐색
- twosum 반복문으로 풀기
def twosum(nums, target):
def recur(arr, start):
if len(arr) == 2:
if nums[arr[0]]+nums[arr[1]] == target:
return True
return False
for i in range(start, len(nums)):
arr.append(i)
if recur(arr, i+1):
return arr
arr.pop()
return recur([], 0)
twosum(nums=[2,7,11,15], target = 9)
- 조합
- 순서 중요x
4: [1,2],[1,3],[1,4][2,3],[2,4],[3,4]
def solution(n, k):
answer = []
if len(arr) == k :
answer.append(arr[:])
return
def combination(arr, start):
for i in range(start, n+1):
arr.append(i)
combination(arr, i+1)
arr.pop()
return combination([], 1)
solution(n=4, k=2)
- 순열
- 순서 중요o
3까지의 경우: [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
def permutation(arr):
if len(arr) == k:
answer.append(arr[:])
return
for i in range(1, n):
if i not in arr:
arr.append(i)
permutation(arr)
arr.pop()
answer = []
n = 4
k = 2
permutation(arr=[])
print(answer)
BFS, DFS
- BFS
from collections import deque
def bfs(graph, start_v):
q = deque()
visited = [False]*len(graph)
q.append(start_v)
visited[start_v] = True
while q:
print(q)
cur_v = q.popleft()
print(cur_v)
for next_v in graph[cur_v]:
if not visited[next_v]:
q.append(next_v)
visited[next_v] = True
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
bfs(graph, start_v=0)
- DFS
- 깊이 탐색: 0,1,3,2,7,5,4,6
위에 그래프 참고
def dfs(start_v):
visited[start_v] = True
print(start_v)
for cur_v in graph[start_v]:
if not visited[cur_v]:
dfs(cur_v)
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
visited = [False for _ in range (len(graph))]
dfs(start_v=0)
- 예제
- bfs,dfs를 통해 모든 노드를 방문했으면 True를 반환
https://leetcode.com/problems/keys-and-rooms/description/
class Solution(object):
def canVisitAllRooms(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: bool
"""
visited = [False for _ in range(len(rooms))]
def dfs(start):
visited[start] = True
for cur_v in rooms[start]:
if not visited[cur_v]:
dfs(cur_v)
dfs(0)
return all(visited)
## bfs
from collections import deque
class Solution(object):
def canVisitAllRooms(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: bool
"""
visited = [False for _ in range(len(rooms))]
def bfs(start):
queue = deque()
queue.append(start)
visited[start] = True
while queue :
s = queue.popleft()
for cur_v in rooms[s]:
if not visited[cur_v] :
visited[cur_v] = True
queue.append(cur_v)
bfs(0)
return all(visited)- 암시적 그래프 bfs,dfs
- 모든 지점에서 방문을 안 했고 '1'이라면 bfs,dfs를 돌면서 섬의 총 개수를 파악한다.
- 상하좌우를 돌면서 grid를 넘지 않고, '1'이면서, visitied가 False라면 수행을 한다.
https://leetcode.com/problems/number-of-islands/description/
# dfs
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(r, c):
visited[r][c] = True
for i in range(4):
next_dr = r + dr[i]
next_dc = c + dc[i]
if 0<= next_dr <len(grid) and 0<=next_dc<len(grid[0]) and grid[next_dr][next_dc] == '1' :
if not visited[next_dr][next_dc]:
dfs(next_dr, next_dc)
cnt = 0
visited = [[False]*len(grid[0]) for _ in range(len(grid))]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
for i in range(len(grid)):
for j in range(len(grid[0])):
if not visited[i][j] and grid[i][j] == '1':
dfs(i, j)
cnt +=1
return cnt
# bfs
from collections import deque
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def bfs(r, c):
q= deque()
q.append([r, c])
visited[r][c] = True
while q:
r, c = q.popleft()
for i in range(4):
next_dr = r + dr[i]
next_dc = c + dc[i]
if 0 <= next_dr < len(grid) and 0 <= next_dc < len(grid[0]) and grid[next_dr][next_dc] == '1':
if not visited[next_dr][next_dc]:
q.append([next_dr, next_dc])
visited[next_dr][next_dc] = True
cnt = 0
visited = [[False]*len(grid[0]) for _ in range(len(grid))]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
for i in range(len(grid)):
for j in range(len(grid[0])):
if not visited[i][j] and grid[i][j] == '1':
bfs(i, j)
cnt +=1
return cnt
