자료구조를 배운 뒤로 많은 사람들이 알고리즘을 늪에서 허우적거리고 있었다. 물론, 나도 같이 물 먹고 있었다. 그래서 이대로 뒤 쳐질 수 없기 때문에 모든 것을 완벽히 하는 '안내서'를 만들어 내기에 이르렀다.
2. Tree의 구조와 특징
<파이썬 알고리즘 인터뷰> p.384, 책만, 2020
트리구조의 특이점은 우리가 이때까지 보아왔던 Array, Stack, Queue와 다르게 '부모와 자식이 있는 구조'가 트리구조라고 할 수 있다. 물론 형제도 있다.
이때 각각의 요소들은 'Node'라고 부른다.
가장 마지막에 있는 node 즉, 자식이 없는 node를 'Leaf'라고 부른다.
각 층에 따라 '레벨'로 구분할 수 있다.
3. 이진트리 (Binary Tree)
Binary Tree. 위키백과
자식을 2개만 가지는 트리.
물론, 3개 이상도 붙을 수 있지만 우리가 보는 알고리즘은 이진트리를 이용해서 해결할 수 있다.
4. 이진 탐색 트리 (Binary Search Tree)
<파이썬 알고리즘 인터뷰> p.42, 책만, 2020
부모 노드의 기준으로 자식이 작은것은 왼쪽, 큰 것은 오른쪽에 위치하게 되는 트리의 한 구조이다.
위의 그림에서 보듯이, 크다 작다만 비교해서 원하는 타깃을 찾을 수 있도록 할 수 있다.
이 경우, 시간복잡도는 O(log N)이 된다.
배열로 이진 탐색트리를 만들 수 있다. 배열을 하나 만들어서 중간 값을 찾아서, 루트로 지정하고 그것을 기준으로 작은 수를 왼쪽의 자식으로 쓰고 그 왼쪽 자식을 다시 루트 즉, 중간값이라고 크기를 다시 비교해서 작으면 왼쪽, 크면 오른쪽에 넣는 것을 반복하면 배열들을 이진 탐색 트리로 만들 수 있다.
즉, 중간값을 찾고, 절반으로 나눈 것에 다시 중간값을 찾고, 또 절반 나눈 것에 다시 중간값을 찾고... 이거 어디서 많이 보던 행동이다. 시작하는 인덱스와 끝나는 인덱스를 받아서 그 중간값을 찾아 반환하는 '재귀 함수'를 만들면 간단하게 해결할 수 있다.
5. 이진트리의 순회방법
Inorder
Left -> Root -> Right의 순서로 탐색함.
자식이 없으면 다시 위로 올라가 자기 자신(Root)을 출력함.
위의 예시에서 보면, 1, 5, 7, 8, 10, 15. 20, 17, 25의 결과가 나온다.
Preorder
Root -> Left -> Right의 순서로 탐색함.
일단 자기 자신(Root)을 출력하고, 왼쪽으로 먼저 가서 다시 자신을 출력, 자식이 없을 때까지 반복한 후, 자식이 없다면 다시 위로 올라간다. 하지만, 먼저 자기 자신을 출력했기 때문에 바로 오른쪽으로 가서 출력하게 된다.
위의 예시에서 보면, 15, 10, 5, 1, 7, 8, 20, 17, 25의 결과가 나온다.
Postorder
Left -> Right -> Root의 순서로 탐색함.
왼쪽으로 자식이 없을 때까지 간 후, 자식이 없는 노드를 출력, 그리고 바로 오른쪽으로 넘어가서 출력, 그 후 자기 자신으로 넘어가게 된다.
위의 예시에서 보면, 1, 7, 8, 5, 10, 17, 25, 20, 15의 결과가 나온다.
위의 방법으로 트리들을 순회해서 답을 찾게 된다. 왼쪽부터 오른쪽으로 가는 것은 같지만 찾는 방법에 따라 답을 도출하는 시간이 차이가 난다.
6. Graph 검색
이 그레프에서 둘의 예시를 설명 할 것이다.
① DFS (Depth-First Search)
깊이 우선 탐색 방법이라고도 말한다.
앞에 적혀 있던 이진트리의 순회 방법 3가지가 DFS에 속한다.
하나의 자식을 방문하여, 그다음 자식, 그다음 자식으로 자식이 없는 경우까지 들어가서 방문한 후에, 그다음 가장 가까운 줄기를 방문하는 것을 반복하는 것이다.
즉, Stack을 이용하면 된다.
처음 Stack으로 사용할 Array를 만들고, Root(0)를 넣는다.
그리고 바로 Root(0)가 Stack에서 나오게 되고, 그에 자식(1)을 모두 Stack에 넣는다.
나왔던 Root(0)를 출력하고, Stack에 들어 있던 자식(1)은 Stack에서 나오게 되고, 그에 자식을 모두(2, 3) Stack에 넣는다.
들어있던 Stack의 가장 상위의 노드(1)를 출력하고, Stack의 가장 위에 있는 노드(3)를 꺼내고, 이미 들어간 노드(2)를 제외하고 남은 자식들(4, 5)을 스택에 넣고 꺼내진 노드(3)를 출력한다.
Stack에서 다시 가장 위에 있는 노드(5)를 꺼내고, 꺼낸 노드의 자식들(6, 7)을 Stack에 넣고 꺼내진 노드(5)를 출력한다.
Stack의 가장 위에 있는 노드(7)를 꺼내고, 자식 노드가 없으므로, 바로 출력한다.
Stack에서 다시 가장 위에 있는 노드(6)를 꺼내고, 꺼낸 노드의 자식(8)을 Stack에 넣고 꺼내진 노드(6)를 출력한다.
Stack에 남은 노드(8, 4 ,2)는 자식이 없으므로 순서대로 꺼내지고 출력된다.
결국 출력 결과는 0, 1, 3, 5, 7, 6, 8, 4, 2 순이다.
위의 내용을 재귀 함수로 구연할 수도 있다. (노드에 방문하면 방문한 노드를 출력하고, 자식들을 Queue에 순서대로 넣고, 그 자식을 재귀 호출한다. 이것을 반복한다.)
시작 노드(0)를 재귀 함수로 호출한다. 호출되었을 때 자신(0)을 출력한다.
자식 노드(1)를 재귀 함수로 호출한다. 호출되었을 때 자신(1)을 출력한다.
첫 번째 자식 노드(2)를 재귀 함수로 호출한다. 호출되었을 때 자신(2)을 출력한다.
연결관계를 입력할 때 왼쪽을 먼저 출력하게 지정하였다. 그래서 왼쪽의 노드(4)를 재귀 함수로 호출한다. 호출되었을 때 자신(4)을 출력한다.
그 전 단계에서 오른쪽 노드(3)에 해당하는 부분을 이미 만났으므로 아까의 오른쪽 노드(3)를 재귀 함수로 호출한다. 호출되었을 때 자신(3)을 출력한다.
마지막 남은 자식 노드(5)를 재귀 함수로 호출한다. 호출되었을 때 자신(5)을 출력한다.
연결관계를 입력할 때 왼쪽을 먼저 출력하게 지정하였기 때문에 왼쪽의 노드(6)를 재귀 함수로 호출한다. 호출되었을 때 자신(6)을 출력한다.
자식 노드(8)를 재귀 함수로 호출한다. 호출되었을 때 자신(8)을 출력한다.
자식이 더 이상 없으므로 앞 단계로 나와서 호출되지 않은노드(7)를 재귀 함수로 호출한다. 호출되었을 때 자신(7)을 출력한다.
결국 출력 결과는 0, 1, 2, 4, 3, 5, 6, 8, 7 순이다.
일상생활에서 페이지 뒤로, 앞으로 가기 등을 생각한다.
② BFS (Breadth-First Search)
넓이 우선 탐색 방법이라고도 말한다.
하나의 자식을 방문하면, 일단 같은 레벨의 모든 형제들을 다 방문하고, 자식의 자식 노드를 방문하여 같은 레벨의 모든 형제들을 방문하는 것을 반복하는 것이다.
즉, Queue를 이용하면 된다.
처음 Queue로 사용할 Array를 만들고. Root(0)를 넣는다. Queue는 기준이 필요해서 처음 만들 때 넣어놓고 시작한다.
그리고 바로 Root(0)가 Queue에서 나오게 되고, 그에 자식(1)을 모두 Queue에 넣는다. 꺼냈던 노드(0)는 출력한다.
Queue에서 순서대로 노드(1)를 하나 꺼내고, 자식 노드들(2, 3)을 모두 Queue에 추가한다. 꺼냈던 노드(1)는 출력한다.
Queue에서 순서대로 노드(2)를 하나 꺼내고, 이미 들어가 있는 자식 노드들(2, 3)을 제외하고 자식 노드(4)를 Queue에 넣는다. 그리고 꺼냈던 노드(2)는 출력한다.
Queue에서 순서대로 노드(3)를 하나 꺼내고, 이미 들어가 있는 자식 노드들(2, 4)을 제외하고 자식 노드(5)를 Queue에 넣는다. 그리고 꺼냈던 노드(3)는 출력한다.
Queue에서 순서대로 노드(4)를 하나 꺼내고, 이미 모든 자식 노드들(2, 3)은 Queue에서 들어왔다 나갔기 때문에 꺼냈던 노드(4)는 바로 출력된다.
Queue에서 순서대로 노드(5)를 하나 꺼내고, 자식 노드들(6, 7)을 모두 Queue에 추가한다. 꺼냈던 노드(5)는 출력한다.
Queue에서 순서대로 노드(6)를 하나 꺼내고, 자식 노드(8)를 Queue에 추가한다. 꺼냈던 노드(6)는 출력한다.
Queue에서 순서대로 노드(7)를 하나 꺼내고, 자식 노드들이 없기 때문에 꺼냈던 노드(7)는 바로 출력된다.
Queue에서 순서대로 노드(8)를 하나 꺼내고, 자식 노드들이 없기 때문에 꺼냈던 노드(8)는 바로 출력된다.
결국 출력 결과는 0, 1, 2, 3, 4, 5, 6, 7, 8 순이다.
일상생활에서 프린터기의 작동 원리 등을 생각한다.
기본적인 방법은 이렇다. 하지만 코드로 표현하려고 하면 잘 안될 것이다. 하지만 의미를 이해하고 간단한 문제부터 접근한다면 각각의 순회 방법을 이용하는 방법이 보이기 시작한다. 그 이후 반복해서 문제를 해결하게 되면 익숙해 질 수 있다. 이후, 시간이 나면 위의 내용을 코드로 직접 구현해 포스팅 할 예정이다.
