재귀함수를 빠르게, 쉽게 작성하려면 어떻게 해야 할까??
문제마다 재귀함수로 접근을 하려고 하면 항상 머릿 속이 하얘지고 머리가 아파오기 때문에 많은 분석을 통하여 나름의 작성 법칙을 만들어 보기로 했다.
여러 dfs 문제 코드를 보면서 그 속에서 공통점을 찾아보자.
재귀를 작성할 때 헷갈리는 것들
- while을 쓸지 if를 쓸지
- while을 쓸지 for를 쓸지
- return을 쓸지, return으로 무엇을 넘겨줄지
- 재귀함수로 무슨 인자를 넘겨줄 것인가
- 백트래킹을 어떻게 할것인가? 즉 말단 노드에서 어떻게 처리할 것인가
연구(계속 업데이트 중)
- 재귀함수에서 while을 쓰면 엄청 복잡해짐
- 재귀함수는 보통 while 보다는 for/if 안에 들어있음 / 아님 아예 밖에 있거나
- 백트래킹 구조(return값이 필요없을 때)
def dfs():
if 백트래킹 체크: ## 길이비교 or 값 존재 여부 탐색
지정코드 수행
return
for/if:
dfs()- 백트래킹 구조(return값이 있을 때)
def dfs():
if 백트래킹 체크: ## 길이비교 or 값 존재 여부 탐색
지정코드 수행
return null 또는 문제에 따라 적절한 값을 넘겨줘야함
for/if:
a = dfs()
b = dfs()
reutrn a, b의 자료형에 맞춰줘야함
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
- 그래프에서 재귀 구조 코드
이 코드의 특징: 모든 정점을 한번씩 도달하는 해밀턴 경로
graph =
{
1:[2,3,4],
2:[5],
3:[5],
4:[],
5:[6,7],
6:[],
7:[3],
}
def recursive_dfs(v, discovered=[]):
discovered.append(v)
for w in graph[v]:
if not w in discovered:
discovered = recursive_dfs(w, discovered)
return discovered
>> print(recursive_dfs(1))
[1,2,5,6,7,3,4]- 38. 일정 재구성 : leetcode.com/problems/reconstruct-itinerary
이 코드의 특징: 모든 간선을 한번씩 도달하는 오일러 경로
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
table = collections.defaultdict(list)
for dep, arr in tickets:
table[dep].append(arr)
for key in table:
table[key].sort(reverse=True)
route = []
def dfs(dep):
while table[dep]:
next = table[dep].pop()
dfs(next)
route.append(dep)
dfs('JFK')
return route[::-1]
32. 섬의 개수: leetcode.com/problems/number-of-islands/
<나의 풀이>
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row = len(grid[0])
col = len(grid)
def dfs(y,x):
if (0<=x<row) and (0<=y<col) and (grid[y][x] =='1'):
grid[y][x]='0'
dfs(y+1,x)
dfs(y-1,x)
dfs(y,x+1)
dfs(y,x-1)
count = 0
for i in range(col):
for j in range(row):
if grid[i][j]=='1':
dfs(i,j)
count+=1
return count
33. 전화번호 문자열 조합 : leetcode.com/problems/letter-combinations-of-a-phone-number/
<나의 풀이>
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return ''
table={
'2':'abc','3':'def','4':'ghi','5':'jkl',
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz',
}
result=[]
def dfs(word, idx):
## back-tracking
if idx == len(digits):
result.append(word)
return
## recursive
for char in table[digits[idx]]:
dfs(word+char, idx+1)
dfs('',0)
return result
34. 순열 : leetcode.com/problems/permutations/
<나의풀이>
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def dfs(lst=[]):
if len(lst)==len(nums):
result.append(lst)
return
for num in nums:
if not num in lst:
dfs(lst+[num])
dfs()
return result
36. 중복조합 : leetcode.com/problems/combination-sum
<나의풀이>
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
def dfs(sum, path, lst):
if sum > target:
return
if sum == target:
result.append((path))
return
for num in lst:
dfs(sum+num, path+[num], lst[lst.index(num):])
dfs(0,[], candidates)
return result
37. 부분집합: leetcode.com/problems/subsets/
<나의풀이>
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def dfs(path, lst):
result.append(path)
if not lst:
return
for num in lst:
dfs(path+[num], lst[lst.index(num)+1:])
dfs([],nums)
return result
댓글