○이어지는 글
https://kuck-su-labor.tistory.com/50
○들어가는 글
저번 시간에는 간단히 재귀적으로 트리 알고리즘을 구성하는 방법에 대해서 알아보았습니다. 들어가기 전에 요약한다면 재귀 함수 내에서 자기 자신을 N 번 호출함으로써, 각 노드에서 N개로 뻗어 나가는 트리를 만들 수 있다고 했습니다. 그리고 저번 시간에는 노드에서 2가지로 뻗어 나가는 이진트리를 예로 들어서 설명해 드렸습니다.
○트리의 활용 (완전탐색 - 브루트포스)
그렇다면 트리를 이용해서 무엇을 할 수 있을까요? 저번 글에서 마지막으로 다루었던 그림입니다. 임의의 변수 N이 있을 때 한쪽은 N을 1 증가시키고, 다른 한쪽은 아무것도 하지 않는 트리를 간단하게 그려보았습니다.
이렇게 되면 마지막 부분에서 N을 증감시켰을 때와 그렇지 않았을 때의 모든 경우의 결과를 확인 할 수 있습니다. 이렇듯 트리에서 노드의 마지막 즉 리프(Leaf) 부분을 얻음으로써, 경우의 수를 얻는 것이 가능합니다. 보통 이러한 것을 완전 탐색 (브루트 포스)라고 합니다.
이러한 완전탐색의 가장 큰 문제는 바로 시간입니다. 흔히 시간복잡도라고 하지요
이러한 완전 탐색의 가장 큰 문제는 바로 시간입니다. 흔히 시간복잡도라고 하지요. 이렇게 재귀로 이루어진 이진 트리의 경우에는 시간복잡도가 O(n^2) 정도입니다. 어느 정도인지 잘 가늠이 되지 않을 수 있지만, 확실한 것은 데이터가 커지면 커질수록 비효율적이라는 것입니다.
위의 예시에서만 보아도 깊이가 3일 때는 우리가 그릴 수 있을 정도로 간단하지만, 만약 깊이가 100, 1000 정도만 되어도 알고리즘의 효율을 점점 낮아집니다. 따라서 (경우의 따라서) 좀 더 효율적인 알고리즘을 사용할 수 있다면 사용합시다.
○트리의 활용 (knapsack 문제)
knapsack 문제는 각 W의 무게와 가치 V를 가지는 물건들이 존재한다고 할 때, 한정된 K의 무게를 담을 수 있는 가방에 최대의 가치의 합이 되도록 담는 방법을 구하는 방법입니다.
가장 쉽게 푸는 방법은 바로 완전 탐색을 이용하는 방법입니다. 위에서 설명했듯이 완전 탐색은 모든 경우의 수를 구할 수 있습니다. 따라서 우리는 이러한 경우의 수 중에 가장 가치가 큰 것을 고르면 그만입니다.
그림으로 표현하면 다음과 같겠죠.
○ 더 나아가서
다만 이는 좋은 방법은 아닙니다. 아까도 말했듯이 이를 구하는 비용이 효율적이지 않기 때문입니다. 따라서 보통 이러한 문제를 해결하는 데 있어서 DP 알고리즘을 사용합니다.
바로 DP 알고리즘의 대해서 진행해도 되겠지만, 그렇기에는 아직 좀 더 다룰 수 있는 내용이 있습니다. 우리는 아까 완전 탐색을 이용해서 만든 알고리즘을 greedy 알고리즘을 통해 개선하고, 이를 통해 비용을 좀 더 효율적으로 개선할 방법을 우선 다뤄보려고 합니다.
따라서 우리는 먼저 greedy 알고리즘에 대해서 다루고, 그다음 이어가도록 하겠습니다. 다음 글에서 뵙겠습니다. 감사합니다.
'알고리즘 5+1' 카테고리의 다른 글
| 탐욕 알고리즘(2) - (greedy 알고리즘 활용 - 강의실 배정문제 ) (0) | 2021.04.21 |
|---|---|
| 탐욕 알고리즘(1 - greedy 알고리즘 소개) (0) | 2021.04.15 |
| 트리 알고리즘 (4- 트리의 순회방법 (정리편)) (0) | 2021.04.07 |
| 트리 알고리즘 (3 - 트리의 순회방법 (개념편)) (0) | 2021.03.23 |
| 트리 알고리즘 (1 - 개요) (0) | 2021.03.10 |