패스트캠퍼스 챌린지 07일차

---

[오늘 진도]

Part 1. 자료구조 이론

Ch 11. 자료구조 (힙)

01. 힙 구조 1

02. 힙 구조 2

03. 힙 구조 JAVA 구현

 

---

 오늘은 힙에 대해 배웠다. 강사님께서 힙은 구조를 이해하는 건 어렵지 않지만, 코드로 작성하는 게 어렵다고 하시면서 개념만 이해하고 알고리즘을 이해한 다음 코드로 구현하는 걸 들으라고 하셨다. 강의는 힙 구조1, 힙 구조2, 힙 구조 JAVA 표현 총 세 가지로 되어있는데 힙 구조2에서 이미 코드로 구현하는게 나오길래 그냥 다 들었다. 이제 정말 자료구조는 끝이다!

 내가 어제인가 며칠 전 후기를 쓸 때, 부스트코스에서 배운 노드 삭제 방법과 패스트 캠프에서 배운 방법이 서로 다르다고 썼다. 오늘 힙을 배우고 나니 서로 다른 게 아니다. 부스트코스에서는 패스트 캠프에서 말한 세 가지 경우의 수만 다루고 코드로는 다루지 않았다. 그리고 나는 힙과 트리를 제대로 구분하지 못하고 있었다. 이 두 가지가 섞여 서로 다르다는 말을 한 것이다. 여기가 아무도 안 오는 블로그니 망정이지 큰 블로그였으며 논란이 났을 거다. 아무튼 패스트 캠프 강의로 지금이나마 제대로 이해할 수 있어 다행이다. 내가 이해한 내용을 다시 정리해봐야겠다.

 우선 트리는 노드와 브랜치를 이용하여 사이클이 형성되지 않도록 구성한 데이터 구조이다. 트리에는 노드의 브랜치가 최대 2인 트리를 이진 트리라 하고, 이진 트리에 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값이 오도록 규칙을 추가한 것이 이진 탐색 트리(Binary Search Tree)이다. 이진 트리는 완전 트리(Complete Tree)와 정 트리(Full Tree)로 나눌 수 있는데, 완전 트리란 잎 노드가 아닌 모든 노드가 두 개의 자식 노드를 갖고 있고, 가장 깊은 잎 노드는 왼쪽에서 오른쪽으로 순서대로 하나씩 차 있는 노드를 말한다. 정 트리란 모든 노드가 두 개의 자식 노드를 갖고 있고, 잎 노드가 모두 같은 레벨인 트리를 말한다. 여기서 힙은 완전 이진 트리이다.

 트리는 이진 트리의 형태로 탐색, 검색 알고리즘 구현에 많이 사용된다. 힙은 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾는 자료구조 및 알고리즘 구현에 사용된다. 따라서 힙은 각 노드가 해당 노드의 자식 노드보다 크다는 조건을 추가하면 최대 힙(Max Heap), 작다는 조건을 추가하면 최소 힙(Min Heap)이라고 분류할 수 있다. 내가 힙의 삭제를 배울 때, 루트 노드를 제거하고 마지막 노드를 루트에 넣으라고 배운 것도 최대 힙이나 최소 힙에서 최댓값이나 최솟값을 뽑아가면 다시 루트 노드를 최댓값이나 최솟값으로 바꿔놓아야 하기 때문이다. 

 힙에 새로운 노드를 추가하거나 삭제, 노드 확인 등은 쥬피터 노트로 코드를 작성하며 배웠다. 블로그에 잘 정리한 사람들이 많으니까 그걸 참고하면 될 것 같다. 아무튼 어떤 개념을 설명하는 방법엔 여러 가지가 있다. 같은 개념을 다른 방식으로 공부하다 보니 서로 보완해주는 것 같다. 내일부터 알고리즘인데, 알고리즘은 또 모두를 위한 컴퓨터 과학(CS50 2019) 강의로 기본 정렬은 공부해놨다. 하지만 안 배운 게 더 많으니 좀 더 집중해야지. 화이팅!

 

---

 

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.