로또 1등에 당첨되고 싶으면 모든 번호 조합을 하나씩 다 사면 됩니다. 아 근데 그러면 60억 손해래요.

• 45개 중 6개 고르는 경우의 수 = $\binom{45}{6} = 8,145,060$
  • 1장당 $1,000$원이니, 총 비용은 $8,145,060,000$원 (약 80억)
• 로또 1등 당첨금: 약 (20억) 원
• 결국엔 60억 손해^^

현실에선 이런 방법이 쓸모없지만, 알고리즘 문제를 풀 땐 쓸모있을 때가 꽤 많습니다. 바로 브루트 포스입니다.

완전 탐색

• 브루트 포스로도 불림. 가능한 모든 경우의 수를 시도하는 방법
  • 예: 캐리어 비밀번호를 까먹어 0000부터 9999까지 시도해 보기
• 보통 시간 복잡도가 높은 편 ($O(N^3)$ 이상인 경우도 많음)
  • $N$이 적은 경우 완전 탐색으로 풀 수 있음
• 그리디 알고리즘마냥 매번 유리한 선택을 하지도 않고, 한정 분기법마냥 정답이 될 수 없는 경우를 미리 가지치기하지도 않음

itertools로 순열, 조합 계산하기

기능	함수	중복	순서	계산 횟수
조합	combinations(a, r)	X	X	$\frac{N!}{r!(N-r)!}$
중복조합	combinations_with_replacement(a, r)	O	X	$\frac{(N + r - 1)!}{r!(N-1)!}$
순열	permutations(a, r)	X	O	$\frac{N!}{(N - r)!}$
중복순열	product(a, repeat=r)	O	O	$N^r$

• 완전 탐색 문제를 풀 땐 가능한 모든 경우를 구해야 하는 경우가 많음
• 따라서 고등학교 확률과 통계 시간 때 배운 순열과 조합 개념이 자주 사용됨
• 내장 itertools 모듈 함수들의 도움을 받을 수 있음
• 공통적으로 이터러블 객체 a와, 뽑을 원소 수 r를 인수로 받음
  • 이터러블: for문에서 하나씩 순회 가능한 객체. 리스트, 튜플, 집합, 딕셔너리, 문자열, range() 등
• 가능한 모든 순열 / 조합을 생성하는 이터러블을 반환
  • 각각의 결과는 튜플의 형태로 반환됨

조합

from itertools import combinations

a = [1, 2, 3, 4]
result = []
for cmb in combinations(a, 2):
    result.append(cmb)
print(f"총 조합 수: {len(result)}")

# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
# 총 조합 수: 6

• 이터러블 객체 a 중에서 원소 r개를 중복 없이, 순서 없이 뽑은 모든 조합을 구함
  • r을 생략하면 에러 발생
• 시간 복잡도: 이터러블 객체의 원소 수를 $N$으로 둘 때
  • $\binom{N}{r} = \frac{N!}{r!(N-r)!}$
  • 위 예제의 경우 $\binom{4}{2} = \frac{4!}{2!2!} = 6$

중복조합

from itertools import combinations_with_replacement

a = [1, 2, 3, 4]
result = []
for cmb in combinations_with_replacement(a, 2):
    result.append(cmb)
print(f"총 중복조합 수: {len(result)}")

# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]
# 총 중복조합 수: 10

• 이터러블 객체 a 중에서 원소 r개를 중복을 허용하고, 순서 없이 뽑은 모든 조합을 구함
  • r을 생략하면 에러 발생
• 시간 복잡도: 이터러블 객체의 원소 수를 $N$으로 둘 때
  • $\binom{N + r - 1}{r} = \frac{(N + r - 1)!}{r!(N-1)!}$
  • 위 예제의 경우 $\binom{4 + 2 - 1}{2} = \frac{5!}{3!2!} = 10$

순열

from itertools import permutations
a = [1, 2, 3, 4]
result = []
for pm in permutations(a, 2):
    result.append(pm)
print(f"총 순열 수: {len(result)}")

# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
# 총 순열 수: 12

• 이터러블 객체 a 중에서 원소 r개를 중복 없이, 순서를 고려하여 뽑은 모든 순열을 구함
  • r을 생략하면 len(a)로 처리
• 시간 복잡도: 이터러블 객체의 원소 수를 $N$으로 둘 때
  • $P(N, r) = \frac{N!}{(N - r)!}$
  • 위 예제의 경우 $P(4, 2) = \frac{4!}{2!} = 12$

중복순열

from itertools import product
a = [1, 2, 3, 4]
result = []
# 얘만 repeat을 따로 파라미터로 지정해야 함
for pm in product(a, repeat=2):
    result.append(pm)
print(result)
print(f"총 중복순열 수: {len(result)}")

# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]
# 총 중복순열 수: 16

• 이터러블 객체 a 중에서 원소 repeat개를 중복을 허용하고, 순서를 고려하여 뽑는 모든 순열을 구함
  • repeat을 따로 파라미터로 지정해야 함에 유의
  • 생략하면 기본값 1
• 시간 복잡도: 이터러블 객체의 원소 수를 $N$으로 둘 때
  • $N ^ r$, 위 예제의 경우 $4 ^ 2 = 16$

문제풀이

1436. 영화감독 숌

백준 / 실버 5 / 1436. 영화감독 숌

• 꼭 브루트포스라고 해서 순열, 조합 문제만 나오는 건 아니고, 이런 문제도 있음
• 6이 3개 이상 연속으로 들어가는 수들을 구했을 때, 그 중 $N$번째 수 구하기

N = int(input())
num = 1
count = 0

while True:
    if "666" in str(num):
        count += 1
    if count == N:
        print(num)
        break
    num += 1

• 1부터 순서대로 체크하면서 6이 3개 이상 연속으로 들어가면 count 1 증가
• count가 N이 되면 반복 멈추고 해당 num 출력
• $N <= 10000$이긴 한데, $N$번 계산하는 게 아니라 $N$이 나올 때까지 계산하는 문제라 시간 복잡도를 구하기 애매하긴 함
  • 실제로 10000을 입력해 보니 2666799이 출력된 걸 봐서, 최대 2666799번 연산이 이루어짐

10971. 외판원 순회 2

문제가 길어져 별도 글로 대체

2468. 안전 영역

문제가 길어져 별도 글로 대체