DFS 시간 복잡도

지금까지는 DFS의 시간복잡도를 따로 계산하지 않고 사용해왔는데 프로그래머스 문제를 풀다가 DFS알고리즘이 생각보다 시간복잡도가 낮다는 것을 깨달았고 이를 계기로 한번쯤은 정리할 필요성을 느껴 포스팅한다.

 

DFS알고리즘은 일반적으로 가상의 n진트리를 만들어 재귀함수로 구현한다. 

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

위 문제의 경우 한번 광물을 캘 때 세개의 곡괭이 중 하나를 선택할 수 있다. 세 곡괭이는 최대 5개씩 주어지며 한번의 곡괭이질로 광물 5개를 캘 수 있을 때 최대 광물의 개수는 50개이므로 최악의 경우 15개의 곡괭이로 50개의 광물을 캘 때의 최소 피로도를 구하면 된다.

 

이를 DFS로 구현해보자. 매 depth에서 3개 중 하나를 골라야 하므로 3진트리를 그려볼 수 있겠다. 그리고 매 depth마다 광물 5개를 채굴하기에 최대 depth는 10이 되겠다.

 

이 문제를 처음 접했을 땐 곡괭이 15개 중 10개를 고르는 순열이라고 생각해 15P10을 구해보았고 100억이 넘는 결과가 나왔기에 DFS로는 풀 수 없다고 판단했다. 그래서 다음과 같은 시나리오를 세웠다.

 

1. 광물개수에 따라 필요한 곡괭이의 개수를 구하고, 다이아 곡괭이부터 순회하며 사용하는데 필요한 곡괭이의 최소 개수를 구했다.

예를 들어서 광물이 8개이고 곡괭이가 각각 1,3,1개라면 다이아 곡괭이 하나, 철 곡괭이 하나만 사용해서 문제를 해결할 수 있기 때문에 사용할 곡괭이 배열에 다이아1, 철1을 추가한다.

 

2. 구한 곡괭이 개수로 순열을 구한다.

이 때 나올 수 있는 최대 경우의 수는 10! = 3,628,800 이므로 구한 순열을 이용해 완전탐색한다.

 

이를 통해 문제를 해결할 수 있었다.

 

하지만 n진트리를 만들어 dfs로도 풀어보았고 위 풀이 대비 30배 정도 성능 향상 시킬 수 있었다. 그리고 dfs풀이를 최적화했을 때는 첫번째 풀이보다 380배 정도 성능이 좋았다.

 

분명 시간초과 날 것으로 예상했는데 어찌된 일일까?

 

내가 계산한 시간복잡도가 틀렸을 것이라 생각해 chatGPT한테 n진트리 탐색의 시간복잡도를 물어보았다.

위 답변을 기반으로 이번 문제의 시간복잡도를 계산해봤을 때 O(3&10) = 59,049가 나온다. 

결과를 믿기 힘들어 구체적으로 조건을 주고 다시 물어본 결과도 동일했다. 

 

이를 근거로 n진 트리를 이용한 dfs의 시간복잡도는 깊이가 d일 때, O(n^d)인 것을 알 수 있었다.

그렇기 때문에 DFS로 푼 풀이가 비교할 수 없을 정도로 성능이 좋았던 것이다.