1. 전수조사와 탐색

1-1. 전수조사 (Brute Force)

전수조사는 모든 상태를 확인하는 무식하지만 확실한 방법입니다. 비밀번호가 숫자 4자리라면 0000부터 9999까지 하는 방법을 의미합니다.

[Programmers] 숫자 야구

from itertools import product

def check(num, c):
    for case in c:
        s = str(case[0])
        strike, ball = 0, 0
        for i in range(3):
            for j in range(3):
                if num[i] == int(s[j]):
                    if i == j : strike += 1
                    else : ball += 1
        if [strike, ball] != case[1:] : return False          
    return True
    
def solution(baseball):
    answer = 0
    scope = range(1, 10)
    for num in product(scope, scope, scope):
        if len(set(num)) != 3 : continue
        if check(num, baseball) : answer += 1
    return answer

[BOJ 2798] 블랙잭

N, M = map(int, input().split())
lst = list(map(int, input().split()))

answer = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            s = lst[i] + lst[j] + lst[k]
            if s <= M:
                answer = max(s, answer)

print(answer)

[BOJ 1018] 체스판 다시 칠하기

실제 코딩테스트에는 다음 정도의 난이도가 나옵니다.

1-2. 트리 순회

상태를 트리로 표현할 수 있다면 어떤 방식으로 둘러볼 수 있을까요? 총 3가지 방법이 있습니다.

pre-order
in-order
post-order

1-3. 그래프 탐색

보통 그래프와 트리에서 사용하는 방법론으로 DFS와 BFS가 있습니다.

1-3-a. 깊이 우선 탐색 (Depth First Search)

깊이 우선 탐색(DFS, Depth First Search)란 탐색의 한 방법으로 어떤 상태에서 시작하여 이동이 불가능할 때까지 진행하다가 이동이 불가능하면 전 상태로 돌아오는 방식으로 답(원하는 상태 도달)을 구하는 방법입니다.

재귀함수의 성질을 띄고 있어 특징만 알고 있다면 쉽게 구현할 수 있습니다. (stack으로 구현할 수 있지만, 보통은 재귀함수로 구현합니다.)

1-3-b. 너비 우선 탐색 (Breadth First Search)

너비 우선 탐색(BFS, Breadth First Search)란 DFS와 마찬가지로 탐색의 한 방법입니다. 하지만 순서를 탐색하는 방법이 다릅니다. 초기 상태에서 가장 가까운 상태부터 살펴보는 방법입니다.

순서대로 한다는 특징을 가지고 있어 보통 queue로 구현합니다.

[BOJ 1697] 숨바꼭질

from collections import deque
N, K = map(int, input().split())

ck = [-1 for _ in range(200000)]
q = deque()

ck[N] = 0
q.append(N)

while len(q) > 0:
    front = q.popleft()
    if front == K:
        print(ck[K])
        break
    if front-1 >= 0 and ck[front-1] == -1:
        ck[front-1] = ck[front] + 1
        q.append(front-1)
    if front+1 < len(ck) and ck[front+1] == -1:
        ck[front+1] = ck[front] + 1
        q.append(front+1)
    if front*2 < len(ck) and ck[front*2] == -1:
        ck[front*2] = ck[front] + 1
        q.append(front*2)

공통으로 풀어볼 문제입니다.

[BOJ 1260] DFS와 BFS

1-4. 백트래킹

대표적인 문제로는 다음이 있습니다.

N Queen

1-5. 탐색 Techniques

탐색을 할 때, 사용하는 트릭 중 대표적인 트릭은 다음과 같습니다.

1-5-a. 방향벡터

2차원, 3차원 등의 다차원 맵에서 탐색을 하는 경우는 종종 있습니다. 이런 경우에는 맵의 공간을 효과적으로 접근할 수 있는 방법이 필요합니다.

우선 2차원 배열을 바탕으로 생각해보겠습니다. 2차원 배열에서 갈 수 있는 방향은 총 4개입니다.

동, 서, 남, 북 입니다. 이 동서남북은 배열을 기준으로 본다면 다음과 같이 쓸 수 있습니다.

# 동서남북 보다는 동남서북 등 시계방향으로 사용
# 변화량을 위해 dx, dy로 사용
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1], 

이제 조금 더 확장하면 동, 북동, 북, 북서, 서, 남서, 남, 남동으로도 표현할 수 있습니다.

# 8-방향벡터
dx = [1, 1, 0, -1, -1, -1 , 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

체스판의 Knight, 장기의 상 등 2차원에서도 특이하게 움직일 수 있는 상황은 많습니다. 이런 경우에도 마찬가지로 다음과 같이 선언하여 사용할 수 있습니다.

# 체스 나이트 예시

# 장기 상 예시

이제 이를 3차원으로 활용하는 경우, 동서남북상하로도 만들 수 있습니다.

[BOJ 16768] Mooyo Mooyo

이건 몰라도 무방합니다.

1-5-b. 비트마스크

탐색의 핵심은 상태입니다. 종종 이미 지난 상태나 체크한 상태의 정보를 유지하고 탐색을 진행해야하는 경우가 생깁니다. 하지만 상태를 container 형태로 전달하게 되면 비효율적일 수 있습니다. 그렇기에 이런 상태를 효율적인 전달하는 방법 중 하나가 비트마스크(bitmask) 입니다.

Chapter. 3