Note
백트래킹(Backtracking)을 활용하여 N개의 자연수에서 M개를 선택하는 모든 수열을 생성하는 문제입니다.
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
문제 링크: https://www.acmicpc.net/problem/15654
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제
예제 입력 1:
3 1
4 5 2
예제 출력 1:
2
4
5
예제 입력 2:
4 2
9 8 7 1
예제 출력 2:
1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8
문제 분석
이 문제는 백트래킹을 사용하는 전형적인 문제입니다.
핵심 포인트
- 순열 생성: N개에서 M개를 선택하는 순열 (순서 중요)
- 중복 방지: 같은 수를 여러 번 사용할 수 없음
- 사전순 출력: 입력 배열을 정렬해야 함
해결 방법
백트래킹 알고리즘을 사용합니다:
- 입력 배열을 정렬 (사전순 출력을 위해)
- 백트래킹으로 수열 생성:
- 현재 수열의 길이가 M이면 출력
- 아직 사용하지 않은 수를 선택
- 재귀 호출
- 선택 취소 (되돌리기)
코드 구현
제공된 코드
import sys
readline = sys.stdin.readline
n, m = map(int, readline().split())
arr = list(map(int, readline().split()))
arr.sort()
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(n):
if not arr[i] in s:
s.append(arr[i])
dfs()
s.pop()
dfs()코드 분석
1. 입력 처리
import sys
readline = sys.stdin.readline
n, m = map(int, readline().split())
arr = list(map(int, readline().split()))
arr.sort()- 입력 최적화를 위해
sys.stdin.readline()사용 - 입력 배열을 정렬하여 사전순 출력 보장
2. 백트래킹 함수
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(n):
if not arr[i] in s:
s.append(arr[i])
dfs()
s.pop()동작 과정:
- 기저 조건: 수열의 길이가 M이면 출력하고 반환
- 선택: 아직 사용하지 않은 수를 선택
- 재귀: 선택한 수를 추가하고 재귀 호출
- 되돌리기:
s.pop()으로 선택 취소
개선된 코드
더 효율적이고 명확하게 작성한다면:
import sys
readline = sys.stdin.readline
def backtrack(arr, m, current=[], used=None):
if used is None:
used = [False] * len(arr)
# 기저 조건: M개를 모두 선택
if len(current) == m:
print(' '.join(map(str, current)))
return
# 가능한 선택들
for i in range(len(arr)):
if not used[i]: # 아직 사용하지 않은 수
# 선택 적용
current.append(arr[i])
used[i] = True
# 재귀 호출
backtrack(arr, m, current, used)
# 선택 취소 (되돌리기)
current.pop()
used[i] = False
n, m = map(int, readline().split())
arr = list(map(int, readline().split()))
arr.sort()
backtrack(arr, m)개선 사항:
arr[i] in s대신used배열 사용 (O(1) vs O(n))- 함수에 파라미터 전달 (전역 변수 사용 최소화)
- 변수명을 더 명확하게 (
s→current)
시간 및 공간 복잡도
시간 복잡도
- 순열 개수: N개에서 M개를 선택하는 순열 = N! / (N-M)!
- 각 순열 생성: O(M)
- 전체: O(M × N! / (N-M)!)
공간 복잡도
- 현재 수열: O(M)
- 사용 여부 배열: O(N)
- 재귀 스택: O(M)
- 전체: O(N + M)
예제 동작 과정
예제 입력 1: n=3, m=1, arr=[4, 5, 2] (정렬 후: [2, 4, 5])
백트래킹 과정:
dfs():s=[]i=0:arr[0]=2선택 →s=[2]→dfs()호출len(s)=1 == m→ 출력:2
i=1:arr[1]=4선택 →s=[4]→dfs()호출len(s)=1 == m→ 출력:4
i=2:arr[2]=5선택 →s=[5]→dfs()호출len(s)=1 == m→ 출력:5
결과: 2, 4, 5
예제 입력 2: n=4, m=2, arr=[9, 8, 7, 1] (정렬 후: [1, 7, 8, 9])
백트래킹 과정 (일부):
dfs():s=[]i=0:arr[0]=1선택 →s=[1]→dfs()호출i=1:arr[1]=7선택 →s=[1,7]→ 출력:1 7i=2:arr[2]=8선택 →s=[1,8]→ 출력:1 8i=3:arr[3]=9선택 →s=[1,9]→ 출력:1 9
i=1:arr[1]=7선택 →s=[7]→dfs()호출i=0:arr[0]=1선택 →s=[7,1]→ 출력:7 1i=2:arr[2]=8선택 →s=[7,8]→ 출력:7 8i=3:arr[3]=9선택 →s=[7,9]→ 출력:7 9
- … (나머지도 동일한 패턴)
주의사항
1. 상태 되돌리기
백트래킹에서 가장 중요한 것은 선택을 취소하는 것입니다:
s.append(arr[i]) # 선택
dfs() # 재귀
s.pop() # 취소 (필수!)s.pop()을 하지 않으면 이전 선택이 남아있어 잘못된 결과가 나옵니다.
2. 중복 체크 방법
비효율적 (제공된 코드):
if not arr[i] in s: # O(n) 시간효율적 (개선된 코드):
if not used[i]: # O(1) 시간3. 정렬
사전순으로 출력하려면 입력 배열을 먼저 정렬해야 합니다:
arr.sort() # 필수!4. 전역 변수 vs 파라미터
전역 변수를 사용하면 간단하지만, 함수 파라미터를 사용하면 더 명확합니다.