[TIL] 231018 - 데브코스 3일차

오늘 배운 내용

• 양방향 연결 리스트
• 스택
  • 스택을 활용해 중위 표기법 -> 후위 표기법 변환 및 계산
• 큐
  • 환형 큐(Circular Queue)
  • 우선순위 큐(Priority Queues)
• 트리
  • 이진 트리
    • 포화 이진 트리
    • 완전 이진 트리
    • 이진 트리 순회 : 깊이 우선 순회(중위/전위/후위 순회), 넓이 우선 순회
    • 이진 탐색 트리
    • 힙

 

이진 트리 종류

이진 트리 : 모든 노드의 차수가 2 이하인 트리

1. 포화 이진 트리(Full Binary Tree)
   - 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리

2. 완전 이진 트리(Complete Binary Tree)
   - 높이가 k일 때, 마지막 레벨 전까지는 포화 이진 트리, 마지막 레벨은 왼쪽부터 노드가 채워져 있는 이진 트리

3. 이진 탐색 트리(Binary Search Tree)
   - 왼쪽 서브트리의 데이터는 루트 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 루트 노드의 값보다 큰 이진 트리

 

궁금했던 점

트리는 스택, 큐와 다르게 2차원 자료구조다.

 

왜 2차원 자료구조라고 하는지 궁금해서 생각해봤다.
그림으로 표현했을 때 생긴 형태도 다르지만, 그래프를 생각하니까 이해가 갔다.
그래프에 x좌표와 y좌표가 있는 것처럼 트리에는 y좌표에 해당하는 높이가 있다. 그 부분이 트리가 스택이나 큐와 다른 점이다. 그래서 트리에서 순회가 중요한 연산이라는 것 같다.

 

 

 

어려웠던 점

실습할 때 특이 조건에 대한 부분을 놓치는 경우가 종종 있다. 항상 특이 조건을 염두에 두고 코드를 짜야겠다.

 

 

느낀 점

일정때문에 2일차 강의를 다 수강하지 못했는데, 3일차 강의가 2일차보다 많아져서 당황했다. 아직 3일차라 다행이지만 나중에는 강의 내용이 더 어려워질테니까 그날 할당된 강의는 꼭 그날 다 듣자는 다짐을 다시 하게 되었다.

자료 구조들을 직접 구현한 적이 별로 없었는데 연산들을 직접 구현하니까 그 자료구조를 더 잘 이해하게 된다. 구현하려는 자료구조에 대한 이해가 부족하다면 구현하는 과정이 굉장히 어려울 것 같다.