코딩테스트 준비할 때 필수 개념! <완전탐색> 알아보기

이번에 알아볼 주제는 완전탐색이다. 흔히 브루트-포스 알고리즘(Brute-force algorithm)이라고 불리는데 특별한 알고리즘은 아니고 무식하게 모든 경우를 탐색해보는 알고리즘이다. 모든 경우를 다 탐색하는 알고리즘이기에 정확성은 100% 보장되지만 반대로 속도는 최악이다. 따라서 문제에서 주어진 데이터가 매우 적을 때만 사용 가능하다. 예시로 든 문제들 모두 데이터의 개수가 매우 적은 것을 확인할 수 있다.

 

보통 완전탐색 문제는 for문과 if 문을 활용하거나 BFS/DFS를 활용하는 경우가 대부분이다. 다른 블로그를 찾아보면 백트래킹이나 비트마스크를 활용한다고 하는데, 사실 백트래킹도 주로 DFS를 활용해서 구현하고 비트마스크도 특정 알고리즘이라기보다 bit를 활용한 일종의 테크닉이기 때문에 따로 공부하지 않아도 완전탐색 문제를 풀다보면 자연스레 어디에 어떻게 활용하는지 감이 잡힐 것이다. 따라서 완전탐색 문제는 설명을 많이 읽어보는 것보다 문제를 많이 푸는 것을 추천한다.

 

다만 순열/조합을 활용해 완전탐색 문제를 푸는 방법은 꽤 자주 나오는데, 순열/조합을 생성하는 것이 익숙하지 않을 경우 버벅거릴 수 있기 때문에 Python을 활용해서 순열/조합을 간단하게 구현하는 법을 알려주고, 함께 풀면 좋은 문제를 많이 공유하도록 하겠다.

 

출제된 완전탐색 관련 문제

• 삼성 SW 역량 테스트 기출문제 "테트로미노"
• 2017 카카오코드 본선 "몸짱 트레이너 라이언의 고민"
• 2018 카카오코드 본선 "승부 예측"
• 삼성 SW 역량 테스트 기출문제 "연산자 끼워넣기"

꼭 알아둬야 할 Python으로 순열 구현하는 법

재귀적으로 순열을 구현하는 법

def permutation(arr, r):
    
    # 순열을 저장할 배열
    result = []
    
    # 실제 순열을 구하는 함수
    def permute(p, index):
        if len(p) == r:
            result.append(p)
            return

        for idx, data in enumerate(arr):
            if idx not in index: 
				# list는 mutable이기 때문에 새로운 리스트를 넘겨준다.
            	permute(p + [data], index + [idx])
				
    permute([], [])
    
    return result

for r in permutation(['A', 'B', 'C', 'D'], 2):
    print(r)


# --- Result ---
'''
['A', 'B']
['A', 'C']
['A', 'D']
['B', 'A']
['B', 'C']
['B', 'D']
['C', 'A']
['C', 'B']
['C', 'D']
['D', 'A']
['D', 'B']
['D', 'C']
'''

 

파이썬 Mutable 관련 정보는 아래 링크를 참고하면 된다.

Mutable vs. Immutable 차이점?

itertools.permutations을 사용해 구현하는 법

itertools 라이브러리에서 제공하는 permutations 메서드를 사용해서 순열을 구현할 수도 있다.
itertools.permutations docs(링크)

 

from itertools import permutations

# permutations(iterable, r)
# iterable의 원소들을 이용해 길이가 r인 순열을 생성한다.
# 리턴값은 순열 튜플의 이터레이터다.

data = "ABCD"
result = permutations(data, 2) # <itertools.permutations object at 0x7ff96110ee90>

for r in result:
    print(r)
    
# --- Result ---
'''
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'A')
('B', 'C')
('B', 'D')
('C', 'A')
('C', 'B')
('C', 'D')
('D', 'A')
('D', 'B')
('D', 'C')
'''

 

꼭 알아둬야 할 Python으로 조합 구현하는 법

재귀적으로 조합을 구현하는 법

# 재귀적으로 조합 구현

def combination(arr, r):
    
    # 조합을 저장할 배열
    result = []
    
    # 실제 조합을 구하는 함수
    def combinate(c, index):
        if len(c) == r:
            result.append(c)
            return 
        
        for idx, data in enumerate(arr):
            # 중복되는 조합이 생성되지 않게 마지막으로 들어온 원소의 인덱스보다
            # 새로 추가하는 원소의 인덱스가 큰 경우만 조합을 생성한다.
            if idx > index:
                combinate(c + [data], idx)
    
    combinate([], -1)
    
    return result

for r in combination(['A', 'B', 'C', 'D'], 2):
    print(r)
    
# --- Result ---
'''
['A', 'B']
['A', 'C']
['A', 'D']
['B', 'C']
['B', 'D']
['C', 'D']
'''

 

itertools.combinations을 사용해 구현하는 법

순열과 마찬가지로 조합도 itertools 라이브러리를 활용하면 쉽게 구현할 수 있다.
itertools.combinations docs(링크)

 

from itertools import combinations

# combinations(iterable, r)
# iterable의 원소들을 이용해 길이가 r인 조합을 생성한다.
# 리턴값은 조합 튜플의 이터레이터다.

data = "ABCD"
result = combinations(data, 2) # <itertools.combinations object at 0x7f603bdc5e90>

for r in result:
    print(r)
    
# --- Result ---
'''
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'C')
('B', 'D')
('C', 'D')
'''

 

함께 풀면 좋은 문제들

• 백준 2309번 문제 "일곱 난쟁이"
• 백준 18111번 문제 "마인 크래프트"
• 백준 9663번 문제 "N-Queen"
• 백준 2580번 문제 "스도쿠"
• 백준 14889번 문제 "스타트와 링크"
• 백준 10974번 문제 "모든 순열"
• 백준 2098번 문제 "외판원 순회"
• 백준 1759번 문제 "암호 만들기"
• 백준 14620번 문제 "꽃길"
• 백준 1182번 문제 "부분수열의 합"

 

코딩 테스트 준비할 때 필수 개념! 시리즈

• 코딩테스트 준비할 때 필수 개념! <문자열 처리> 알아보기
• 코딩테스트 준비할 때 필수 개념! <기본 자료구조> 알아보기