[백준 / 파이썬] 백준 15649번 문제 풀이: N과 M (1)

문제

---

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

입력

---

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

---

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

문제 해결

---

 

전체 코드

import sys

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

def permutation(N,M,sequence,visited):
    
    if len(sequence)==M:
        print(*sequence)
        
    for i in range(N):
        if visited[i]==False:
            sequence.append(i+1)
            visited[i]=True
            permutation(N,M,sequence,visited)
            sequence.pop()
            visited[i]=False

visited=[False]*(N)
sequence=[]

permutation(N,M,sequence,visited)

 

이 코드는 N과 M을 입력받고, 1부터 N까지의 숫자 중 M개를 선택하여 만들 수 있는 모든 순열을 출력하는 백트래킹(Backtracking) 알고리즘이다.

 

코드 해설

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

 

• sys.stdin.readline()을 사용하여 한 줄의 입력을 받는다.
• 입력값을 공백 기준으로 나눈 뒤, int형으로 변환하여 N과 M에 저장한다.
• N: 사용할 숫자의 개수 (1부터 N까지)
• M: 순열에서 선택할 개수

-순열을 만드는 재귀 함수 (permutation)

def permutation(N, M, sequence, visited):

 

 

• N: 사용할 숫자의 개수 (1부터 N까지)
• M: 뽑아야 할 숫자의 개수
• sequence: 현재까지 선택한 숫자 리스트
• visited: 해당 숫자를 사용했는지 여부를 나타내는 리스트

기저 사례 (종료 조건)

if len(sequence) == M:
    print(*sequence)
    return

• sequence의 길이가 M과 같아지면, 즉 M개의 숫자를 모두 선택하면 출력하고 종료.

순열 생성 (백트래킹)

for i in range(N):
    if visited[i] == False:
        sequence.append(i+1)
        visited[i] = True
        permutation(N, M, sequence, visited)
        sequence.pop()
        visited[i] = False

• for i in range(N): 1부터 N까지의 숫자를 차례대로 확인
• if visited[i] == False: 아직 사용하지 않은 숫자라면,
  1. sequence.append(i+1): 숫자를 추가
  2. visited[i] = True: 해당 숫자를 사용했다고 표시
  3. 재귀 호출: permutation(N, M, sequence, visited)을 호출하여 다음 숫자를 선택
  4. sequence.pop(): 재귀 호출이 끝난 후 숫자를 제거 (백트래킹)
  5. visited[i] = False: 방문 표시를 원래대로 복구

실행 흐름 (예제)

예제 입력

 

3 2

 

과정

1부터 3까지의 숫자 중 2개를 선택한 모든 순열을 구해야 한다.

• 초기 상태: N = 3, M = 2, sequence = [], visited = [False, False, False]

1️⃣ 첫 번째 숫자 선택 (1 선택)

• sequence = [1]
• visited = [True, False, False]

2️⃣ 두 번째 숫자 선택 (2 선택)

• sequence = [1, 2]
• visited = [True, True, False]
• 길이가 M(=2)이므로 출력 → "1 2"

🔙 백트래킹: 2 제거 → sequence = [1], visited = [True, False, False]

2️⃣ 두 번째 숫자 선택 (3 선택)

• sequence = [1, 3]
• visited = [True, False, True]
• 길이가 M(=2)이므로 출력 → "1 3"

🔙 백트래킹: 3 제거 → sequence = [1], visited = [True, False, False]

🔙 백트래킹: 1 제거 → sequence = [], visited = [False, False, False]

---

1️⃣ 첫 번째 숫자 선택 (2 선택)

• sequence = [2]
• visited = [False, True, False]

2️⃣ 두 번째 숫자 선택 (1 선택)

• sequence = [2, 1]
• visited = [True, True, False]
• 길이가 M(=2)이므로 출력 → "2 1"

🔙 백트래킹: 1 제거 → sequence = [2], visited = [False, True, False]

2️⃣ 두 번째 숫자 선택 (3 선택)

• sequence = [2, 3]
• visited = [False, True, True]
• 길이가 M(=2)이므로 출력 → "2 3"

🔙 백트래킹: 3 제거 → sequence = [2], visited = [False, True, False]

🔙 백트래킹: 2 제거 → sequence = [], visited = [False, False, False]

---

1️⃣ 첫 번째 숫자 선택 (3 선택)

• sequence = [3]
• visited = [False, False, True]

2️⃣ 두 번째 숫자 선택 (1 선택)

• sequence = [3, 1]
• visited = [True, False, True]
• 길이가 M(=2)이므로 출력 → "3 1"

🔙 백트래킹: 1 제거 → sequence = [3], visited = [False, False, True]

2️⃣ 두 번째 숫자 선택 (2 선택)

• sequence = [3, 2]
• visited = [False, True, True]
• 길이가 M(=2)이므로 출력 → "3 2"

🔙 백트래킹: 2 제거 → sequence = [3], visited = [False, False, True]

🔙 백트래킹: 3 제거 → sequence = [], visited = [False, False, False]

---

🔹 최종 출력 결과

 

 

1 2
1 3
2 1
2 3
3 1
3 2

---

시간 복잡도

• N! / (N-M)! 개의 순열을 만들므로, 최악의 경우 O(N!)이다.
• N이 커질수록 시간이 급격히 증가하므로, 효율적으로 백트래킹을 적용해야 한다.

 

라이브러리를 이용해 구현해 보자! (feat. itertools.permutation())

 

직접 구현한 permutation을 python에서 제공하는 itertools.permutation()으로 똑같이 구현할 수 있다. 

 

itertools.permutations()은 Python의 C로 구현된 내부 라이브러리 함수이므로, 우리가 Python에서 직접 재귀 호출을 사용하는 것보다 훨씬 빠르게 동작한다.

• itertools.permutations()은 내부적으로 C 언어 최적화가 적용되어 있어 Python 인터프리터를 통한 함수 호출과 메모리 관리 비용을 줄인다.
• 반면, 직접 구현한 백트래킹 방식은 Python의 재귀 호출 비용과 리스트 연산 비용이 포함되어 상대적으로 느리다.

결론적으로 itertools.permutations()이 더 빠르게 동작하는 가장 큰 이유는 C로 구현되어 있어서 함수 호출 오버헤드가 적기 때문이다.

 

import sys
import itertools

# N과 M 입력 받기
N, M = map(int, sys.stdin.readline().split())

# itertools.permutations을 이용하여 모든 순열 생성 후 출력
for perm in itertools.permutations(range(1, N+1), M):
    print(*perm)