[SW 정글] WEEK01 개발일지(백트래킹)

* 알고리즘에 대한 내용은 제 스스로의 생각을 적은 것입니다. 잘못된 내용이 있을 수 있으니 비판적으로 받아들여주시기 바랍니다. 잘못된 내용은 댓글에 남겨주시면 감사하겠습니다.

알고리즘 입문

 목요일 미니프로젝트 발표가 끝난 뒤 바로 '컴퓨팅 사고로의 전환'을 주제로한 알고리즘 공부가 시작되었다.

 

 - Week01 주제 : 정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도

 

 이번 주는 총 39개의 백준 문제가 주어졌으며 하~중의 난이도를 갖고 있었다. 불행인지 다행인지 기존에 알고리즘 공부를 꽤나 해놨던 터라 이미 풀었던 문제가 많았다. 덕분에 첫 날에 반 정도의 문제를 풀고, 다음 날 끝까지 문제를 해결할 수 있었다.

 

 이번주에 공부했던 내용들 중 가장 인상깊었던 것은 백트래킹이었다. 백트래킹 대표 문제인 N-Queen 문제를 최근에 풀었었는데, 당시에는 백트래킹에 대한 감이 잘 잡히지 않았지만 이번에 같은 문제를 다시 풀고 유사한 문제들을 풀면서 감을 잡을 수 있었다. 이번에 공부했던 백트래킹에 대해 정리해보겠다.

---

백트래킹(Backtracking)

경우의 수 따지는 문제를 푸는 방법

 알고리즘 문제들 중에는 특정 조건을 만족하는 경우의 수가 몇 개인지 묻거나 최적의 답이 무엇인지 묻는 문제들이 많다. 이런 문제를 푸는 방법은 여러가지가 있다.

1. 모든 경우를 따져본다.(Brute Force)
2. 경우를 따지는 방법을 단계적으로 나눠 매 단계마다 조건을 만족하는지 평가해 만족하지 않으면 그 다음 단계로 넘어가지 않고 해당 가지를 버리고 돌아간다.(Backtracking)
3. 반복되는 부분 구조를 찾고 계산한 내용을 저장해 이후 부분구조 반복 시 저장했던 내용을 다시 꺼내어 활용해 계산량을 줄인다.(Dynamic Programming)

 위 세 가지 방법들은 잠단점이 있으며, 일반적으로 브루트 포스 > 백트래킹 > 다이나믹 프로그래밍 순으로 알고리즘의 시간복잡도가 낮아지지만 모든 문제에 세 알고리즘을 적용할 수 있는 것은 아니다. 브루트포스로만 풀 수 있는 문제가 있고, 백트래킹으로 풀면 더 효율적이거나 다이나믹 프로그래밍을 사용하면 더 효율적인 문제들이 있을 뿐이다. 세 가지 알고리즘을 모두 활용할 수 있는 대표적인 문제는 이번주 문제 목록에도 있었던 TSP(외판원 순회) 문제이다.

 

어떤 문제가 백트래킹 문제일까?

 알고리즘 문제를 빨리 풀기 위해서는 그 문제를 봤을 때 어떤 방법을 통해 풀어야할지 빠르게 감을 잡는 게 중요하다. 나는 아래와 같은 특징이 있으면 백트래킹 유형이라 생각한다.

1. 숫자의 범위가 좁아 경우의 수가 적은 편이다. 하지만 브루트포스로 풀기엔 많다.
2. 문제를 단계적으로 나눌 수 있는 구조이다.
3. 문제의 조건을 매 단계마다 평가할 수 있는 구조이다.(조건을 만족하지 않는 경우, 그 가지를 버려 경우의 수를 줄일 수 있는 문제이다.)

백트래킹 코드 짜기

Backtracking 이해를 돕기 위한 이미지

 문제에서 가능한 모든 경우의 수가 뻗어나가는 모양을 트리와 같은 모양으로 생각하면 경우의 수를 따지는 백트래킹 문제를 그래프 문제라 생각할 수 있다. 그래프(경우의 수)를 탐색하는 대표 알고리즘인 BFS(Breadth First Search)와 DFS(Depth First Search) 중 DFS가 각 경우의 수 가지의 조건을 기억하고 되돌리기 좋고, 재귀를 활용하면 코드 구현이 간단하고 직관적이며, 메모리를 적게 사용한다는 점에서 백트래킹과 궁합이 좋다.

 

 DFS로 구현한 백트래킹 함수는 보통 다음과 같은 특징이 있다.(절차 순)

1. 현재 상태를 저장하는 변수 : 보통 함수의 외부에 선언되어 있으며, 조건을 확인할 때 활용한다.
2. 파라미터 : 함수의 파라미터로 현재 자신이 몇 단계에 있는지 받는다.
3. 반복문 : 해당 단계에서 확인해야 하는 경우의 수를 반복문을 통해 확인한다.
4. 조건문 : 확인하려는 경우의 수가 특정 조건을 만족하는지 확인한다.
5. 상태 업데이트 : 조건을 만족하는 경우, 다음 단계로 넘어가며 변경된 상태를 업데이트 해준다.
6. 재귀 : 조건을 업데이트한 상태에서 그 다음 단계로 넘어가는 함수를 호출한다.
7. 상태 되돌리기 : 재귀함수가 끝난 후 원래 상태로 되돌려준다.(다른 경우의 수를 따질 때 지장이 없도록)

 다만 백트래킹을 구현한 모든 코드가 위 구조를 갖고 있는 것은 아니며, 몇몇 특징들이 빠진 경우도 많다.

 위 구조를 활용한 코드 예시는 아래와 같다. 상단에 백준 문제 번호와 제목이 적혀 있다.

 

# 9663 N-Queen
N = int(input())
cnt = [0]
row_info, plus_info, minus_info = [1]*N, [1]*(2*N-1), [1]*(2*N-1)

def queen(col=0):
    if col == N:
        cnt[0] += 1
        return
    for row in range(N):
        if row_info[row] and plus_info[row+col] and minus_info[row-col]:
            row_info[row], plus_info[row+col], minus_info[row-col] = 0, 0 ,0
            queen(col + 1)
            row_info[row], plus_info[row+col], minus_info[row-col] = 1, 1, 1
queen()
print(cnt[0])

---

# 10971 외판원 순회 2
import sys
input = sys.stdin.readline

N = int(input())
to_root_info = []
adj_list = [[] for _ in range(N)]
for i in range(N):
    for j in enumerate(map(int, input().split())):
        if j[0] == 0: # 각 노드에서 root가는 정보를 저장하기 위해
            to_root_info.append(j[1])
        if j[1]: # 비용이 1 이상
            adj_list[i].append(j)

root = 0
visited = [0]*N
visited[root] = 1
mini = [10**8]

def tsp(now_city=root, n=1, total_cost=0):
    """now_city : 현재 방문한 도시 / n:현재 방문한 도시 수"""
    if n == N and to_root_info[now_city]: # 모든 도시를 방문했고 root로 가는 길이 있다면
        total_cost += to_root_info[now_city]
        if mini[0] > total_cost:
            mini[0] = total_cost
            return
    for adj_city, cost in adj_list[now_city]:
        if not visited[adj_city]:
            visited[adj_city] = 1 # 이 세 줄이 백트래킹 핵심
            tsp(adj_city, n+1, total_cost + cost)
            visited[adj_city] = 0

tsp()
print(mini[0])

---

# 14888 연산자 끼워넣기
N = int(input())
A = list(map(int, input().split()))
oper_cnt = list(map(int, input().split()))

def plus(a, b): return a + b
def minus(a, b): return a - b
def mult(a, b): return a * b
def divide(a, b): return -(-a//b) if a<0 else a//b

oper_list = [plus, minus, mult, divide]
mini, maxi = [10**11], [-10**11]

def back_tracking(i=1, res=A[0]):
    if i == N:
        if res > maxi[0]:
            maxi[0] = res
        if res < mini[0]:
            mini[0] = res
        return
    for j in range(4):
        if oper_cnt[j]:
            oper_cnt[j] -= 1
            back_tracking(i+1, oper_list[j](res, A[i]))
            oper_cnt[j] += 1
back_tracking()
print(maxi[0], mini[0])

---

# 1182 부분수열의 합
N, S = map(int, input().split())
A = tuple(map(int, input().split()))

ans = [0]
def solve(i=0, s=0):
    if i == N:
        if s == S:
            ans[0] += 1
        return
    solve(i+1, s+A[i])
    solve(i+1, s)
solve()
print(ans[0]) if S else print(ans[0]-1)

---

# 9095 1, 2, 3 더하기
T = int(input())

for _ in range(T):
    n = int(input())
    
    def solve(remain=n):
        if remain < 0:
            return 0
        if remain == 0:
            return 1
        
        return solve(remain-1) + solve(remain-2) + solve(remain-3)

    print(solve())

 

---

목요일 Week01 시험

 목요일엔 오전엔 Week01 시험을 봤다. 잘 보고 싶은 마음에 시험 시작할 때 좀 긴장했는데, 다행히 여유 있게 세 문제를 모두 풀 수 있었다. 그 중 백트래킹 유형이 두 문제(백준 1182, 9095) 나왔는데 모두 빠르게 풀어냈다. 헤헤 담주도 화이티잉~