📌 문제 요약

• 문제 이름: 15650번: N과 M (2)
• 알고리즘 분류: 백트래킹 (Backtracking)
• 사용 언어: Python 3

자연수 $N$과 $M$이 주어졌을 때, 1부터 $N$까지 자연수 중에서 중복 없이 $M$개를 고른 수열을 모두 구하는 문제입니다. 단, 고른 수열은 오름차순이어야 합니다. (즉, 순서만 다르고 구성이 같은 수열은 취급하지 않는 조합 문제입니다.)

---

💡 문제 접근 방법 (핵심 로직)

이 문제는 백트래킹의 가장 기본이 되는 교과서적인 문제입니다. '순열(Permutation)'이 아닌 '조합(Combination)'을 구해야 하므로, 탐색을 할 때 "이전에 고른 숫자보다 무조건 큰 숫자만" 탐색 후보로 두어야 합니다.

1. DFS 탐색: 재귀 함수를 이용해 깊이 우선 탐색(DFS)을 진행합니다.
2. 가지치기 (Pruning) - start_n의 역할: 재귀 함수인 dfs()에 start_n이라는 매개변수를 전달합니다. 반복문을 for i in range(start_n, N + 1)로 설정하면, 자연스럽게 현재 숫자 이후의 값들만 탐색하게 되어 오름차순 조건이 지켜집니다.
3. 백트래킹 (상태 복구): result.append(i)로 숫자를 스택에 넣고 재귀를 호출한 뒤, 탐색이 끝나고 돌아오면 result.pop()을 통해 방금 넣었던 숫자를 빼줍니다. 이 과정이 있어야 부모 노드로 돌아가 다른 가지를 탐색할 수 있습니다.
4. 종료 조건: result 배열의 길이가 $M$과 같아지면 조건에 맞는 수열을 완성한 것이므로 출력하고 함수를 종료(return)합니다.

---

💻 코드 구현

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

result = []

def dfs(start_n):
    # 원하는 길이 M에 도달하면 출력
    if len(result) == M:
        print(*result)
        return
    
    # start_n부터 시작하여 오름차순을 유지 (중복 방문 방지)
    for i in range(start_n, N + 1):
        result.append(i)
        dfs(i + 1)
        result.pop() # 다음 조합을 찾기 위해 상태 복구

dfs(1)

---

🚨 트러블 슈팅 및 회고
순열과 조합의 차이 구현: 만약 start_n 없이 항상 for i in range(1, N + 1)로 탐색했다면 (1, 2)와 (2, 1)이 모두 나오는 순열이 되었을 것입니다. 함수 인자를 통해 탐색의 시작점을 제어하는 것만으로 오름차순 조합을 만들어낼 수 있다는 백트래킹의 핵심을 확실히 짚고 넘어갈 수 있었습니다.

파이썬 언패킹 연산자(): 리스트에 담긴 요소를 공백으로 구분해서 출력할 때 for문을 돌리거나 ' '.join(map(str, result))를 쓰지 않고, print(result) 한 줄로 아주 깔끔하게 처리할 수 있는 파이썬의 문법적 장점을 적극 활용했습니다.

라이브러리 vs 직접 구현: 실전 코딩 테스트에서는 itertools.combinations를 쓰면 한 줄로 풀리겠지만, DFS의 구조를 이해하기 위해 직접 바닥부터 상태 공간 트리를 탐색해 본 의미 있는 문제였습니다.

💡 [추가 풀이] 파이썬다운 궁극의 1줄 숏코딩: itertools와 제너레이터 활용

회고에서 언급했듯, 실전 코딩 테스트에서 시간이 부족하거나 로직을 빠르게 구현해야 할 때는 파이썬의 강력한 표준 라이브러리인 itertools.combinations를 사용하는 것이 압도적으로 효율적입니다.

DFS로 직접 짰던 코드를 파이썬의 고급 문법(제너레이터 표현식, map, join)을 활용해 단 한 줄의 출력문으로 압축한 최적화 풀이입니다.

💻 코드 구현

import sys
from itertools import combinations

input = sys.stdin.readline
N, M = map(int, input().split())

# 조합 생성부터 문자열 변환, 줄바꿈 결합, 출력까지 단 한 줄로 처리
print('\n'.join(' '.join(map(str, comb)) for comb in combinations(range(1, N + 1), M)))

🔍 1줄 코드 해부하기 (동작 원리)

안쪽에서 바깥쪽으로 코드가 어떻게 변환되는지 해석하면 다음과 같습니다.

1. combinations(range(1, N + 1), M): 1부터 N까지의 숫자 중 M개를 뽑는 조합을 순서대로 생성합니다. (예: (1, 2))
2. map(str, comb): 튜플 안에 들어있는 정수들을 join으로 합치기 위해 문자열로 일괄 변환합니다. (예: ('1', '2'))
3. ' '.join(...): 문자열로 변환된 숫자들을 공백을 두고 하나로 합칩니다. (예: "1 2")
4. '\n'.join(... for comb in ...): 리스트 괄호 [] 없이 괄호 () 안에서 for 문을 돌려 제너레이터 표현식(Generator Expression)을 만듭니다. 메모리에 한 번에 올리지 않고, 만들어진 "1 2" 같은 문자열들을 그때그때 뽑아내어 사이사이에 엔터(\n)를 발라 거대한 하나의 문자열로 결합합니다.
5. print(...): print() 함수를 여러 번 호출할 필요 없이, 완성된 거대한 문자열을 단 1번만 출력하여 입출력(I/O) 성능을 극대화합니다.

• print() 함수와 제너레이터(Generator)의 동작 방식 차이 깨닫기: 숏코딩을 시도하는 과정에서 print(' '.join(map(str, comb)) for comb in combinations(...))와 같이 작성했다가, 정답 대신 <generator object <genexpr> at ...> 이라는 메모리 주소가 출력되는 현상을 겪었습니다.
  이를 통해 파이썬의 중요한 동작 원리를 깨달았습니다. 대괄호 []가 아닌 소괄호 ()로 묶인 제너레이터 표현식은 메모리를 아끼기 위해 당장 값을 계산하지 않는 '게으른 연산(Lazy Evaluation)'을 수행합니다.
  print() 함수는 넘어온 객체를 억지로 실행시키지 않고 있는 그대로 보여주기 때문에 기계(제너레이터 객체) 자체를 출력했던 것입니다. 반면 .join() 메서드는 이 제너레이터를 끝까지 작동시켜 알맹이를 모두 뽑아낸 뒤 하나의 문자열로 결합해 준다는 점을 명확히 이해하게 되었습니다. 결과적으로 겉보기엔 비슷한 1줄 코드라도, 내부적으로 메모리를 어떻게 다루고 소비하는지(I/O 최적화) 깊이 고민해 볼 수 있는 값진 경험이었습니다.