DP vs DFS??

Dynamic Programming (DP)와 Depth-First Search (DFS)의 차이점은 무엇일까요?

문득 문제를 풀다보니, DP(동적프로그래밍)과 DFS(깊이우선탐색)이 뭐가 다른지 궁금해져서 조사해보면서 정리를 해보았다.

우선 각자의 개념부터 먼저 알아보겠다.

DP(Dynamic Programming)란?

DP는 큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘입니다. 이전 하위 문제의 결과를 저장하고 재사용함으로써 중복 계산을 피하고 효율적으로 문제를 해결합니다. DP는 보통 최적화 문제 또는 결정 문제를 해결하는 데 사용됩니다.

DP를 설명하기 위해 예시 문제를 살펴보겠습니다. 계단을 오르는 방법의 수를 구하는 문제입니다. 계단은 한 번에 한 칸 또는 두 칸씩 오를 수 있습니다. 예를 들어, 5 개의 계단을 오르는 방법의 수는 다음과 같이 구할 수 있습니다.

• 첫 번째 계단을 오르는 방법은 1가지입니다. (한 칸씩 오르기)
• 두 번째 계단을 오르는 방법은 2가지입니다. (한 칸씩 오르기 or 두 칸씩 오르기)
• 세 번째 계단을 오르는 방법은 3가지입니다. (한 칸씩 오르기 or 두 칸씩 오르기 or 1 -> 2칸)
• 네 번째 계단을 오르는 방법은 5가지입니다. (한 칸씩 오르기 or 두 칸씩 오르기 or 1 -> 2 -> 1 or 2 -> 1 -> 1 or 1 -> 1 -> 2)
• 다섯 번째 계단을 오르는 방법은 8가지입니다. (한 칸씩 오르기 or 두 칸씩 오르기 or 1 -> 2 -> 2 or 2 -> 1 -> 2 or 2 -> 2 -> 1 or 1 -> 1 -> 1 -> 2 or 1 -> 1 -> 2 -> 1 or 1 -> 2 -> 1 -> 1 or 2 -> 1 -> 1 -> 1)

DP를 사용하여 이 문제를 풀면, 계단을 오르는 방법의 수를 저장할 배열을 만들고, 이전 계단을 오르는 방법의 수를 이용하여 현재 계단을 오르는 방법의 수를 계산하는 방식으로 문제를 해결할 수 있습니다.

DP에 대해 정리한 블로그: 동적 계획법(Dynamic Programing)

DFS란?

DFS는 그래프를 탐색하는 데 사용되는 알고리즘입니다. 그래프의 깊은 부분을 우선적으로 탐색하기 때문에 깊이 우선 탐색이라고도 합니다. DFS는 주로 그래프에서 경로를 찾거나, 순환을 감지하거나, 그래프의 구조를 분석하는 데 사용됩니다.

DFS는 스택이나 재귀 함수를 사용하여 구현됩니다. 그래프를 탐색할 때, 노드를 방문하면서 이전에 방문하지 않은 인접한 노드를 스택에 넣어 탐색을 계속합니다. 스택에서 노드를 꺼내 방문하면서, 이전에 방문하지 않은 인접한 노드를 스택에 넣습니다. 이를 반복하여 그래프를 탐색합니다.

DFS에 대해 정리한 블로그: DFS vs BFS

DP와 DFS의 차이점

• DP는 문제의 최적 해를 구하기 위해 사용됩니다.
  반면에, DFS는 그래프의 탐색을 위해 사용됩니다.
• DP는 문제를 작은 하위 문제로 분할하여 해결합니다.
  반면에, DFS는 그래프의 깊은 부분을 우선적으로 탐색합니다.
• DP는 이전 하위 문제의 결과를 저장하고 재사용함으로써 중복 계산을 피합니다.
  반면에, DFS는 그래프의 구조를 분석하기 위해 스택이나 재귀 함수를 사용합니다.

따라서, DP와 DFS는 서로 다른 유형의 알고리즘이며, 각각 다른 종류의 문제를 해결하기 위해 사용됩니다. DP는 보통 최적화 문제나 결정 문제를 해결하는 데 사용되고, DFS는 그래프에서 경로를 찾거나 순환이 있는지 검사하는 데 주로 사용됩니다.

정리

DFS는 데이터의 개수가 조금만 커져도 시간초과가 날 확률이 높은 방법이다. 왜냐하면 50x50칸의 2차원 배열이 있을때 0,0에서 50,50으로 가는 경우의 수를 찾을때 dfs를 사용해야 하고, 상하좌우 네방향으로 이동 가능하다고 했을 때 4의(50x50)승이라는 어마어마한 연산의 횟수가 발생한다.

그렇기에 반복적으로 계산하는 것을 피해서 처리해야하는데, 그 방법이 DP(동적계획법)이다. 즉 DFS로 풀긴 푸는데, 예전에 구해왔던 값이 있으면 반복계산하지 않고, 예전에 썻던 값을 기억했다가 다시 쓰겠다는 의미이다.

예를 들어 0,0에서 1,1을 거쳐 50,50으로 가는 경로가 있다고 하자 (50x50 2차원 배열을 떠올리자)

1. 0,0에서 오른쪽->아래 순서로 1,1으로 간 후 50,50으로 가는 경로가 생길수있고,

2. 0,0에서 아래->오른쪽 순서로 1,1에 간 후 50,50으로 가는 경로가 생길수있다. 첫번째 경우에서 DP[1][1] = (1,1에서 50,50으로 가는 경로수)를 기록해 놓으면, 2번째 경우에서 1,1에 왔을때 이미 DP에 계산된 결과를 메모해놓았으므로 또다시 계산할 필요 없이 그 값을 그대로 쓰면 된다. 어차피 1,1에 온 이상 1,1 까지 어떻게 왔던지 간에 50,50까지 가는 경로는 똑같을 것이기 때문이다. 이렇게 해주게 되면 중복된 계산을 피할 수 있게 되며 딱 필요한 만큼의 계산만 하게 되므로 연산 횟수가 매우매우 크게 줄어들게 된다.

그래서 DFS를 데이터가 큰 경우에도 사용할수 있게 된다.