Tree DP, Bitmasking DP (동적계획법 심화)

 

1. Tree DP

Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나)

        => 그래프처럼 DP 기법 적용 가능

 

트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다.

트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적.

   => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함.

 

기본적으로 Top-down 방식으로 코드 작성.

   => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식.

 

 

 

Tree DP 예제

<백준 15681 - 트리와 쿼리> https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

 

 

예를 들면, 6번 노드를 루트로 탐색을 진행할 때 그림에서 node[6] 에는 5, 7, 9, 8이 연결되어 있지만 코드 흐름상 6과 연결된 5번 노드는 이미 방문한 적이 있기 때문에 부모 노드인 5번으로는 가지 않고 방문하지 않은 자식 노드들(7, 8, 9)만 count한다.

 

또한 3을 루트로 하는 서브트리는 하위 노드이자 leaf node인 1로 간 뒤 1에 연결된 다음 노드가 없으므로 반환되고, dp[3]에는 dp[3] + dp[1] = 2 값이 저장된다. 그 뒤에 또 다른 하위 노드인 2에 간 뒤, 2에 연결된 다음 노드가 없으므로 반환되고 dp[3]에는 결과적으로 dp[3] + dp[2] = 3 값이 저장된다.

 

 

 

 

2. Bitmasking DP

Bitmasking : 정수의 이진수 표현을 활용한 기법

 

Bit 연산

• AND 연산 (&) : 1010 & 1111 = 1010
• OR 연산 (|)     : 1010 | 1111 = 1111
• XOR 연산 (^)  : 1010 ^ 1111 = 0101
• NOT 연산 (~)  : ~1010 = 0101
• SHIFT 연산(<<, >>) : 001010 << 2 = 101000, 001010 >> 2 = 000010

 

Bit 연산을 이용한 기능

• 특정 비트를 0으로 만든다 (reset) : 1110 & ~(1<<2) // 2번 비트만 0으로 만든다. => 1110 & 1011 = 1010
• 특정 비트를 1로 만든다 (set) : 1000 | 1<<1 // 1번 비트만 0으로 만든다. => 1000 | 0010 = 1010
• 특정 비트를 반전시킨다 (toggle) : 1110 ^ (1<<2) // 2번 비트를 반전시킨다. => 1110 ^ 0100 = 1010
• 특정 비트의 값을 검사한다 : 1010 & (1<<2) => 1010 & 0100 = 0, 1010 & (1<<3) => 1010 & 1000 = 1000                                             (=> i번째 비트값이 0이라면 결과값이 0)

 

• Bitmasking DP 활용 방법

Bitmasking은 보통 제한이 굉장히 작게 걸려 있고, 모든 경우를 다 표현하고 싶을 때 사용한다.

Bit를 사용하기 때문에 지수 스케일로 증가한다. (선형 복잡도 나올 수 x. linear하게 나오지 않고 exponential로 증가하기 때문에 제한이 작게 걸려있는 문제에서만 사용 가능).

어떠한 한 원소에 대해 Yes/No인 상황만 표현할 수 있다.

 

 

 

Bitmasking DP 예제

<백준 2098 - 외판원 순회> https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

 

 

 

 

출처 : https://jenndph.tistory.com/2