덕's IT Story

힙정렬(Heap Sort)은 힙(Heap)이라는 특수한 자료구조를 사용하는 정렬 알고리즘이다. 힙은 최소힙(Minimum Heap)과 최대힙(Maximum Heap)이 있는데 값이 저장되는 방향만 반대일 뿐 성질은 똑같다. 우선 힙(heap)에 대해서 설명하면, 힙은 이진트리(Binary Tree)로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다(nearly complete binary tree). 힙은 최소힙..

퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다. 퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇..

병합정렬/합병정렬(Merge Sort)는 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합정렬은 자신에 비해 크기가 반인 문제를 두개 푼 다음, 이들을 병합하..

삽입정렬(Insertion Sort)는 이미 정렬되어 있는 i 개 짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다. 선택정렬(Selection Sort)과 버블정렬(Bubble Sort)이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려가는 정렬이다.위의 예제를 살펴보면 배열 A[]에서 루프문을 통해 i가 두번째 원소 ..

버블정렬(Bubble Sort)도 선택정렬(Selection Sort)처럼 제일 큰 원소를 옮기는 작업을 반복하는 정렬이다. 다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다.선택정렬(Selection Sort) 이란 ? 클릭 선택정렬(Selection Sort)버블정렬(Bubble Sort)는 위의 예제 처럼 배열의 처음 인덱스부터 n-1 인덱스까지 이동하면서 인접하는 다음 인덱스의 원소와 크기를 비교하여 순서를 바로 잡아 나간..

선택정렬(Selection Sort)는 원리가 가장 간단한 정렬 알고리즘 중의 하나다. 우선 배열 A[1...n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경쓰지 않아도 된다. 이 원소는 정렬이 끝났다고 볼 수 있으므로 이제 이 원소를 제외한 나머지 원소들로 같은 작업을 반복하면 된다.간결하게 나타내면 각..

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다.예를 들어, 학생 100명의 시험점수를 입력으로 받아 최고점을 출력하는 작업을 한다면 입출력을 다음과 같이 표현할 수 있다.입력 : 100개의 점수출력 : 입력된 100개의 점수 중 최대값이 입출력을 ..

이진검색트리는 저장과 검색에 평균 Θ()시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다. 레드블랙 트리는 자가균형이진탐색 트리(self-balancing..