Table of Content
길었던 멋사 부트캠프의 일정이 끝나고…. 다시금 자료 구조와 알고리즘 공부로 돌아오게 되었다. 그렇게 다시 마주한 것은 바로 완전탐색 !
어떻게 하면 완전탐색 문제를 조금 더 편하게, 그리고 파이썬답게 풀 수 있을지 정리해보려고 한다.
이번 글에서는 완전탐색 자체에 대한 아주 짧은 설명부터, 문제를 풀 때 자주 쓰게 되는 파이썬 구현 방식, 그리고 프로그래머스 알고리즘 고득점 Kit 문제 풀이까지 한 흐름으로 정리해보려 한다.
| 주제 | 세부 내용 |
|---|---|
| 완전탐색이란 | 완전탐색의 감각, 언제 단순하게 가도 되는가 |
| 파이썬 구현 방식 | 에라토스테네스의 체, 인라인 for if, itertools |
| 문제 풀이 | 최소직사각형, 소수 찾기, 카펫, 전력망, 모음사전 |
🔍 자료구조 / 알고리즘에 대한 간략한 설명
완전 탐색은 알고리즘이라고 할 것이 별로 많지 않다….! 그저 반복문을 돌고 또 돌 뿐….
하지만 막상 문제를 풀다 보면, 이 “돌고 또 도는” 과정을 어떤 자료형으로, 어떤 파이썬 문법으로, 어느 범위까지 돌릴지를 정하는 게 더 중요할 때가 많다.
특히 코딩 테스트에서는 다음 두 가지가 굉장히 중요했다.
- 모든 경우의 수를 정말 다 봐야 하는 문제인지
- 다 본다면, 그걸 파이썬으로 얼마나 덜 귀찮게 구현할 수 있는지
완전탐색은 엄청난 아이디어 싸움이라기보다,
문제를 가능한 경우의 수로 잘 쪼개고 그걸 실수 없이 순회하는 힘에 더 가깝다.
그래서 이번 글도 “이론”보다는, 완전탐색 문제를 풀 때 자주 쓰는 구현 감각에 더 가깝게 정리해보려 한다.
🐍 여러가지 파이썬 구현 방식
에라토스테네스의 체
완전탐색 문제를 풀다 보면 생각보다 자주 마주치는 것이 바로 소수 판별이다.
그럴 때마다 매번 나눠보는 식으로 풀기 시작하면 꽤나 귀찮아진다. 그래서 비슷한 원리로 구성되는 에라토스테네스의 체를 먼저 익혀두면 좋다.
에라토스테네스의 체란 자연수
n까지의 소수를 구하는 대표적인 방법을 말한다.
작은 수부터 훑으면서 해당 수의 배수들을 차례대로 지워 나가는 방식이다.
가장 처음 떠오르는 구현은 보통 이렇다.
1부터n까지를 담은 자료형을 만들고- 배수들을 하나씩 지우는 방식
그런데 이건 생각보다 비효율적이다.
실제 “소수 값”을 계속 관리하기보다는, 해당 자리가 소수인지 아닌지만 표시하는 자료형을 두는 편이 훨씬 편하다. 예를 들면 [False, False, True, True, ...] 같은 식이다.
여기서 한 걸음 더 나아가면 파이썬의 bytearray를 활용할 수 있다. 0~255 정수를 바이트 단위로 저장하는 배열이라, 단순한 마킹 배열을 만들 때 일반 리스트보다 가볍게 쓸 수 있다.
from math import isqrt
def get_primes(n):
is_prime = bytearray(b'\x01') * (n + 1)
if n >= 0:
is_prime[0] = 0
if n >= 1:
is_prime[1] = 0
for r in range(2, isqrt(n) + 1):
if is_prime[r]:
start = r * r
is_prime[start:n+1:r] = b'\x00' * ((n - start) // r + 1)
return is_prime
is_prime = get_primes(20)
print(is_prime[2], is_prime[4], is_prime[19]) # 1 0 1핵심은 실제 소수만 따로 들고 있지 말고, “이 수가 소수인가?”만 빠르게 판별할 수 있는 배열을 먼저 만드는 것이다.
완전탐색 문제에서는 이 “판별기” 하나가 나중에 정말 든든하게 쓰인다.
물론 bytearray가 아직 낯설다면 그냥 리스트로 시작해도 충분하다. 중요한 건 자료형 그 자체보다, 한 번 계산한 판별 결과를 계속 재활용하는 감각이다.
인라인 for if 구문
완전탐색 문제를 풀다 보면, 가능한 후보를 한 번에 모아두고 그중에서 조건에 맞는 것만 걸러내는 일이 굉장히 많다.
그럴 때 파이썬의 인라인 for if 구문, 즉 리스트 컴프리헨션은 체감상 거의 필수에 가깝다.
예를 들어 어떤 수의 약수 쌍만 빠르게 모으고 싶다면 이런 식으로 쓸 수 있다.
from math import isqrt
yellow = 24
pairs = [(yellow // y, y) for y in range(1, isqrt(yellow) + 1) if yellow % y == 0]
print(pairs) # [(24, 1), (12, 2), (8, 3), (6, 4)]이 구문의 장점은 분명하다.
- 조건을 만족하는 값만 바로 모을 수 있고
- 별도의
append()반복이 줄어들고 - “무엇을 모으려는지”가 코드에 바로 드러난다
완전탐색은 경우의 수 자체가 많기 때문에, 이 경우의 수를 얼마나 간결하게 표현하느냐가 생각보다 중요하다.
특히 문제를 처음 풀 때는 구현이 길어질수록 실수도 같이 늘어난다. 그래서 인라인 for if 구문은 익숙해질수록 정말 자주 손이 간다.
itertools 이용
완전탐색을 파이썬으로 할 때 거의 치트키처럼 느껴지는 모듈이 있다. 바로 itertools다.
특히 아래 세 가지는 정말 자주 쓴다.
permutations: 순열combinations: 조합product: 중복 허용 곱집합
예를 들어 문자열 숫자들로 만들 수 있는 모든 순열을 보고 싶다면 이렇게 쓸 수 있다.
from itertools import permutations
numbers = ['0', '1', '1']
for p in permutations(numbers, 2):
print("".join(p))또 특정 문자들을 길이별로 모두 조합하고 싶다면 product도 굉장히 유용하다.
from itertools import product
for p in product("AEIOU", repeat=2):
print("".join(p))이런 도구들이 좋은 이유는, 완전탐색 문제에서 가장 귀찮은 부분인 모든 경우의 수 생성을 훨씬 짧고 안정적으로 처리해주기 때문이다.
특히
itertools는 “내가 지금 직접 재귀를 짜야 하나…?” 싶은 순간에
한 번쯤 먼저 떠올려볼 만한 도구다.
물론 항상 itertools만으로 끝나는 것은 아니다. 어떤 경우에는 재귀가 더 자연스러울 수도 있다.
하지만 적어도 파이썬으로 완전탐색을 공부하는 단계에서는, itertools를 익혀두는 것만으로도 체감 난이도가 꽤 내려간다.
✅ 프로그래머스 문제 풀이
최소직사각형 Lv.1
지갑의 가로, 세로 길이가 주어졌을 때 모든 명함을 수납할 수 있는 최소 크기의 지갑을 구하는 문제다.
핵심은 단순하다.
각 명함마다 긴 변은 모두 가로로, 짧은 변은 모두 세로로 정렬해놓고 생각하면 된다. 그러면 최종 답은:
- 긴 변들 중 최댓값
- 짧은 변들 중 최댓값
이 둘을 곱한 값이 된다.
def solution(sizes):
maxi = max(max(w, h) for w, h in sizes)
mini = max(min(w, h) for w, h in sizes)
return maxi * mini파이썬의 min, max는 언제나 활용도 1순위….!!
이 문제는 복잡하게 생각하기보다, 회전 가능한 명함을 어떻게 한 방향으로 정렬해서 볼지만 떠올리면 금방 풀린다.
소수 찾기 Lv.2
문자열로 주어진 숫자 조각들을 이어 붙여 만들 수 있는 소수의 개수를 구하는 문제다.
이 문제는 앞서 공부한 에라토스테네스의 체와 itertools.permutations를 같이 써먹기 정말 좋다.
풀이 흐름은 아래처럼 잡았다.
- 만들 수 있는 최대 수까지의 소수 판별 배열을 만든다.
- 주어진 숫자들로 가능한 모든 순열을 만든다.
- 앞자리가
0인 경우를 처리하면서 실제 숫자로 바꾼다. - 소수라면
set에 넣는다.
from math import isqrt
from itertools import permutations
def get_primes(n):
is_prime = bytearray(b'\x01') * (n + 1)
if n >= 0:
is_prime[0] = 0
if n >= 1:
is_prime[1] = 0
for r in range(2, isqrt(n) + 1):
if is_prime[r]:
start = r * r
is_prime[start:n+1:r] = b'\x00' * ((n - start) // r + 1)
return is_prime
def solution(numbers):
is_prime = get_primes(10 ** len(numbers))
answer = set()
digits = list(numbers)
for n in range(1, len(digits) + 1):
for p in permutations(digits, n):
num = "".join(p).lstrip("0")
if num and is_prime[int(num)]:
answer.add(int(num))
return len(answer)이 문제를 풀면서 느낀 건, 완전탐색 자체보다도 “판별기를 먼저 만들어두자”는 감각이 더 중요하다는 점이었다.
소수 판별을 매번 하지 않고 배열 조회로 바꿔버리면, 이후의 완전탐색이 훨씬 수월해진다.
그리고 다른 분 풀이를 보다가 감명을 받아버린 것….
이런 경우는 permutations 말고도 재귀로 완전탐색을 구현할 수 있다.
prime_set = set()
def dfs(current, remaining):
if current:
number = int(current)
if is_prime[number]:
prime_set.add(number)
for i in range(len(remaining)):
dfs(current + remaining[i], remaining[:i] + remaining[i+1:])핵심은 한 글자씩 넘겨주면서 재귀 호출을 반복하는 것이다.
문자열 기반 완전탐색에서는 이런 방식도 자주 쓰이니 같이 익혀두면 좋다.
카펫 Lv.2
주어진 brown, yellow 타일 수를 보고 전체 카펫의 가로세로 크기를 구하는 문제다.
이 문제는 내부를 채우는 yellow 영역만 먼저 생각하면 조금 편해진다.
결국 yellow를 만들 수 있는 약수 쌍들을 모두 구한 뒤, 그 둘레에 brown이 딱 맞게 둘러지는지를 확인하면 된다.
from math import isqrt
def solution(brown, yellow):
candidates = [
(yellow // h, h)
for h in range(1, isqrt(yellow) + 1)
if yellow % h == 0
]
for inner_w, inner_h in candidates:
if brown == 2 * (inner_w + inner_h) + 4:
return [inner_w + 2, inner_h + 2]가장 먼저 yellow 타일을 제곱근까지만 보며 가능한 배열 쌍을 구하고,
그 뒤 실제 brown 타일 수와 맞는지 비교하는 식이다.
인라인 for if 구문이 익숙했다면 비교적 깔끔하게 풀리는 문제였다.
이런 문제는 결국 “가능한 후보를 먼저 다 모으고, 조건에 맞는 것만 고르기”의 전형 같은 느낌이다.
전력망을 둘로 나누기 Lv.2
다음은 트리 구조의 전력망 네트워크를 한 군데 끊어서, 두 전력망의 크기 차이가 최소가 되도록 만드는 문제다.
이 문제는 처음에 정말 고민을 많이 했다.
딕셔너리로 풀까, 리스트로 풀까, 그냥 클래스를 만들어서 풀까….
주어진 노드에서 한 단계 더 내려간 여러 노드들을 어떻게 구하고, 그 다음 단계는 또 어떻게 볼까 싶어서 꽤 오래 붙잡고 있었다.
결국 정리해보면 핵심은 단순하다.
- 간선 하나를 끊어본다.
- 한쪽 네트워크의 노드 수를 센다.
- 나머지 쪽과의 차이를 계산한다.
- 이걸 모든 간선에 대해 반복한다.
이 흐름만 잡히면 BFS나 DFS로 풀 수 있다.
from collections import defaultdict, deque
def solution(n, wires):
graph = defaultdict(list)
for a, b in wires:
graph[a].append(b)
graph[b].append(a)
def bfs(start, cut_edge):
visited = {start}
queue = deque([start])
while queue:
cur = queue.popleft()
for nxt in graph[cur]:
if (cur, nxt) == cut_edge or (nxt, cur) == cut_edge:
continue
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
return len(visited)
answer = n
for a, b in wires:
size = bfs(a, (a, b))
answer = min(answer, abs((n - size) - size))
return answer처음에는 “이걸 어떻게 하나씩 타고 내려가지…?” 싶었는데, 결국은 간선을 하나씩 제거하면서 연결된 노드 수를 세는 문제였다.
이렇게 보고 나니 훨씬 정직한 완전탐색 문제가 되어버린 것.
모음사전 Lv.2
마지막은 A, E, I, O, U 다섯 개의 모음으로 만들 수 있는 모든 단어를 사전순으로 나열했을 때, 특정 단어가 몇 번째인지 구하는 문제다.
처음 보면 뭔가 규칙을 찾아야 할 것 같지만, 사실 이 문제는 완전탐색이 아주 정직하게 먹히는 문제다.
왜냐하면 길이가 1부터 5까지이고, 사용할 수 있는 문자가 5개뿐이기 때문이다.
전체 경우의 수는 다음과 같다.
- 1글자:
5 - 2글자:
25 - 3글자:
125 - 4글자:
625 - 5글자:
3125
전부 더해도 3905개밖에 되지 않는다.
이 정도면 그냥 다 만들어놓고 찾는 것이 훨씬 마음 편하다.
from itertools import product
def solution(word):
vowels = "AEIOU"
words = []
for length in range(1, 6):
for p in product(vowels, repeat=length):
words.append("".join(p))
words.sort()
return words.index(word) + 1예를 들면:
print(solution("AAAAE")) # 6
print(solution("AAAE")) # 10
print(solution("I")) # 1563
print(solution("EIO")) # 1189이 문제는 괜히 어렵게 접근하지 않아도 된다는 점이 오히려 포인트였다.
완전탐색 문제를 풀다 보면 자꾸 “더 똑똑한 방법이 있지 않을까?”를 먼저 찾게 되는데, 이 문제는 오히려 그 반대였다.
경우의 수가 충분히 작다면,
그냥 다 만들고 찾는 것이 가장 깔끔한 풀이가 될 수도 있다.
물론 이 문제는 가중치를 이용해 더 수학적으로 푸는 방법도 존재한다.
하지만 지금 글의 주제가 완전탐색인 만큼, itertools.product로 끝까지 밀어붙이는 방식이 더 잘 어울린다고 느꼈다.
완전탐색은 “엄청난 아이디어가 필요한 알고리즘”이라기보다, 가능한 경우를 빠짐없이 잘 다루는 구현력에 더 가깝다.
그래서 오히려 파이썬에서는 어떤 문법과 자료형을 익혀두었는지가 체감 난이도에 꽤 큰 영향을 준다.
이번에 문제들을 다시 정리하면서 느낀 것도 비슷했다.
에라토스테네스의 체, 인라인 for if 구문, itertools, 그리고 경우에 따라 재귀까지. 이런 도구들을 하나씩 익혀두면 완전탐색 문제는 생각보다 훨씬 덜 막힌다.
부트캠프가 끝나고 다시 돌아온 알고리즘 공부는 조금 낯설었지만, 완전탐색처럼 정직한 주제부터 다시 잡아가니 오히려 감이 천천히 돌아오는 느낌이었다.
앞으로도 고득점 Kit 문제들을 풀면서, 이런 식으로 구현 감각을 하나씩 정리해보려고 한다.
