240111-TIL

1월 11일

오늘은 일어나자마자 알고리즘 문제 하나를 풀었다.

 

오늘의 문제!

 

김서방을 찾으면 되는데

 

문제 설명을 보자

 

 

아하! 금방 하겠는데?

 

 

이게 서울

 

 

우리는 서울의 집들을 전부 뒤져가지구?

 

 

내가 뒤진 집에 김서방이 살고있다면? answer에 말해준다.

 

 

금방했네!

 

그리고 나선 어제 알고리즘 시간에 정말 궁금했었던 이진 트리에 대한 내용을 정리해보겠다.

 

트리

트리는 계층적 자료구조로 부모 노드 하단에 자식 노드를 연결하여 구성되는 형태의 자료구조이다.

 

트리 용어 정리

• Root : 트리의 맨 위에 있는 노드, 유일한 부모가 없는 노드
• Node : 값을 가지고 있는 기본 단위 객체
• Edge : 상위 노드와 하위 노드 간의 연결하는 선(link)
• Branch : 한 노드에서 갈라져 나온 자식 노드의 수
• Parent : 해당 노드 바로 위에 있는 부모 노드
• Child : 해당 노드 바로 아래에 있는 자식 노드
• Sibling : 같은 부모를 같는 노드들
• Leaf : 더 이상 자식 노드가 없는 최하위 노드
• Sub Tree : 주어진 노드의 모든 하위 목록
• Depth : 노드에서 루트까지의 edge 수
• Height : 루트 노드와 가장 먼 leaf 사이의 edge 수
• Level : depth + 1
• Tree traversal : 트리의 모든 노드를 한번씩 방문하는 과정

트리에 대해 알아봤으니 그럼 도대체 이진 트리가 뭐냐?

 

이진 트리 : 노드의 최대 Branch가 2개인 트리

 

 각 노드가 2개의 자식노드를 가질때 이진 트리라고 하는데

 

이때 자식노드는 각각 왼쪽 자식노드와 오른쪽의 자식노드로 표현한다

 

최대 2개이기 때문에 자식이 있을수도 없을수도 있다.

 

2진트리의 장점은 1차원 배열로 표현할 수 있다는 점인데

 

출처 : https://rosweet-ai.tistory.com/

 

단점이라 한다면 배열의 한계인 공간의 제약이나 데이터의 삽입, 삭제시에 기존 데이터의 이동과 같은 단점은 

 

극복할 수 없다고 한다.

오늘은 간단한 알고리즘 문제와 함께 궁금했던 트리에 대해서 알아보고

 

이진트리의 장 / 단점에 대해서 알아보았다.

 

그림으로 자세히 설명되있는 글들이 많아서 이해하는데 굉장히 많은 도움이 됬던 이진 트리였다.

 

이렇게 1월 11일 TIL을 마치도록 하겠다.