벨로그에서 글을 쓸 때는 꼭 어딘가에 백업을 하는 습관을 들이도록 하자.....
업로드 되었다면서 다시 새로고침하니까 게시글이 게눈 감추듯 사라진 경우가 두 번이나 있었다....흑 슬퍼
출처 : 파이썬 알고리즘 인터뷰
어제 푼 문제와 오늘 푼 문제들에 대해 소개해보겠다.
(가뜩이나 잘 풀지도 못하는데 하루에 두 문제 이상 풀면 자신감 더 하락할 것 같아서 하루에 하나라도 제대로 풀기로 함..)
어제와 오늘 푼 문제는 조합을 어떻게 dfs로 다루는지를 알 수 있는 문제였다.
어제 푼 문제
leetcode 77. Combinations
1부터 n까지의 숫자 중 k개 조합의 구성을 나열하는 간단한 문제였다.
풀던 방식대로 생각의 흐름부터..
생각의 흐름
-
1부터 n까지의 수
-> list로 만들어야되나
=> 결과적으로 그럴 필요 없었다. 어차피 순회를 하면서 dfs를 진행하기 때문에 겸사겸사 숫자를 append하는 개념이 시간을 줄일 수 있다. -
그림을 어떻게 그려야 잘 이해할 수 있을까
위와 같이 그려보니 이해가 됐다...
dfs를 풀이할 때마다 어떻게 그리면서 이해하고 로직을 구성해야되는지가 늘 어려웠는데 어제 딱 알았음......이런 날도 오는구나..쾌감 미쳣공(다음문제에 굉장한 도움이 되셨다네요.) -
k개를 뽑아서 조합?
=> k 숫자를 줄여가는 방식으로 접근해보기 -
조합
=> 자기 자신을 제외한 elements를 매개변수로 계속 전달해서 내려주자.
접근 1
중복을 포함하지 않는 조합의 경우, 답 후보에 1이 들어가 있으면 1이 추가로 들어갈 수 없다. => 그 다음부터 탐색하도록 index를 변수로 넘겨주면 됨
for i in range(start, n+1):
elements.append(i)
dfs(elements, i+1, k-1) #elements에 숫자 append했으니까 바로 k수 깎기
elements.pop()여기에서 왜 elements.pop()을 dfs 종료 후 해줘야 할까?
예를 들어, 1을 담고 나서
2 탐색
3 탐색
4 탐색
을 순차적으로 돌아야 한다고 하면, 1은 그대로 있는데, 2/3/4를 갈아끼워줘야되는 것이다...! 그 역할을 해주는게 pop()메서드이다. pop()을 안해주면 [1,2]가 result에 append되고 난 후에 [1,3]이 적합할지 판단해야 하는 함수에 그 전 탐색에 이용되었던 elements [1,2]가 따라들어가게 된다.
접근 2
언제 종료하나요
k의 개수를 다 채웠을 때(k==0)
어제 푼 문제 최종코드
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(elements, start, k):
if k==0:
result.append(elements[:])
return
for i in range(start, n+1):
elements.append(i)
dfs(elements, i+1, k-1)
elements.pop()
result = []
dfs([],1,k)
return result
solution = Solution()
solution.combine(4,2)오늘 푼 문제
candidates의 요소들을 (중복허용)조합하여 target 값을 만드는 문제이다.
이 문제가 기념비적인 이유는 내 힘으로 제대로 푼 첫 dfs문제임...
이렇게 힘을 얻습니다...
생각의 흐름
중복 허용 X 였던 어제 문제의 핵심은 "자기 자신을 제외한 리스트를 넘겨주어야 한다는 것이었다.
그렇다면, 중복을 허용하는 해당 문제에선 자기 자신을 포함한 리스트를 계속 넘겨주면 된다.
딱 깔쌈하게 그림으로 그려보면 
요렇게 그릴 수 있다. 그림으로 그려서 이해하는게 편하다는걸 오늘이 되어서야 피부로 깨달았달까요 ㅎㅅㅎ
풀어봅시다.
- target 값을 빼주는 방식으로 종료 조건에 접근
- 정렬되어있지 않은 리스트이므로, 정렬을 하고 시작하면 편함
- 정렬이 되어있다는 가정 하에, 앞부터 탐색.
-> 탐색을 시작하면 되는 index를 넘겨준다.
접근 1
dfs 내에서 매개변수로 받은 index와 후보군 개수의 수까지 도는 for문을 구성한다.
for i in range(index, len(candidates)):
if t-candidates[i] >= 0:
t -= candidates[i]
elements.append(candidates[i])
dfs(i, t, elements)
t += elements.pop()elements를 더해주고, 다음 dfs로 넘기면서 현재의 target값 t도 함께 넘겨주는 방식을 (위 사진에는 안나와있지만) 추가했다.
책에 나와있는 방식보다는 살짝 더럽다.ㅎㅎ.그래도 푼게 어디..
접근 2
언제 종료하나요
현재의 t 값이 0이면 result에 추가하는 결말을 주고, t가 음수가 되거나 index가 범위를 넘었거나 candidates가 비어있는 경우에 종료하는 결말을 주면 된다.
오늘 푼 문제 최종코드
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort()
def dfs(index, t, elements):
if t == 0:
result.append(elements[:])
return
if index < 0 or index > len(candidates) or t < 0 or not candidates or t-candidates[index] < 0: return
for i in range(index, len(candidates)):
if t-candidates[i] >= 0:
t -= candidates[i]
elements.append(candidates[i])
dfs(i, t, elements)
t += elements.pop()
else: return
dfs(0, target, [])
return result