01. 자료구조론 Intro (알고리즘, Selection Sort, Binary Search)

알고리즘

알고리즘은 특정한 작업을 수행하는 유한 개의 명령 집합으로, 다음과 같은 기준을 만족해야합니다.

• 0개 이상의 input
• 1개 이상의 output
• 명확성
• 유한성 (유한한 단계를 거치면 종료되어야 함)
• 효용성

다음으로 몇가지 알고리즘을 소개하겠습니다.

Selection Sort (선택 정렬)

정렬 알고리즘을 이용하면 리스트의 요소들을 특정한 기준에 맞추어 정렬할 수 있으며, 이 게시글에서는 숫자를 오름차순으로 정렬하는 경우를 다루겠습니다.

우선 선택 정렬은 정렬되지 않은 리스트에서 가장 작은 아이템을 골라 정렬된 리스트에 이어붙이는 방식으로 진행되는 알고리즘입니다.

 

선택 정렬 알고리즘을 돌리면 아래와 같은 순서로 배열이 정렬됩니다.

빨간 색으로 표현된 숫자는 정렬이 된 부분이고, 까만색의 숫자는 아직 정렬이 되지 않은 부분입니다.

까만색의 정렬이 되지 않은 배열에서 가장 작은 숫자를 골라 빨간 배열의 다음 숫자와 위치를 바꿔주는 방식으로 알고리즘이 진행됩니다.

 

해당 알고리즘을 코드로 나타내면 다음과 같습니다.

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void selection_sort(int list[], int n) {
    int min, tmp;
    for (int i = 0; i < n - 1; i++) {
        min = i;
        for (int j = i + 1; j < n; j++) {
        	if (list[j] < list[min]) min = j;
        }
        SWAP(list[i], list[min], tmp);
    }
}

Binary Search (이진 탐색)

탐색 알고리즘은 주어진 배열에서 원하는 조건을 만족하는 요소의 index 를 찾는 알고리즘입니다.

이때, 이진 탐색 알고리즘에서 사용하는 배열은 반드시 정렬되어 있어야 합니다.

 

이 알고리즘은 배열의 가운데 요소를 찾고자 하는 요소와 비교합니다. 만약 가운데 값과 찾는 값이 동일하다면 원하는 값을 찾은 것이기 때문에 알고리즘을 종료합니다.

찾는 값보다 가운데 값이 작다면 가운데 값보다 큰 값을 갖는 오른쪽 배열만 신경쓰면 되고, 찾는 값보다 가운데 값이 크다면 가운데 값보다 작은 값을 갖는 왼쪽 배열만 고려하면 되게 됩니다. 그리고 이렇게 반으로 줄어든 배열을 가지고 원하는 값을 찾을 때까지 위의 행동을 반복합니다.

 

이렇게 한 번의 비교마다 고려해야할 배열의 크기는 절반으로 줄어들게 되므로, 처음부터 하나하나 비교해가며 원하는 값을 찾는 것보다 훨씬 더 빠르게 탐색을 할 수 있습니다.

 

다시 한번 알고리즘의 동작을 나타내자면,

찾는 값을 value, 배열을 list, 고려해야하는 배열의 첫번째 인덱스를 start, 마지막 인덱스를 end라고 했을 때,

middle = (start + end) / 2 로 중간 지점을 잡고
list[middle] 을 value와 비교하여
1) value < list[middle] 인 경우, end = middle-1 로 값을 변경해주고,
2) value = list[middle] 인 경우, middle을 리턴하며 알고리즘을 종료하고,
3) value > list[middle] 인 경우, start = middle+1 로 값을 변경해준다.

위의 동작을 아래의 boundary condition에 도달할때 까지 반복적으로 수행합니다.

아래의 조건에 도달하면 알고리즘을 종료한다.
1) list[middle] = value 인 경우 원하는 값을 찾은 것이고, middle 값을 리턴해준다.
2) start > end 인 경우 원하는 값이 배열에 들어있지 않은 것이다.

 

이진 탐색을 코드로 나타내면 다음과 같습니다.

int binary_search(int list[], int value, int start, int end) {
    int middle;
    while (start <= end) {
        middle = (start + end) / 2;

        if (list[middle] > value) end = middle - 1;
        else if (list[middle] == value) return middle;
        else start = middle + 1;
    }

    return -1;
}

반복문 대신 재귀적으로도 구현할 수 있습니다.

int binary_search(int list[], int value, int start, int end) {
    int middle;
    if (start <= end) {
        middle = (start + end) / 2;
        if (list[middle] > value) return binary_search(list, value, start, middle-1);
        else if (list[middle == value) return middle;
        else return binary_search(list, value, middle+1, end);
    }
    return -1;
}

 

학교 수업에서 배운 자료를 토대로 정리하였으며, 관련된 책은 다음과 같습니다.

• Horowitz, Shani & Anderson-Freed, “Fundamentals of Data Structures in C” 2nd ed., Silicon Press, 2008

• Weiss, “Data Structures and Algorithm Analysis in C” 2nd ed. Addison Wesley, 2009