LALA's blog

이진 탐색 트리의 단점 이전에 공부했던 이진 탐색 트리는 검색, 삽입, 삭제 모두 O( h )의 시간복잡도를 보였다. h = 트리의 높이를 의미하며, 평균적으로 O( log n )이라고 할 수 있다. 하지만 최악의 경우? 이진 탐색 트리는 일반 이진트리 구조이다. 일반 이진트리는 2개 이하의 자식을 가지고 있다는 조건을 가졌을 뿐, Complete 이진트리처럼 균형 잡힌 트리 모양을 보장하지 않는다. 만약 입력 데이터가 [ 1, 2, 3, 4 ] 순으로 들어온다면 아래의 그림과 같이 한쪽으로 치우친 Skewed Tree 모양이 되어, 노드 n개일 때 O( n )의 시간복잡도를 보일 수 있다. 이진 트리에 1부터 N까지 랜덤한 숫자가 들어온다면 평균적으로 트리의 높이가 log n이라고 증명되어 있다. lo..

Dynamic Set이란? - 배열, 링크드 리스트, 트리 등등.. - 여러 개의 키(key) 저장 - 다음과 같은 연산을 지원하는 자료구조 ① INSERT - 새로운 키의 삽입 ② SEARCH - 키 탐색 ③ DELETE - 키의 삭제 다양한 방법들 - 정렬된 / 정렬되지 않은 배열 or 연결 리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)이다. - 이진 탐색 트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 - Direct Address Table, 해쉬 테이블 등 검색 트리란? - Dynamic set을 트리의 형태로 구현 - 일반적으로 INSERT, SEARCH, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 ..

트리의 기본적인 성질 - 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다. - 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. - 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에). 이진 트리 (binary tree)란? - 이진 트리는 여러 개의 자식 노드를 가질 수 있는 일반 트리와 다르게, 최대 2개의 자식만을 가질 수 있다. - 즉, 0개, 1개, 2개의 자식 노드만 가질 수 있다. - 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도) 이진 트리 응용의 예 1) Expression Tree 2) 허프만 코드 각각의 알파벳에 부여된 이진 코드를 이런 트리의 형태로 표현할 수 있..

계수 정렬 원소의 종류가 K개, 즉 원소들의 범위가 0 ~ K-1일 때, 시간복잡도가 O(N + K)밖에 되지 않는 정렬법이다. 예를 들어, 원소가 1, 2, 3, 4, 5로 한정되어 있을 때 어떻게 정렬하면 좋을까? 각 원소가 몇 번 등장했는지 세면 간단하게 정렬할 수있다. [ 1 , 5 , 4 , 2 , 3 , 1 , 4 ] 의 경우 1 - 2번 2 - 1번 3 - 1번 4 - 2번 5 - 1번 등장한다. 그렇다면 작은 수부터 등장한 횟수만큼 [ 1 , 1 , 2 , 3 , 4 , 4 , 5 ] 로 쉽게 정렬할 수 있다. 가장 빠른 퀵정렬의 시간복잡도는 O(nlogn)이며 최악의 경우에는 O(N^2)이다. 그렇다면 항상 계수정렬이 더 빠른걸까? 만약 10개의 데이터 (N = 10)이고 가장 큰 수가 ..

퀵 정렬 (Quick Sort)이란? - 분할 정복 알고리즘 중 하나로 pivot을 기준으로 양쪽으로 정렬하는 알고리즘이다. - 병합 정렬과는 다르게 배열을 비균등하게 분할한다. Process ① 배열에서 하나의 원소(Pivot)을 고른다. ② (분할) Pivot 앞에는 Pivot보다 작은 원소들이 오고, Pivot 뒤에는 Pivot보다 큰 원소들이 오도록 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. ③ 분할된 두 배열에 대해 재귀적으로 이 과정을 반복한다. Code 시간복잡도 최선의 경우 : O(nlog₂n) * 비교 횟수 => log₂n 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순..

삽입 정렬 (Insertion Sort)이란? - 선택 정렬과 유사하지만, 좀 더 효율적인 알고리즘이다. - 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. - 매 순서마다 해당 원소를 삽입할 위치를 찾고 해당 위치에 넣는 방식이다. Process ① 처음 Target 값은 두 번째 원소부터 시작한다. 두 번째 원소부터 앞의 원소들과 비교하여 삽입할 위치를 찾는다. ② 찾은 위치부터 자료를 뒤로 밀고 그 자리에 해당 원소를 삽입한다. Code void InsertSort(int Data[], int Lenght) { for(int i = 1; i < Lenght; i++) { int j, Target = Dat..

선택 정렬 (Selection Sort)이란? 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을 지 선택하는 알고리즘이다. 선택 정렬 vs 삽입 정렬 선택 정렬은 배열에서 해당 자리를 선택하고 그자리에 오는 값을 찾는 것이라고 생각하면 편하다. Process ① 주어진 배열 중에 최소값을 찾는다. ② 그 값을 맨 앞에 위치한 값과 교체한다. ③ 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Code void SelectionSort(int DataSet[], int Lenght) { for(int i = 0; i DataSet..

버블 정렬 (Bubble Sort)이란? 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. Process ① 1회전에서 첫 번째 원소부터 시작. 첫 번째 원소와 두 번째 원소를 비교하여 첫 번째 원소가 더 크면 두 원소의 자리를 교환한다. 그리고 두 번째 원소를 세 번째 원소와, 세 번째 원소를 네 번째 원소와, ... N - 1 번째 원소를 N 번째 원소와 비교와 교환을 반복한다. ② 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하기 때문에, 2회전에서는 맨 마지막 원소를 제외하고 비교하면 된다. 이렇게 1회전 수행할 때마다 뒤에서 하나씩 비교 대상에서 제외된다. Code void BubbleSort(int DataSet[], int Lenght..

신장트리(Spanning Tree)란? 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다. 그래프에서 난데없이 트리? 그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 그래프 vs 트리 그래프 - 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다. 트리 - 그래프의 일종 - Cycle을 가지지 않는다. - 계층적 구조를 가진다. - 단 하나의 root를 가진다. 최소 신장 트리(Minimum Spanning Tree : MST)란? 최소 가중치 신장 트리(Minimum Weight S..

신장트리(Spanning Tree)란? 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다. 그래프에서 난데없이 트리? 그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 그래프 vs 트리 그래프 - 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다. 트리 - 그래프의 일종 - Cycle을 가지지 않는다. - 계층적 구조를 가진다. - 단 하나의 root를 가진다. 최소 신장 트리(Minimum Spanning Tree : MST)란? 최소 가중치 신장 트리(Minimum Weight S..