6. 완전탐색

Posted Apr 17, 2025

By JUNHEE LEE

15 min read

6. 완전탐색

1. 완전탐색이란?

가능한 모든 경우의 수를 시도해서 정답을 찾는 방식.
조건을 만족하는 답을 찾을 때까지 모든 경우를 전부 탐색

언제 사용?

입력 크기 작을 때 (보통 N ≤ 10~15 정도)
“모든 경우를 일단 다 해봐야 해”라고 생각될 때

2. 완전탐색의 대표 유형

기법	설명	사용 함수
순열 (permutation)	순서를 고려한 모든 경우	`itertools.permutations`
조합 (combination)	순서를 고려하지 않고, 정해진 수만큼 뽑기	`itertools.combinations`
중복 순열 (product)	중복 허용, 여러 자리 수 만들기	`itertools.product`
부분집합 탐색	모든 부분집합 확인	비트마스크 or 백트래킹

3. 각 유형별 예제

1. 순열 - `itertools.permutations`

숫자 1, 2, 3을 이용해 만들 수 있는 모든 순서 출력

  
from itertools import permutations 

arr = [1, 2, 3]
result = permutations(arr, 3)

for i in result:
	print(i)

'''
결과
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
'''

2. 조합 - `itertools.combinations`

조합(combination) 은 주어진 요소 중에서 원하는 개수만큼 선택하되, 같은 조합이면 순서를 다르게 해도 하나로 보는 경우에 사용한다.

예제: A, B, C, D 중 2명 팀 짜기

여기서는 'A', 'B', 'C', 'D' 총 4명 중에서 2명을 뽑아 팀을 만드는 경우를 구한다.
팀 구성에는 순서가 중요하지 않으므로 (A, B)와 (B, A)는 같은 팀으로 간주되어 한 번만 출력된다.

  
from itertools import combinations

arr = ['A', 'B', 'C', 'D']

result = combinations(arr, 2)
for i in result:
	print(i)

'''
결과 
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'C')
('B', 'D')
('C', 'D')
'''

언제 사용할까?

팀 구성, 조별 과제 멤버 선정
카드 게임에서 손패 조합 구하기
메뉴 중 몇 가지를 선택하는 조합 찾기
소수 클래스 데이터 샘플 증강 시 조합 기반 증강

`permutations`와의 차이

permutations는 순서를 다르게 하면 다른 경우로 봄
combinations는 순서가 달라도 같은 경우로 처리

3. 중복 순열 - `itertools.product`

예제: 0~9 숫자를 중복 허용해서 2자리 비밀번호 생성

  
from itertools import product

digits = list(range(10))
result = product(digits, repeat=2)

for i in result:
	print(i)

'''
결과 일부
(0, 0)
(0, 1)
(0, 2)
...
(9, 8)
(9, 9)
'''

4. 부분집합 탐색 - `비트마스크 or 반복문`

부분집합(subset) 은 어떤 집합의 원소들로 만들 수 있는 모든 조합.
조합처럼 고정 개수만 뽑는 게 아니라, 전체 부분집합을 전부 탐색해야 하는 문제에서 사용됨
특히 최대합, 최소차이, 백트래킹 문제, 집합 비교 문제 등에서 핵심 도구로 등장
DFS/백트래킹으로도 가능하지만, 작은 집합에서는 비트마스크가 더 빠르고 간단함

예를 들어 [1, 2, 3]의 부분집합은 [], [1], [2], [1, 2], …, [1, 2, 3]처럼 총 2^n개가 존재한다.

비트마스크 방식이란?

정수 i를 이진수로 해석해서, 그걸 선택 여부의 마스크로 사용하는 방법
예를 들어 i = 5 (0b101)이면, arr[0]과 arr[2]를 선택했다는 의미

  
arr = ['A', 'B', 'C']

for i in range(1<<len(arr)):
	result = []
	for j in range(len(arr)):
		if i & (1 << j):
			result.append(arr[j])
	print(result)

'''
결과 
[]
['A']
['B']
['A', 'B']
['C']
['A', 'C']
['B', 'C']
['A', 'B', 'C']
'''

`i` 값과 대응되는 이진수 해석

i (10진수)	i (2진수)	부분집합
0	000	`[]`
1	001	`[A]`
2	010	`[B]`
3	011	`[A, B]`
4	100	`[C]`
5	101	`[A, C]`
6	110	`[B, C]`
7	111	`[A, B, C]`

언제 사용 할까?

“모든 경우의 수” 를 따져야 할 때
최적의 조합, 최소 차이, 조건을 만족하는 부분집합 탐색 등
예:
부분집합 중 합이 K인 경우의 수
두 집합으로 나눠 최소 차이를 구하라
최대 XOR 값 구하는 문제

요약:

비트마스크를 활용하면 2^n개의 부분집합을 간단하게 순회할 수 있다. 특히 원소 수가 적은 경우(20 이하) 빠르고 효율적이다.

4. 핵심 개념 요약

1. `itertools.permutations`, `combinations`, `product`는 길이(개수)가 정해져 있음

이 세 개는 전부 “몇 개를 뽑을지”를 명시 ```python permutations(data, r)

combinations(data, r)

product(data, repeat=r)

<br/>

---
### 2. `permutations`: **길이 r짜리 뽑기 + 순서 중요**

> 예: `permutations(['A', 'B'], 2)` → `[('A', 'B'), ('B', 'A')]`

<br/>
  
---
### 3. `combinations`: **길이 r짜리 뽑기 + 순서 무시**

> 예: `combinations(['A', 'B'], 2)` → `[('A', 'B')]` (B, A는 안 나옴)

<br/>
  
---
### 4. `product`: **중복 포함, 길이 r짜리 모든 조합**

> 예: `product(['A', 'B'], repeat=2)` → `[('A','A'), ('A','B'), ('B','A'), ('B','B')]`

<br/>

---
### 5. **비트마스크는 개수 r을 정하지 않음. 그냥 모든 경우 다 탐색**

```python
arr = ['A', 'B']

→ 가능한 부분집합은: [], ['A'], ['B'], ['A', 'B']

→ 총 2^n = 4개

이건 “길이 0부터 n까지” 모든 부분집합을 다 포함
즉, r이 고정되지 않음 → [[], [A], [B], [A,B]]

[A, B] 가 주어졌을 때

기법	길이 r 고정?	중복 허용?	순서 중요?	예시
`permutations`	✅ 예	❌ 아니오	✅ 예	(A,B), (B,A)
`combinations`	✅ 예	❌ 아니오	❌ 아니오	(A,B)
`product`	✅ 예	✅ 예	✅ 예	(A,A), (A,B), (B,A), (B,B)
비트마스크	❌ 아니오 (0~n까지 다 포함)	❌ 아니오	❌ 아니오	[], [A], [B], [A,B]

구분	핵심 내용
언제 쓰나?	“경우의 수를 다 따져봐야 할 때”, 입력 크기 작을 때
시간복잡도?	일반적으로 느림 — (O(N!), O(2^N))
조합/순열/중복/부분집합	`itertools`로 빠르게 구현 가능
현업/코테 활용도	높음 — 기초 탐색 로직 + 조건 필터링 조합

5. 실전 문제

문제 1.

주어진 알파벳 L개 중에서 C개를 선택해, 조건을 만족하는 모든 비밀번호 조합을 출력하는 문제.
단순 조합 생성이 아니라 조건을 만족해야 한다.

입력 설명

첫 줄: 정수 L C가 주어짐
- L: 만들어야 할 비밀번호의 길이
- C: 주어지는 알파벳 개수
두 번째 줄: C개의 소문자 알파벳이 주어짐
- 알파벳은 오름차순으로 정렬된 상태로 출력해야 함

조건

반드시 모음 1개 이상
반드시 자음 2개 이상
오름차순 정렬된 문자열만 유효한 비밀번호로 간주

가능한 조합

알파벳 6개 중 4개 선택 → 6C4 = 15가지 조합 가능
예: a c i s, a c i t, a i s w, …

조건 체크 예시

조합 중 a c i s 를 보자.

모음: a, i → 2개 → ✅
자음: c, s → 2개 → ✅ → 유효한 비밀번호!

📥 입력 예시

4 6

a t c i s w

📤 출력 예시

acis
acit
aciw
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

※ 출력은 오름차순이어야 함 (사전순 정렬)

해설

  
from itertools import combinations

def is_valid(password):
	모음 = 'aeiou'
	m = sum(1 for i in password if i in 모음)
	j = len(password) - m

	return m >= 1 and j >= 2

L, C = list(map(int, input().split()))
letters = input()

letters = sorted(letters)
for i in combinations(letters, L):
	if is_valid(i):
		print(''.join(i))

문제 2. 세 수로 나누어 합 맞추기

1부터 9까지의 숫자를 한 번씩만 사용해서 A + B = C가 되도록 세 수 A, B, C를 만들어라. A, B, C는 각각 아무 자리 수여도 괜찮다.

(예: A=1, B=2345, C=6789도 가능)

단, 1~9 사이 숫자를 중복 없이 전부 다 사용해야 함

📥 입력 예시

입력은 따로 없음.

📤 출력 예시

  
123 + 456 = 579

1234 + 5678 = 6912

...

가능한 모든 A + B = C 형태를 출력한다.

해설

  
from itertools import permutations 

digits = list(range(1, 10))

for perm in permutations(digits):
	for i in range(1, 8):
		for j in range(i+1, 9):
			A = int(''.join(map(str, perm[:i])))
			B = int(''.join(map(str, perm[i:j])))
			C = int(''.join(map(str, perm[j:])))

			if A + B == C:
				print(f'{A} + {B} = {C}')

''' 출력
124 + 659 = 783 
125 + 739 = 864 
127 + 359 = 486 
127 + 368 = 495 
128 + 367 = 495 
128 + 439 = 567 
129 + 357 = 486 
129 + 438 = 567 
129 + 654 = 783 
129 + 735 = 864 
134 + 658 = 792
...
782 + 154 = 936 
782 + 163 = 945 
783 + 162 = 945 
784 + 152 = 936
'''

문제 3. 금고 비밀번호 찾기

📘 문제 설명

길이가 N인 숫자 조합 중에서 모든 자리의 합이 S가 되는 숫자들을 찾아라.

숫자는 0~9 중복 가능
자리 수는 N자리, 앞자리에 0이 와도 된다

총 몇 개의 조합이 존재하는가?

📥 입력 형식

N S

N: 비밀번호 자리수 (1 ≤ N ≤ 6)
S: 원하는 자리 합 (0 ≤ S ≤ 54)

📤 출력 형식

조건을 만족하는 조합의 개수 출력

입력 예시

2 5

출력 예시

6

해설

  
from itertools import product

N, S = map(int, input().split())
password = list(range(10))

result = sum(1 for result in product(password, repeat = N) if sum(result) == S)

print(result)

'''
6
'''

문제 4. 암호 해독기

📘 문제 설명

알파벳 대문자로 이루어진 문자열이 주어진다. 여기서 알파벳의 순서를 조합해서 만든 문자열이 주어진 암호 문자열과 아나그램(anagram) 관계인지 판별하라.

아나그램: 철자만 바뀌었고, 등장한 문자의 수가 같은 관계

📥 입력 형식

원본 문자열

암호 문자열

문자열 길이 ≤ 10

📤 출력 형식

아나그램 관계면 1, 아니면 0 출력

입력 예시

ARMY

MARY

출력 예시

1

해설

itertools.permutations 방식 O(n!) > 이렇게도 풀 수 있다는거지 이렇게 풀라는건 아님

  
from itertools import permutations 

s1 = input().strip()
s2 = input().strip()

if_found = any(''.join(p) == s2 for p in permutations(s1))

print(is_found)

Sorting 방식 O(n log n)

  
s1 = input().strip()
s2 = input().strip()

print(1 if sorted(s1) == sorted(2) else 0)

코딩 테스트

This post is licensed under CC BY 4.0 by the author.

6. 완전탐색

1. 완전탐색이란?

2. 완전탐색의 대표 유형

3. 각 유형별 예제

1. 순열 - itertools.permutations

2. 조합 - itertools.combinations

예제: A, B, C, D 중 2명 팀 짜기

언제 사용할까?

permutations와의 차이

3. 중복 순열 - itertools.product

4. 부분집합 탐색 - 비트마스크 or 반복문

비트마스크 방식이란?

i 값과 대응되는 이진수 해석

언제 사용 할까?

요약:

4. 핵심 개념 요약

1. itertools.permutations, combinations, product는 길이(개수)가 정해져 있음

5. 실전 문제

문제 1.

입력 설명

조건

가능한 조합

조건 체크 예시

📥 입력 예시

📤 출력 예시

해설

문제 2. 세 수로 나누어 합 맞추기

📥 입력 예시

📤 출력 예시

해설

문제 3. 금고 비밀번호 찾기

📘 문제 설명

📥 입력 형식

📤 출력 형식

입력 예시

출력 예시

해설

문제 4. 암호 해독기

📘 문제 설명

📥 입력 형식

📤 출력 형식

입력 예시

출력 예시

해설

itertools.permutations 방식 O(n!) > 이렇게도 풀 수 있다는거지 이렇게 풀라는건 아님

Sorting 방식 O(n log n)

Trending Tags

1. 순열 - `itertools.permutations`

2. 조합 - `itertools.combinations`

`permutations`와의 차이

3. 중복 순열 - `itertools.product`

4. 부분집합 탐색 - `비트마스크 or 반복문`

`i` 값과 대응되는 이진수 해석

1. `itertools.permutations`, `combinations`, `product`는 길이(개수)가 정해져 있음