○이어지는 글
○들어가는 글
저번 시간에는 우리가 트리의 순회 방법의 대해서 간단히 개념만을 알아보았습니다. 이번 시간에는 이러한 개념에 대해서 실습해보는 시간을 가지려고 합니다.
○트리의 구현
이전 글에서 있던 트리입니다. 한쪽으로는 노드의 값을 1 증가시키고, 다른 쪽은 증감 없이 진행하는 트리를 만들었습니다. 이러한 완전 탐색 트리는 특정 로직으로 모든 경우의 수를 탐색하였을 때의 경우의 수를 모두 얻을 수 있다고 이야기 드렸습니다.
그리고 이를 간단히 재귀로 구현을 한다면 다음과 같은 것입니다.
결과를 보면 우리가 처음에 그렸던 그림과 같이 순서대로 리프(트리의 마지막) 부분의 값들이 출력되는 것을 알 수 있습니다. 이처럼 재귀를 통해서 완전 탐색을 구현할 수 있는 것입니다.
○트리 노드의 순회
위의 경우 우리는 완전 탐색을 한 것이고, 이는 트리의 마지막 노드, 즉 리프 노드만을 취한 결과입니다. 이러한 값들을 우리는 구했지만, 중간의 노드들의 값이 제대로 취해졌는지는 우리가 직접 보기 전까지는 모르는 법입니다.
이럴 때는 순회를 하는 방법이 있습니다. 모든 노드를 순회하고 출력하도록 로직을 짠다면 해결되는 문제입니다. 이는 재귀 함수에 출력문을 쓰는 것만으로도 충분하겠죠. 우선 예시는 다음과 같습니다.
출력되었습니다. 다만 문제는 순서입니다. 값들은 제대로 나왔지만, 이것들이 제 자리를 가지는지는 아직 명확하게는 모르겠습니다.
하지만 출력 결과와 그림을 본다면 뭔가 규칙이 있음을 알 수 있습니다. 한번 이전 시간에 공부했었던 순회 방법으로 노드를 순회해 봅시다.
우선 전위 순회를 진행하였는데 우리의 출력 결과와 같습니다. 이것이 우연일 리는 없겠죠. 실제 재귀 함수를 자세히 보자면 이는 재귀 함수에서 자기 자신의 함수를 출력하기 전에 값을 출력했기에 가능했던 일입니다. 이는 결국 전위 순회의 동작 방법과 비슷하다는 것을 알 수 있습니다.
○다른 순회의 구현
이러한 방식이라면 전위순회뿐만 아니라 중위 순회, 후위 순회도 쉽게 만들 수 있을 것입니다. 값을 취하거나 얻는 부분의 위치만 바꾸어 주면 됩니다. 예시는 아래와 같습니다.
중위 순회의 구현
후위 순회의 구현
○ 트리 부분을 마치면서
지금까지 트리에 대해서 간단히 개념과 재귀적으로 구현하는 방법까지 알아보았습니다. 트리의 구현에는 재귀적으로 구현하는 방법 말고도 스택으로 구현하는 방법도 있다고 하는데 이는 나중에 시간이 될 때 알아보도록 하겠습니다.
다음은 greedy 알고리즘에 대해서 알아보려고 합니다. 비교적 간단한 알고리즘이기도 하고, 무엇보다 트리 알고리즘(정확히는 완전탐색)과 greedy 알고리즘을 이용해서 더 효율적인 완전 탐색 알고리즘을 만들 수 있기 때문에 다음 시간에는 greedy 알고리즘을 알아보려고 합니다.
그럼 다음 시간에 뵙겠습니다. 감사합니다.
'알고리즘 5+1' 카테고리의 다른 글
| 탐욕 알고리즘(2) - (greedy 알고리즘 활용 - 강의실 배정문제 ) (0) | 2021.04.21 |
|---|---|
| 탐욕 알고리즘(1 - greedy 알고리즘 소개) (0) | 2021.04.15 |
| 트리 알고리즘 (3 - 트리의 순회방법 (개념편)) (0) | 2021.03.23 |
| 트리 알고리즘 (2 - 완전 탐색) (0) | 2021.03.15 |
| 트리 알고리즘 (1 - 개요) (0) | 2021.03.10 |