15 트리

공부하는 감자·2024년 5월 26일

알고리즘

코딩 테스트

목록 보기

15/17

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

트리 알아보기

트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.
- 즉, 그래프의 표현으로도 tree를 표현할 수 있다.
트리의 특징은 다음과 같다.
- 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
- 루트 노드를 제외한 모든 노드는 단 1개의 부모 노드를 갖는다.
- 트리의 부분 트리(sub tree) 역시 트리의 모든 특징을 따른다.
- 트리의 임의의 두 노드를 이어주는 경로는 유일하다. (1개만 나온다)

핵심 이론

트리의 구성 요소

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 노드

코딩 테스트의 트리 문제

두 가지 유형으로 구분할 수 있다.
1. 그래프로 푸는 tree 문제
2. tree만을 위한 문제
DFS, BFS를 이용하여 푸는 tree 문제가 있다.
- tree의 Node와 Edge는 인접 리스트로 표현할 수 있다.
이진 트리 & 세그먼트 트리(index tree) & LCA(최소공통조상)는 tree만을 위한 문제이다.
- 1차원 배열로 tree를 표현할 수 있다. (1차원 배열로 구현하려면 무조건 이진 트리여야 한다)
- 부모 노드로 이동할 때 인덱스 연산(index/2)을 통해 접근한다.

이진 트리

이진 트리(binary tree)는 각 노드의 자식 노드(차수)의 개수가 2개 이하로 구성된 트리를 말한다.
트리 영역에서 가장 많이 사용되는 형태이다

트리의 종류

이진 트리의 종류에는 다음 세 종류가 있다.

편향 이진 트리
포화 이진 트리
완전 이진 트리

편향 이진 트리

노드들이 한쪽으로 편향돼 생성된 이진 트리
데이터를 트리 자료구조에 저장할 때, 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다.

포화 이진 트리

트리의 높이가 모두 일정하며 레프 노드가 꽉 찬 이진 트리

완전 이진 트리

마지막 레벨을 제외하고 완전하게 노드들이 채워져 있다.
마지막 레벨은 왼쪽부터 채워진 트리이다.

이진 트리의 순차 표현

코딩 테스트에서 트리 문제가 나오면 그래프의 표현 방식보다 다음 방식으로 데이터를 담는 것이 일반적이다.

가장 직관적이면서 편리한 트리 자료구조 형태는 ‘배열’이다.

이진 트리는 1차원 배열의 형태로 표현할 수 있다.

만약 노드가 없다면(아직 채워지지 않는다면) 해당 공간은 비워놓는다.

int[] tree = new int[N];
tree[1] = A; // 루프 노드
tree[2] = B; // 루프 노드의 자식 노드 1
tree[3] = C; // 루프 노드의 자식 노드 2
tree[4] = D; // B 노드의 자식 노드 1
tree[5] = E; // B 노드의 자식 노드 2
tree[6] = F; // C 노드의 자식 노드 1
tree[7] = G; // C 노드의 자식 노드 2

트리의 노드와 배열의 인덱스 간의 상관관계는 다음과 같다.

아래의 인덱스 연산 방식은 세그먼트 트리나 LCA 알고리즘에서도 기본이 되는 연산이다.

이동 목표 노드	인덱스 연산	제약 조건 (N=노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index * 2	index * 2 ≤ N
오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 ≤ N

세그먼트 트리 (인덱스 트리)

세그먼트 트리는 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태이다.
- 구간 합에서 사용하는 합 배열은 업데이트가 잦으면 속도가 느려진다.
더 큰 범위는 ‘인덱스 트리’라고 불린다.
- 코딩 테스트 영역에서는 큰 차이가 없다.

핵심 이론

세그먼트 트리의 종류는 다음과 같이 나눌 수 있다.
- 구간 합
- 최대/최소 구하기
세그먼트 트리의 구현 단계는 다음과 같이 나눌 수 있다.
- 트리 초기화하기
- 질의값 구하기 (구간 합 또는 최대/최소)
- 데이터 업데이트 하기

구현 단계

트리 초기화하기
- 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.
  - 트리 배열의 크기는 $2^k≥N$ 을 만족하는 k의 최솟값을 구한 후, $2^k*2$ 를 트리 배열의 크기로 정의한다.
```
// 샘플 데이터 (N=8이므로, k는 3이 된다)
int[] sample = new int {5, 8, 4, 3, 7, 2, 1, 6};

// 트리 배열의 크기 size
int size = 2^3 * 2;
```
- 리프 노드에 원본 데이터를 입력한다. 이때, 리프 노드의 시작 위치를 트리 배열의 인덱스로 구한다. (시작 인덱스 = $2^k$ )
```
int[] tree = new int[N+1];

int start_index = 8;
tree[start_index++] = node;
```
- 리프 노드를 제외한 나머지 노드의 값을 채운다. ( $2^k-1$ 부터 1번 쪽으로 채운다)
  - 채워야 하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당 값을 채울 수 있다.
  - 자식 노드의 인덱스는 2N과 2N+1이다.
```
// 구간 합 (자식 노드들의 합)
A[N] = A[2N] + A[2N+1];

// 최대 (자식 노드 중 큰 값)
A[N] = max(A[2N], A[2N+1]);

// 최소 (자식 노드 중 작은 값)
A[N] = min(A[2N], A[2N+1]);
```
💡 이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구 사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있게 된다.

질의값 구하기

주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다.
- 기존 샘플을 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야 한다.
```
// 인덱스 변경 방법
(세그먼트 트리 index) = (주어진 질의 index) + 2^k - 1
```

질의에서의 시작 인덱스와 종료 인덱스에 관해 부모 노드로 이동하면서 주어진 질의에 해당하는 값을 구한다.

// 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에,
// 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고,
// 해당 노드의 부모 노드는 대상 범위에서 제외한다.
1. start_index % 2 == 1일 때 해당 노드를 선택한다. (두 자식 노드 중 오른쪽일 때)
2. end_index % 2 == 0일 때 해당 노드를 선택한다. (두 자식 노드 중 왼쪽일 때)

// 부모 노드를 대상 범위에서 제거하는 방법 (범위를 부모 노드로 이동)
3. start_index depth 변경: start_index = (start_index + 1)/2 연산을 실행한다.
4. end_index depth 변경: end_index = (end_index - 1)/2 연산을 실행한다.

5. 1~4번 과정을 반복하다가 end_index < start_index가 되면 종료한다.

질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.
- 구간 합: 선택된 노드를 모두 더한다
- 최댓값 구하기: 선택된 노드 중 MAX 값을 선택해 출력한다.
- 최솟값 구하기: 선택된 노드 중 MIN 값을 선택해 출력한다.

데이터 업데이트하기
- 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 다르다.
- 구간합에서는 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경한다.
- 최댓값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트한다. 업데이트가 일어나지 않으면 종료한다.
- 최솟값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트 한다. 업데이트가 일어나지 않으면 종료한다.

최소 공통 조상 LCA

트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상(Lowest common ancestor)이라고 한다.
시간 복잡도는 트리의 높이에 밀접하다.

일반적인 최소 공통 조상 구하기

트리의 높이가 크지 않을 때 최소 공통 조상을 구하는 방법
트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다.
- 이러한 문제를 해결하기 위해 새롭게 제안된 방식이 ‘최소 공통 조상 빠르게 구하기’이다.

구현 방식

루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다.
- DFS 또는 BFS를 이용해 탐색을 수행한다.
- 트리라는 특징 덕분에 바로 직전 탐색 노드가 부모 노드가 되고, depth를 쉽게 구할 수 있다.
선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춘다.
- 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.
선택된 두 노드의 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.
- 이때 처음 만나는 노드가 최소 공통 조상이므로 탐색을 종료한다.

최소 공통 조상 빠르게 구하기

일반적인 최소 공통 조상 구하기 알고리즘을 약간 변형한 형태이므로, ‘일반적인 구하기’ 원리를 정확하게 학습해야 한다.
서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주던 방식에서 $2^k$ 씩 올라가 비교한느 방식이다.
따라서 기존에 자신의 부모 노드만 저장해 놓던 방식에서 $2^k$ 번째 위치의 부모 노드까지 저장해 둬야 한다.

구현 방식

부모 노드 저장 배열 만들기
- 부모 노드 배열의 정의 P[K][N] = N번 노드의 $2^k$번째 부모의 노드 번호
- 부모 노드 배열의 점화식 P[K][N] = P[K-1][P[k-1][N]] N의 $2^k$ 번째 부모 노드는 N의 $2^{k-1}$ 번째 부모 노드의 $2^{k-1}$ 번째 부모 노드라는 의미이다. 배열에서 K는 트리의 깊이 > $2^k$ 를 만족하는 최댓값이다. 즉, K=4라고 가정하면 N의 16번째 부모 노드는 N의 여덟 번째 부모 노드의 여덟 번째 부모 노드라는 의미이다.
선택된 두 노드의 깊이 맞추기
- P 배열을 이용해 기존에 한 단계씩 맞췄던 깊이를 $2^k$ 단위로 넘어가면서 맞춘다.
최소 공통 조상 찾기
- 공통 조상을 찾는 작업도 $2^k$ 단위로 점프하면서 맞춘다.
- K값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
- 최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동한다.
- K가 0이 될 때까지 반복하며, 반목문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

공부하는 감자

책을 읽거나 강의를 들으며 공부한 내용을 정리합니다. 가끔 개발하는데 있었던 이슈도 올립니다.

15 트리

코딩 테스트

트리 알아보기

핵심 이론

코딩 테스트의 트리 문제

이진 트리

트리의 종류

편향 이진 트리

포화 이진 트리

완전 이진 트리

이진 트리의 순차 표현

세그먼트 트리 (인덱스 트리)

핵심 이론

구현 단계

최소 공통 조상 LCA

일반적인 최소 공통 조상 구하기

구현 방식

최소 공통 조상 빠르게 구하기

구현 방식

Reference

14 최소 신장 트리

16 조합

0개의 댓글