반응형
문제
1 ~ n 의 숫자 중에서 k 개를 골라 만들 수 있는 모든 "조합" 을 출력한다.
조합은 순서없이 어떤 것을 골랐는가 만 따진다.
문제풀이
백트래킹이란?
예전에 정리한 바로는 해가 될 수 없는 경로는 즉시 포기하는 것이다. 좀 더 설명을 덧붙이자면, 선택 > 탐색 > 취소 세 단계의 패턴으로 구성된다.
def combinations(n: int, k: int) -> list:
result = [] # 완성된 조합을 모아 둘 곳
def backtrack(start: int, current_combination: list) -> None:
if len(current_combination) == k:
result.append(list(current_combination))
return
for num in range(start,n + 1): # range 가 (start, end) 일떄 end -1 까지 돈다.
current_combination.append(num)
backtrack(num + 1, current_combination)
current_combination.pop()
# 처음 호출: 시작 숫자는 1, 지금까지 고른 숫자는 비어 있음
backtrack(1, [])
return result
이 문제는 힌트가 정답의 거의 전부를 제공하고 있어서 너무 아쉬웠다. 나중에 힌트 없이 다시 풀어볼 예정이다. 힌트를 토대로 풀었고, 난 이해를 못했는데 정답을 맞추게 되었다.
디버깅 툴을 돌려가며 이해한 바로는
backtrack(1, []) 호출
ㄴ num=1: append(1) → [1]
ㄴ backtrack(2, [1]) 호출됨
ㄴ num=2: append(2) → [1,2]
ㄴ backtrack(3, [1,2]) 호출 → len ==2, result에 [1,2] 추가, return
ㄴ pop() 실행 → [1,2] → [1]
ㄴ num=3: append(3) → [1,3]
ㄴ backtrack(4, [1,3]) 호출 → len ==2, reulst에 [1,3] 추가, return
ㄴ pop() 실행 → [1,3] → [1]
ㄴ for 문 종료 (range(2,4) 완료)
ㄴ return
ㄴ pop() 실행 → [1] → []
다음 for 문 호출 ...for 문 안에서 append > 재귀호출 > pop 이 반복된다.
이때 포인트는, 중복을 방지하기 위해 두번째 들어가는 값은 이전 값보다 무조건 커야한다는거다.
타입 힌트
코드들에서 이상한 점을 느끼진 않았는지? 일반적인 함수와 다르게, `def combinations(n: int, k: int) -> list:` 이런식으로 표기되어 있다. 이런걸 타입 힌트라고 한다.
n: int : 매개변수 n 은 int 타입일 거라고 힌트를 주는 것이다.
-> list : 이 함수가 반환하는 값은 list 타입일 거라고 힌트를 주는 것이다.
이 항목들은 강제가 아니라 실제 런타임에 체크하지 않는다. 함수의 주석이라고 생각하면 된다. 자바에서는 int n, int k 이런식으로 쓰면 컴파일러가 강제로 체크했는데 파이썬은 다르니 유의할 것 !
어려웠던 점
- 재귀 호출이 들어가고 나가는 부분이 너무 헷갈린다. 특히 재귀안의 재귀들이 도는건 이해가 가는데, 가장 외부 재귀에서 빠져나오는 부분이 헷갈린다.
- 힌트가 없었으면 풀 수 있었을까? 싶은 생각이 들었다. 다음에 한번 더 풀어볼 것.
반응형
