덕's IT Story

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

퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다. 퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇보다 큰 수들은 피봇의 뒤로 보낸다. 정렬되지 않은 피봇의 좌우는 재귀적으로 문제를 해결하여 배열 전체가 정렬이 되도록 한다. 예를 들어 설명하면 다음과 같다. 이 예는 배열의 젤 뒷원소를 피봇으로 삼아 퀵정렬(Quick Sort)를 수행하는 경우이다. 피봇인 15보다 작은 수들..

병합정렬/합병정렬(Merge Sort)는 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합정렬은 자신에 비해 크기가 반인 문제를 두개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다. 위 그림의 예를 살펴보면 초기 배열 A = { 5, 2, 4, 7, 1, 3, 2, 6} 이다. 병합정렬의 전반부, 후반부 정렬이 재귀적으로 반복되면서 배열의 원소가 하나씩 남을때 까지 쪼개진다. 그리고 각각 병합을 하면서 정렬이..

삽입정렬(Insertion Sort)는 이미 정렬되어 있는 i 개 짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다. 선택정렬(Selection Sort)과 버블정렬(Bubble Sort)이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려가는 정렬이다. 위의 예제를 살펴보면 배열 A[]에서 루프문을 통해 i가 두번째 원소 부터 배열의 끝 원소까지 루프문을 돌면서 A[i]번째의 원소를 자리에 알맞게 넣는다. i가 두번째 원소를 가리킬때 A[2]인 10의 자리는 A[1]인 29와 위치가 바껴야 하므로 자리가 교체된다. i가 세번째 원소를 가르킬때 A[3]인 14의 위치는 A[1]인 10 ..

버블정렬(Bubble Sort)도 선택정렬(Selection Sort)처럼 제일 큰 원소를 옮기는 작업을 반복하는 정렬이다. 다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 선택정렬(Selection Sort) 이란 ? 클릭 선택정렬(Selection Sort) 버블정렬(Bubble Sort)는 위의 예제 처럼 배열의 처음 인덱스부터 n-1 인덱스까지 이동하면서 인접하는 다음 인덱스의 원소와 크기를 비교하여 순서를 바로 잡아 나간다. 이 과정을 반복하게 되면 배열의 맨끝에는 배열의 가장 큰 원소가 자리하게 된다. 그러면 배열의 제일 마지막을 잊어버리고 이를 반복하게 되면 배열이 차례대로 끝에서 부터 내림차순으로 정렬되게 된다. 버블정렬(Bubble Sort)의 슈도코드는 다음과 같다. 버블..

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

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다. 예를 들어, 학생 100명의 시험점수를 입력으로 받아 최고점을 출력하는 작업을 한다면 입출력을 다음과 같이 표현할 수 있다. 입력 : 100개의 점수출력 : 입력된 100개의 점수 중 최대값 이 입출력을 다음과 같이 좀더 구체적으로 표현할 수도 있다. 입력 : 100개의 변수 x[1],...,x[100]의 값출력 : x[1],...,x[100] 중 최대값 이런 입출력을 요구하는 알고리즘은 대략 다음과 같은 모양을 가질 것이다. maxScore(x[], n..

이진검색트리는 저장과 검색에 평균 Θ()시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다. 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때..