2022.11.14 TIL 알고리즘 4장

트리 - 계층형 비선형 자료 구조

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형구조는 표현에 초점이 맞춰져 있습니다.

 

Node: 트리에서 데이터를 저장하는 기본 요소

Root Node: 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node: 어떤 노드의 상위 레벨에 연결된 노드

Child Node: 어떤 노드의 하위 레벨에 연결된 노드

Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

이진 트리의 높이는 최대로 해봤자 O(log(N))

 

 

힙

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

최댓값이 맨 위인 힙을 Max 힙 , 최솟값이 맨 위인 힙을 Min 힙

원소 추가 규칙

1. 원소를 맨 마지막에 넣습니다.

2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.

 

원소 제거 규칙

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교합니다.

    두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다 .

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.

5. 2에서 제거한 원래 루트 노드를 반환합니다.

 

DFS & BFS

DFS : Depth First Search

- 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.

- 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.

- 만약 끝에 도달했다면 리턴한다.

 

BFS :  Breadth First Search

현재 인접한 노드 먼저 방문

구현의 방법

1. 루트 노드를 큐에 넣습니다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가딕 비면 탐색을 종료한다.

 

 

Dynamic Programming

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용

 

결과를 기록하는 것을 메모이제이션(Memoization)

문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)

 

 

이해를 바탕으로 반복 숙달 필요!