SW사관학교 정글

[SW 정글] WEEK04 개발일지(DP & Greedy)

SalmonSushi 2022. 5. 1. 18:07

* 스스로 공부한 저의 생각을 적은 것입니다. 틀린 부분이 있다면 댓글로 알려주시면 감사하겠습니다.

 

 week04 DP & Greedy가 끝났다. 이로써 알고리즘 주차가 끝났는데, 정말 순식간이었다. 그래도 알고리즘 주차를 보면서 한 달 동안 알고리즘에만 집중했으니 꽤 성장할 수 있었던 것 같다.

 

Week04 알고리즘 주제 : 동적 프로그래밍, 그리디 알고리즘

 이번 주 공부 주제는 DP(Dynamic Programming)와 Greedy였다. 보통 알고리즘의 끝에 배우는 끝판왕 같은 느낌.. 그리디 문제는 나동빈님의 추천에 따라 혼자 알고리즘 문제를 풀 때 꽤나 많이 풀어서 조금 자신 있었지만 어려운 문제를 만났을 때 감이 잘 안 잡히는 문제들이 많았고, DP는 문제를 많이 풀어보지 못해 이번 기회를 통해 DP의 중요 특징을 익히고 싶었다.

 이번주 포스팅은 어떤 문제가 DP, 그리디이며 어떻게 접근해야 하는지에 대해, 그리고 가장 흥미롭게 풀었던 DP를 활용한 '외판원 순회(백준 2098)'에 대해 적도록 하겠다.

 

DP(Dynamic Programming)와 Greedy

 이번주 알고리즘 주제였던 DP와 Greedy. 두 알고리즘은 뭘까?

 

DP와 Greedy. 왜 항상 함께 배우나?

 둘이 함께 다니는 이유가 있다. 둘 다 최적부분구조(Optimal Substructure)를 갖고 있는 문제에 대해 사용하기 때문이다. 내 경험상 최적 부분 구조를 가진 문제는, 문제에서 요구한 케이스를 손으로 적어나가다보면 (마치 프랙탈처럼) 문제 안에 똑같은 작은 문제가 있는 구조가 나타난다. 그렇기 때문에 '현재의 상태'를 해결한 '다음 상태'를 만들다보면 최종 답에 도달하게 된다.

 

<Greedy>

 여기서 DP로 푸는 문제와 그리디로 푸는 문제의 차이는 앞에서 말한 '해결한다'라는 방법의 차이에서 나타나는데, 그리디 문제의 경우 감사하게도 '현재 상태'에서 '다음 상태'로 넘어갈 때 그 순간 최고의 선택을 하고 그것을 반복하다보면 전체 문제의 답을 구할 수 있게 된다. 이렇게 풀리는 문제는 탐욕 선택 속성(greedy choice property)이 있다고 한다. 그리디 문제는 탐욕 선택 속성 덕분에 확인해야 하는 경우의 수가 현저히 줄어들게 된다.

 

<DP>

 반면, DP로 푸는 문제의 경우에는 탐욕 선택 속성이 없다. 그럼 모든 경우의 수를 다 확인해봐야 하는 것이냐? 그렇지 않다.(그런 문제는 Brute Force 알고리즘으로 해결하며, DP 문제보다 전체 경우의 수가 훨씬 적다.) DP문제가 갖고 있는 또 다른 중요한 특성은 중복된 계산이 발생한다는 점이다.(중복된 하위 문제가 있다고 한다.) 그러니까, '현재의 상태'를 해결하고 '다음 상태'로 넘어갔는데, "어.. 이거 했던 건데..?"하는 상황이 발생하는 것이다. 그렇기 때문에 이미 계산했던 것을 (보통 dp_table이라 부르는 곳에) 저장해 이미 확인했던 경우가 다시 나타난 경우 계산했던 결과를 꺼내 다시 사용하게 된다. DP문제는 이런 식으로 확인하는 계산량을 줄이게 된다.

 

 이렇게 쉽게 말했지만 Greedy, DP는 어려운 문제가 많다. 최적부분구조를 찾고 명확하게 문제를 쪼개는 것, 그리디의 경우 문제가 탐욕 선택 속성이 있는지 알아차리는 것과 최적의 선택을 하는 것, DP의 경우 현재 상태를 나타내는 파라미터를 명확히 하는 것과 점화식을 찾는 것이 어렵기 때문이다. 개인적으로 두 문제 모두 손으로 경우의 수를 직접 써보고 그 안에서 반복된 규칙이나 탐욕속성을 찾는 것이 많은 도움이 된다.

 

어떤 문제를 DP로 해결하는가?

- Bruteforce나 Backtracking으로 풀기엔 경우의 수가 매우 많다

- 경우의 수를 손으로 적다보면 똑같은 작은 문제가 반복된다.(최적 부분 구조) -> 따라서 현재의 상태를 몇 개의 파라미터로 표현할 수 있다.

- 중복된 계산이 발생하며, 이를 위에서 구한 파라미터를 활용해 dp table에 저장할 수 있다.

 

어떤 문제를 Greedy로 해결하는가?

- Bruteforce나 Backtracking으로 풀기엔 경우의 수가 매우 많다.

- 경우의 수를 손으로 적다보면 똑같은 작은 문제가 반복된다.(최적 부분 구조)

- 매 순간 최선의 선택을 한 것이 전체의 최선의 결과를 보장한다.(탐욕 선택 속성)

 

 이렇게 DP와 Greedy에 대한 내 생각을 적어보았는데, 이제부터 이번 주에 풀었던 문제들 중 가장 흥미롭게 풀었던 DP문제인 '2098 외판원 순회'문제에 대해 적어보겠다. 위에서 적은 DP문제의 특성과 접근방법을 고려하면서 읽으면 도움이 될 것이다.

 

[백준] 2098 외판원 순회 - Dynamic Programming

 외판원 순회(Traveling Salesman Problem) 문제는 이전에 알고리즘 1주 차 때 풀었던 '10971 외판원 순회 2'와 같은 문제다. 다만, 방문하는 도시 수의 범위가 10 이하에서 고작 16 이하로 늘어났을 뿐인데 난이도 차이가 엄청나다. 이전의 문제는 백트래킹으로 풀 수 있었지만, 이번 문제는 그렇게 해서는 방문하는 도시의 경우의 수가 미친 듯이 늘어나기 때문에 좀 더 효율적으로 풀어야 한다. 외판원 문제(Traveling Salesman Problem)는 컴퓨터과학에서 매우 중요하고 어려운 문제라고 하는데, DP를 이용해 좀 더 효율적으로 풀 수 있다는 것이 알려져 있다.

 

어떻게 하면 경우의 수를 줄일 수 있을까?

 1, 2, 3, 4, 5, 6 여섯 개의 도시가 있다고 쳐보자. 1번 도시에서 출발해 모든 도시를 거쳐 다시 1번 도시로 돌아오는 경우를 생각해보자. 이때 1-2-3-4, 1-3-2-4 순으로 도시를 방문한 경우, 경우는 두 가지지만 두 경우 모두 4번 도시에서 출발해 {5, 6} 도시를 거쳐 1번 도시로 돌아와야 한다는 것은 같다. 즉, 반복되는 계산이 발생한다. 그럼 해당 경우를 저장해 같은 경우가 또 발생한다면 저장했던 정보를 활용(Dynamic Programing)할 수 있을 것이다. 이것이 외판원 순회 DP풀이의 핵심 아이디어다. 여기서 방금 전의 상황은 {1, 2, 3, 4} 도시를 방문하고 {5, 6} 도시를 방문하지 않은 상태(status)에서 현재 위치해 있는 4번 도시(now_node)에서 1번 도시로 돌아와야 하는 상황이었다. 즉, 지금의 상태는 지금까지의 방문 상태와 현재 위치 두 가지를 가지고 현재의 상황을 표현할 수 있는 것이다. 그럼 우리에게 now_node와 status를 파라미터로 가지는 다음과 같은 함수가 있다면 어떨까?

 

tsp라는 함수는 방문 상태가 status일 때 now_node에서 출발해 1번 도시로 돌아오는 최소 비용을 리턴해준다.

 

 tsp함수는 현재 상태에서 1번 도시로 돌아가기 위한 최소비용을 리턴해주기 때문에 현재 도시(now_node)에서 갈 수 있는 인접 도시들(adj_node)까지 가는 비용을 고려하면 tsp(now_node, status)와 tsp(adj_node, new_status) 사이에 점화식을 세울 수 있고, 이를 이용해 귀납적으로 답을 구할 수 있게 된다. 좋다, 이제 구현만 하면 된다.

 

그래서 어떻게 구현하는데?

 그러나 문제가 있다. status를 어떻게 표현할 것인가? 일반적으로 그래프 문제에서 status라는 것은 visited라는 리스트를 만들어 노드들의 방문 상태를 표현해주기 때문에 익숙하긴 하다. 만약 위의 {1, 2, 3, 4}도시를 방문하고 {5, 6}도시를 방문하지 않은 상태라면 [1, 1, 1, 1, 0, 0]과 같이 표현하는 것이다. 그러나 방문해야 할 도시가 16개이고, 방문 상태의 경우의 수가 2^16 = 65536가지이기 때문에 리스트나 튜플로 구현하는 것은 오버헤드가 너무 크기도 하고 dp table에 방문상태를 저장하는 것 또한 문제이다. 이때 이 문제를 해결하기 위해 등장하는 것이 비트 마스킹이다.

 

비트 마스킹

 비트 마스킹은 이번에 외판원 순회 문제를 풀면서 처음 사용했기 때문에 이제야 공부하게 되었는데, 이름이 무서워서(?) 좀 거부감이 있었지만 방법을 이해하고 나니 생각보다 별거 없으면서도 방법이 기가 막히다는 생각이 들었다. 아이디어는 간단하다.

 

{1, 2, 3, 4}를 방문하고 {5, 6}을 방문하지 않은 상태를 [1, 1, 1, 1, 0, 0]으로 표현하던 것을

111100과 같이 이진법으로 표현하는 것

 

이다. 이렇게 하면 자료구조를 생성하고 없애는 오버해드가 사라지고, 2^16=65536가지의 방문 상태(status)가 단지 0~65535의 숫자로 변환되기 때문에 dp table을 만들고 status 변수를 함수에 전달하는 것도 간단해진다. status를 가지고 노드의 방문 여부를 확인하고 방문 상태를 업데이트하는 것은 이진법에 익숙하다면 어렵지 않다. 비트 연산자(|, &, ~, <<, >> 등)를 잘 활용하면 쉽게 구현할 수 있다.

 

 이제 모두 구현할 수 있겠다. 구현한 코드는 아래와 같다.

# 2098 외판원 순회
import sys
input = sys.stdin.readline
N = int(input())
adj_matrix = [tuple(map(int, input().split())) for _ in range(N)]
adj_list = [[] for _ in range(N)]
for a, row in enumerate(adj_matrix):
    for b, cost in enumerate(row):
        if cost != 0: # 갈 수 있는 경우만
            adj_list[a].append((b, cost))

# 방문상태를 표시해주는 binary 값인 status는 오른쪽부터 1번 노드로 친다.
def visited(node, status):
    """방문상태가 status일 때 node의 방문여부 리턴"""
    return (status >> node)%2

def visit(node, status):
    """방문상태가 status일 때 node를 방문한 처리한 new_status 리턴"""
    return status + (0b1<<node)

start = 0 # 비트마스킹 때문에 0으로 고정해야 함
dp = [[float('inf')]*2**N for _ in range(N)] # 아래 tsp 함수의 정보 저장
all_visited = 2**N - 1
def tsp(now_node=start, status=visit(start,0)):
    """방문상태가 status일 때 now_node에서 출발해 start로 돌아오는 최소 비용 리턴"""
    if dp[now_node][status] == float('inf'):
        if status == all_visited: # 전부 다 돈 경우
            if adj_matrix[now_node][start]: # start로 가는 길이 있으면
                dp[now_node][status] = adj_matrix[now_node][start]
            else:
                dp[now_node][status] = 10**8 # 길 없다고 표시
        else:
            candi_costs = [10**8]
            for adj_node, adj_cost in adj_list[now_node]:
                if adj_node != start and not visited(adj_node, status):
                    new_status = visit(adj_node, status)
                    new_cost = adj_cost + tsp(adj_node, new_status)
                    candi_costs.append(new_cost)
            dp[now_node][status] = min(candi_costs)
    return dp[now_node][status]

print(tsp())

 

4주간의 컴퓨팅 사고로의 전환을 마치며

 4주가 순식간에 지났다. 원래 알고리즘 문제를 꾸준히 풀어왔어서 문제를 푸는 것이 익숙하긴 했지만 이렇게 긴 시간을 알고리즘만 몰입해서 공부한 것은 처음이었다. 그러다 보니 확실히 혼자 할 때보다 알고리즘 실력도 많이 오른 것 같은데, 앞으로도 이 감을 잃지 않고 조금씩 성장하기 위해 매일 알고리즘 문제를 풀 계획이다. 다행히 매일 함께 알고리즘 문제를 한 문제씩 푸는 스터디를 하게 되어 좀 더 즐겁게 실력을 높일 수 있을 것 같다. 앞으로 공부하게 될 C언어와 OS 공부가 걱정되기 하지만 열심히 하다 보면 잘할 수 있겠지?ㅎㅎ 앞으로도 화이팅!