트리 ~ 그리디

트리

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조.

특징

• 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가짐.

• 노드가 N개인 트리는 반드시 N-1개의 간선을 가짐.

• 루트에서 특정 노드로 가는 경로는 유일함.

이진 트리

• 각 노드가 최대 2개의 자식을 가지는 트리를 의미. 탐색 알고리즘에 자주 사용됨.

• 이진트리, 완전이진트리, 포화이진트리, 편향이진트리가 있음.

이진 트리 특징

• 노드가 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있음.

• 노드가 N개인 포화 또는 완전 이진 트리의 높이는 log N임.

• 높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가짐.

• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등의 자료구조에 응용되는 경우가 많음.

이진 트리 구현 방법

힙 (Heap)

• 우선순위 큐 : FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐.

• heap은 우선 순위 큐를 구현하기 위한 가장 적합한 방법(우선순위 큐 ≠ 힙).

특징

• 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬됨.

• 우선순위가 높은 요소가 먼저 나감.

• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 가장 작은 값이 되는 최소 힙(Min Heap)이 있음.

• 아쉽게도 JS에서 직접 구현해야 함.

트라이 (Trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조.

• 미리 정의한 문자열로 자동완성 구현 가능.

특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있음.

• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있음.

• L이 문자열의 길이일 때, 탐색, 삽입은 O(L)만큼 걸림 (찾는 문자열의 길이만큼 시간 복잡도를 가짐).

• 대신 각 노드가 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용함.

정렬 (Sort)

• 요소들을 일정한 순서대로 열거하는 알고리즘.

특징

• 정렬 기준은 사용자가 정할 수 있음.

• 크게 비교식과 분산식 정렬로 나뉨.

• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재함.
• 버블 : 서로 인접한 두 요소를 검사하여 정렬. O(n^2)
• 선택 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하여 정렬. O(n^2)
• 삽입 : 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하여 정렬. O(n^2)
• 합병 : 분할 정복 알고리즘을 이용한 최선, 촤악이 같인 안정적인 정렬 알고리즘. O(n log n)
• 퀵 : 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 있는 불안정 정렬. O(n log n)

이진 탐색 (Binary Search)

• 선형 탐색 : 순서대로 하나씩 찾는 탐색 알고리즘. O(n)

• 이진 탐색 : 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘. O(log n)

특징

• 반드시 정렬이 되어 있어야 함 → 정렬 후 탐색 시 선형 탐색보다 느릴 수 있음.

• 배열, 이진 트리를 이용하여 구현할 수 있음.

• O(log n) 시간 복잡도인만큼 상당히 빠름.

이진 탐색 트리

• 문제점 : 최악의 경우 한쪽으로 편향된 트리가 될 수 있음. 그런 경우 순차 탐색과 동일한 시간복잡도를 가짐. AVL 트리, 레드-블랙 트리와 같은 자료구조를 이용해야 함.

BFS, DFS

BFS (너비 우선 탐색)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘.

• Queue를 이용하여 구현 가능.

• 시작 지점에서 가까운 노드부터 탐색.

• V가 노드 수, E가 간선 수일 때 시간복잡도는 O(V+E)임.

DFS (깊이 우선 탐색)

• 그래프 탐색 알고리즘으로 최대한 깊은 노드부터 탐색하는 알고리즘.

• stack을 이용하여 구현 가능.

• 시작 노드에서 깊은 것부터 찾음.

• BFS의 시간 복잡도와 동일함.

그리디 (Greedy)

• 매 선태개에서 지금 가장 최적인 답을 선택하는 알고리즘.

• 최적해를 보장해주진 않음.

특징

• 최적해를 구하는 알고리즘보다 빠른 경우가 많음. O(n)

• 크루스칼, 다익스트라 알고리즘 등에 사용됨.

• 직관적인 문제 풀이에 적합함.

Follow Up Tasks