문제에서 요구하는 것
자연수 1..N 중에서 중복 없이 M개를 고른 수열을 모두 출력한다.
추가 조건:
- 수열은 오름차순
- 전체 출력 순서도 사전 순(lexicographic) 증가
즉, 사실상 조합(combination) 을 사전순으로 출력하는 문제다.
내가 막혔던 포인트 정리
1) for문으로 하면 중첩 개수가 M에 따라 달라짐
맞다. M=2면 2중 for, M=3이면 3중 for… 이런 식이라서 고정된 for문 중첩으로는 일반화가 어렵다.
2) 재귀로 하려니 “수열을 어떻게 생성해야 하는지” 감이 안 옴
이 문제는 전형적인 백트래킹(Backtracking) 패턴을 쓰면 된다.
핵심 아이디어는:
- 현재까지 고른 수열
path가 있고 - 다음에 고를 수 있는 후보의 시작점을
start로 관리한다 start부터N까지 하나씩 선택하며 재귀로 들어간다- 길이가
M이 되면 출력한다
start를 다음 단계에서 i+1로 넘기면 자동으로 오름차순 + 중복 방지가 된다.
정답 코드 (백트래킹)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
path = []
out = []
def dfs(start: int):
if len(path) == m:
out.append(' '.join(map(str, path)))
return
for x in range(start, n + 1):
path.append(x)
dfs(x + 1) # 다음은 x보다 큰 수만 선택 -> 오름차순 유지
path.pop()
dfs(1)
sys.stdout.write('\n'.join(out))
이 코드에서 배울 수 있는 점
1) “가변 길이 중첩 반복”은 재귀로 일반화한다
M이 바뀌어도 재귀 깊이만 바뀌기 때문에, 중첩 for문을 직접 늘릴 필요가 없다.
2) 오름차순 조건은 start 하나로 해결된다
- 현재 단계에서
x를 선택했다면 - 다음 단계는
dfs(x+1)로 들어가면 된다
→ 그러면 다음에 고르는 값이 항상 더 커져서 오름차순이 보장된다.
3) 중복 제거를 visited 없이도 할 수 있다
오름차순을 강제하면 같은 원소를 다시 고를 일이 없어서 visited 배열이 필요 없다.
4) 백트래킹의 기본 형태
- 선택:
path.append(x) - 탐색:
dfs(...) - 되돌리기:
path.pop()
이 3줄이 백트래킹의 “뼈대”다.
참고: 출력이 많은 문제에서의 출력 최적화
print()를 매번 호출해도 이 문제는 충분히 통과하는 편이지만, 습관적으로 out에 모아 \n.join(…) 후 한 번에 출력하면 더 안정적이다.