8회 테코테코

 

---

≣ 목차

• 요약
• 트리
  • 첫 번째 문제
    • 접근 방법
    • 고민 포인트
    • 최종 코드 및 회고

---

요약

• 이진 트리: 왼쪽 노드와 오른쪽 노드가 균일하게 있는 경우
  • 배열, 연결 리스트를 구현할 수 있다. (메모리 제약 차이)
  • * Tri-Tree 구조
  • 계층형 구조
  • 파일 시스템, 인덱스 B-Tree 등에 이용된다.
• 이진 탐색 트리: 이진 트리 + 정렬
  • 정렬이 잘 되어있으면 탐색이 빠르다.
• 트리 (사이클X) <-> 그래프 (사이클O) - 순환참조 발생
• 트리 (비선형 구조) <-> 배열, 리스트 (선형 구조)

 

• 균형 이진 트리, 포화 이진 트리, 완전 이진 트리
• 전위 순회: DFS, 트리 복사, 파일 탐색
• 중위 순회: 오름차순 정렬, 이진 탐색 트리에서 정렬 유지
• 후위 순회: 메모리 해제, 파일 구조 삭제, 후위 표기법 계산
• 레벨 순회: BFS, 자식 노드를 큐에 담으면서 확인, 최단 거리 탐색(그래프에서 자주 사용되긴 함)

---

트리

첫 번째 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

접근 방법

- a과 b가 만나기까지 a / 2, b / 2 반복문을 진행한다.

- 홀수 인덱스를 처리하기 위해 +1 를 더해서 처리한다.

고민 포인트

- a, b가 만나는 지점이 어디지? (루트 노드)

- 반복문을 어디까지 진행해야 하지? (a != b)

- 홀수 인덱스는 어떻게 처리하지? (+1)

- 다시 배정되는 참가자의 번호를 어떻게 처리하지? (1~N/2)

최종 코드 및 회고

- 처음에는 생각할 부분이 많았는데, 풀이법이 생각난 후 쉽게 풀이할 수 있었다.

class Solution
{
    public int solution(int n, int a, int b)
    {
        int level;
        for (level = 0; a != b; level++) {
            a = (a + 1) / 2;
            b = (b + 1) / 2;
        }
        return level;
    }
}