ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 3.1 알고리즘 탐색과 정렬
    Discrete mathmatics and Problem Solving/3 알고리즘 2017. 10. 1. 16:14

    이전글 보기 알고리즘 Introduction + 알고리즘의 특징

    http://ingyeoking13.tistory.com/75

    Contents

    탐색알고리즘 (순차탐색, 이진탐색)
    정렬알고리즘 (버블정렬, 삽입정렬)


    탐색 알고리즘Searching Algorithms

    정렬된 리스트에서 어떤 원소를 찾는 문제는 많은 상황에서 발생합니다. 예로, 사전같이 순서대로 정렬되어있는 단어 리스트들 중에서 단어 탐색을 하기위해 스펠링을 체크하는 프로그램이 있습니다. 이런 류의 문제들은 탐색 문제searching problems 입니다. 

    <정렬되어있는 단어에서 특정 단어 찾기. 어려워지려면 충분히 어려울 수 있는 문제다.>


    우리는 이 섹션에서 탐색을 위한 몇 몇 알고리즘들에 대해 논의할 것입니다. 
    일반적인 탐색 알고리즘은 다음과 같이 서술될 수 있습니다. 각 각 다른 원소들 a1, a2, .... , an 의 리스트에 존재하고 있습니다. 그리고 탐색 알고리즘은 원소 x의 위치를 찾거나 또는 리스트에 없다는 것을 확인할 것입니다. 이 탐색 문제의 결과값은 x와 같은 리스트 내의 원소 위치가 되거나 x가 리스트에 없다면 0 (또는 -1) 이 됩니다.


    선형 탐색THE LINEAR SEARCH


    우리가 볼 첫 번째 알고리즘은 선형 탐색linear search 또는 순차 탐색sequential search 입니다. 선형 탐색 알고리즘linear search algorithm은 x와 a0을 비교하는 것 부터 시작합니다. x==a0이라면, 정답은 이름그대로 a0의 위치가 될 것입니다. x!=a0 일 때, x는 a1와 비교합니다. x==a1일 땐, 정답은 a1의 위치가 됩니다. x!=a1일 때, x는 a2와 비교합니다. 이 프로세스를 계속하여, x는 계속적으로 리스트 내에 같은 것이 발견될 때까지 각 항과 비교합니다. 여기서 정답은 같은 것이 발견되지 않는 이상 같은 항의 위치가 됩니다. 만약 x를 발견하지 못하고 리스트 내에 모든 원소들과 비교를 끝마쳤다면, 정답은 -1이 됩니다. 선형 탐색linear search 알고리즘은 다음과 같습니다.

    procedure linbear search(x: integer, a0, a2, ... ,an-1: distinct integers)
    i = 0
    while (i<n and x!=ai)
    i = i + 1
    if i<n then location = i
    else location := -1
    return location{location is the subscript of the term that equals x, or is -1 if x is not found}

    //implementation in c
    int i=0;
    while (i<n && a[i]!=x) i++;
    if i<n return i;
    else return -1;

    <C의 순차탐색 구현>


    이진 탐색THE BINARY SEARCH


    이제는 다른 탐색 알고리즘을 알아볼것입니다. 이 알고리즘은 리스트의 항들이 정렬 되어있을 때 사용할 수 있습니다. (만약 각 항들이 숫자라면, 가장 작은 수부터 큰 수까지 정렬 또는 그 반대. 만약 단어인 경우, 사전순 또는 철자 순으로 정렬 또는 그 반대.) 
    이 두번째 탐색 알고리즘은 이진 탐색 알고리즘binary search algorithm 이라고 불립니다. 이 알고리즘은 원소들을 비교하여 리스트의 중간 항에 놓으면서 진행됩니다. 리스트는 그러면 두 개의 서브리스트들로 나뉘게되며 이 두 서브리스트는 같은 크기거나, 한 쪽이 다른 하나 보다 하나 작은 크기를 가지게 됩니다. (리스트 내의 원소들 개수가 짝수이거나 홀수 일 때에 따라) 이 탐색 알고리즘은 찾아야할 원소들을 비교하면서 생기는 적절한 서브리스트내로 탐색을 제한해나가면서 탐색을 계속합니다. 3.3 쯤의 포스팅에서는, 이진 탐색 알고리즘이 선형 탐색 알고리즘보다 훨씬 효율적임을 볼 것입니다. 

    다음 예제 3은 이진 탐색이 어떻게 동작하는지 보여줍니다.

    예제 3
    리스트내에서 19를 찾아보자.

    1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
    먼저 리스트를 분할합니다, 16항을 가진 이 리스트는 각각 8개의 서브리스트들로 나뉩니다.

    1 2 3 5 6 7 8 10        12 13 15 16 18 19 20 22
    그리고 19와 첫 번째 리스트의 가장 큰 항과 비교합니다. 10 < 19 이기 때문에, 19를 탐색할 땐 두 번째 리스트의 첫 번째부터 마지막까지 즉, 9번째항부터 16항까지로 범위를 제한할 수 있습니다. 그 다음 이 8항의 리스트를 각각 4항의 서브리스트로 분할합니다. 

    12 13 15 16        18 19 20 22
    19와 첫 번째 리스트의 가장 큰 수와 비교합니다. 16<19 이기에 탐색은 두 번째 리스트의 서브리스트로 제한됩니다. 즉, 원래 리스트의 13번째 원소에서부터 16번째 원소까지로 제한됩니다. 리스트 18 19 20 22 는 두 서브리스트로 분할됩니다.

    18 19        20 22
    19는 두번째 리스트의 첫 번째 원소보다 크지 않기 때문에, 탐색은 첫 번째 리스트로 제한됩니다. 18, 19는 원래 리스트의 13, 14번째 원소입니다. 다음으로, 두 항의 리스트는 두 서브리스트로 분할됩니다.

    18        19
    18<19이기 때문에, 탐색은 두 번째 리스트로 제한됩니다. 두 번째 리스트는 원래 리스트의 14번째 원소 19를 포함하고있습니다. 탐색은 한 항으로 좁혀졌으며, 비교가 수행됩니다. 그리고 19가 리스트의 14번째 항임을 찾을 수 있습니다.

    <적은 비교만으로 많은 수의 항들을 제외할 수 있다.
     첫 비교에서는 무려 8개의 항을 후보에서 제외한다.>


    이제 우리는 이진 탐색 알고리즘의 단계들을 정의해야합니다. 리스트 a[0], a[1], ... ,a[n-1] (단, a[0]<a[1]<...<a[n-1])에서 정수 x를 찾기 위해서는, x를 리스트의 중앙 항 a[m]과 비교해야합니다. 여기서 am = ⌊(n+1)/2⌋ 입니다. (⌊x⌋는 x를 넘지않는 가장 큰 정수입니다.) 만약 x > a[m]이면, x 탐색은 두 번째 서브리스트로 옮겨갑니다. 이 서브리스트는 a[m+1], a[m+2], ..., a[n-1] 로 구성되어있습니다. 만약 x가 a[m]보다 크지 않다면, 탐색은 첫 번째 서브리스트로 제한되고, 이 서브리스트는 a[0], a[1], ... ,a[m]로 구성되어있습니다.
    이제 탐색은 ⌈n/2⌉개의 엘리먼트들로 제한됩니다.(⌈x⌉는 x보다 큰 가장 작은 큰 정수이거나 같은 정수입니다.) 이후에도 같은 절차를 이용하여, x를 제한된 리스트의 중간항과 비교합니다. 그 뒤 탐색은 첫번째 또는 두번째 리스트로 제한됩니다. 이 프로세스는 한 항만 남을 때까지 반복합니다. 그리고 남은 항이 x와 같은지 비교합니다. 이진 탐색 알고리즘의 스도코드는 다음과 같습니다.

    procedure binary search (x: integer, a[0], a[1], ..., a[n-1]: increasing integers)
    i = 0{i is left endpoint of search interval}
    j = n-1{j is right endpoint of search interval}
    while i<j
    m = ⌊(i+j)/2⌋
    if x > a[m] then i = m+1
    else j = m
    if x==a[i] then location = i
    else location = -1
    return location{location is the subscript i of the term ai equal to x, or 0 if x is not found}

    //implementation in C
    int l=0, r=n-1;
    while (l<r){
    int m= (l+r)/2;
    if (x >a[m]) l=m+1;
    else r=m;  
    }
    if (x==a[l]) return l;
    return -1;

    <같은 알고리즘이더라도 표현법이 다를 수 있다. 다른 만큼 디테일한 면에서 차이가 나기도한다.
    위 두 코드는 어디서 다를까? 아래의 코드는 다음 서브리스트 18 19 20 22 에서 break가 걸린다. >


    위 알고리즘은 점차점차 탐색하는 수열의 범위를 좁혀가면서 진행합니다. 매 단계는 a[l]에서 a[r]까지의 항들만 고려합니다.  다르게 표현하면, l과 r은 남아있는 항들 중에 가장 작고 가장 큰 항입니다. 결과적으로 위 알고리즘은 한 항만 남을때까지 수열의 범위를 좁혀갑니다. 이를 수행했으면, 남은 한 항이 x와 같은지 확인합니다.


    정렬Sorting

    리스트 내의 엘리먼트들을 순차적으로 정렬하는 일은 많은 경우에 발생합니다. 예로, 연락처를 제공하려면 사람들의 이름을 글자 순서대로 정렬하는 것이 중요합니다. 비슷하게, 다운로드 가능한 노래 디렉토리를 제공할 때에도 노래 제목들을 글자 순서대로 나열하는 것이 필요합니다. e-mail 리스트에 주소를 글자 순서대로 놓으면 주소가 중복되는지 확인할 수 있습니다. 사전을 만들 때는 글자 순으로 정렬하는 것이 필요합니다. 유사하게, 부품 리스트를 만들 때 부품번호를 증가 순으로 정렬하는 것이 필요합니다.

    어떤 집합의 원소들로 이루어진 리스트를 우리가 가지고 있다고 가정합시다. 또, 집합의 원소들을 정렬하는 방법이 있다고 가정합니다. 정렬sorting은 이런 엘리먼트들을 증가 순으로 정렬하는 것입니다. 예로, 리스트 7, 2, 1, 4, 5, 9 를 정렬하면 리스트 1, 2, 4, 5, 6, 7, 9. 를 얻을 것입니다. 다음 리스트 d, h, c, a, f를 글자 순으로 정렬하면 a, c, d, f, h를 얻을 수 있습니다.

    연산에 필요한 자원computing resources들의 굉장한 부분이 어떤 것들을 정렬하는데에 사용됩니다. 따라서, 효율적인 정렬 알고리즘을 개발하는데 상당한 노력들이 들었습니다. 각기 다른 방법을 이용하는 굉장한 수의 정렬 알고리즘이 고안되어왔습니다. Donald Knuth는 자신의 저서 , The Art of Computer Programming 에서 탐색에 관해 400 페이지에 달하는 분량을 각기 깊이가 다른 15가지의 정렬에 대해 서술했습니다. 이제까지 100 가지가 넘는 정렬 알고리즘들이 고안되었으니 얼마나 빈번하게 정렬 알고리즘이 개발되는지 놀랍기도 합니다. 가장 새로운 정렬 알고리즘은 2006년에 개발된 gapped insertion sort (library sort라고도 알려짐)입니다. 

    컴퓨터 과학자들과 수학자들이 정렬 알고리즘에 흥미를 느끼는 것엔 다양한 이유가 있습니다. 이런 이유들 중에 어떤 알고리즘이 구현하기 쉬운지, 어떤 알고리즘이 어떨 때 더 효율적인지 (일반적인 input의 경우일 때, 또는 조금 조금씩 순서가 어긋나있는 것처럼의 어떤 특징을 가지는 input이 주어졌을 때의 경우), 어떤 알고리즘이 특정 컴퓨터 아키텍쳐(컴퓨터 설계 구조)상 유리한지, 어떤 알고리즘이 뛰어나게 기발한지 등등이 있습니다.

    이 섹션에서는 두 가지의 정렬 알고리즘에 대해 이야기해볼 것입니다. 버블 정렬bubble sort와 삽입 정렬insertion sort입니다. 우리는 우선 두 정렬 알고리즘을 다룰겁니다. 왜냐하면 이 정렬 알고리즘은 중요하고 다양한 중요 개념들의 예제로 사용할 수 있기 때문입니다.

    // 또 다른 두 정렬 알고리즘, 선택 정렬selection sort 와 이진 삽입 정렬binary insertion sort는 예제 문제에서 다뤄집니다. 그리고 보충 예제 문제에서는 칵테일 셰이커 정렬shaker sort이 다뤄집니다. 섹션 5.4에서는 병합 정렬merge sort와 퀵 정렬quick sort가 예제로 나옵니다. 토너먼트 정렬tournament sort는 섹션 11.2에서 다뤄집니다. //

    버블 정렬BUBBLE SORT

    버블 정렬bubble sort은 가장 간단한 정렬 알고리즘입니다. 하지만 가장 효율적인 알고리즘은 아닙니다. 버블 정렬은 인접한 엘리먼트들을 차례차례로 비교하며, 만약 증가순으로 되어있지 않다면 자리를 바꿔가며 증가순으로 정렬합니다. 

    버블 정렬을 수행하기 위해서는, 다음과 같은 기본적인 동작을 수행해야합니다. 상대적으로 큰 엘리먼트를 뒤에 따라오는 작은 엘리먼트의 자리와 바꿔가며, 리스트의 처음부터 시작하여 리스트 끝까지 수행합니다. 우리는 이 진행을 정렬이 다 될 때까지 이 절차를 반복합니다. 

    <버블 정렬의 기본적인 동작, 인접한 원소를 비교하고 큰놈을 위로 올린다. (오름차순인 경우)>


    리스트에 한 열마다 위치하고 있는 엘리먼트들을 상상해봅시다. 버블 정렬에서는, 작은 원소들이 큰 원소들과 자리를 바꿔가면서 마치 거품이 위로 떠오르는 것 같습니다. 큰 원소들은 아래로 가라앉는 것 처럼 보입니다. 다음의 예제에서 이를 확인할 수 있습니다

    예제 4

    버블 정렬을 이용하여 3, 2, 4, 1, 5를 증가 순으로 정렬해보자.


    알고리즘의 단계는 위 그림으로 확인할 수 있습니다. 맨 처음 두 엘리먼트들을 비교합니다. 3과 2입니다. 3>2 이므로, 3과 2의 자리를 바꿉니다. 리스트는 2, 3, 4, 1, 5가 됩니다. 3 < 4 이므로 4 와 1을 비교합니다. 4> 1 이므로 1과 4의 자리를 바꿉니다. 리스트는 2, 3, 1, 4, 5가 됩니다. 4<5가 되므로 첫번째 진행이 완료됩니다. 두번째 진행은 2와 3을 비교하면서 시작됩니다. 순서가 옳으므로, 3과 1을 비교합니다. 3>1이므로 1과 3의 자리를 바꾸면서 리스트 2, 1, 3, 4, 5를 만듭니다. 그다음 3과 4를 비교하며 옳으므로 자리를 바꾸지 않습니다. 이 이상의 엘리먼트들에 대한 비교는 필요하지 않습니다. 왜냐하면 5는 이미 첫번째 진행으로 인해 정상 위치에 존재하고 있기 때문입니다. 이제 두번째 진행을 마침으로써 가장 큰 두 엘리먼트들이 오름차순으로 정렬했을 때 옳은 자리에 있다고 보증할 수 있습니다. 세번째 진행은 2와 1을 비교하면서 시작합니다. 2>1이므로 교환을 수행하며 리스트 1,2,3,4,5를 만듭니다. 2와 3을 비교하고 자리를 바꿀필요가 없습니다. 이 이상의 비교는 필요없습니다. 왜냐하면 두번째 진행까지 우리는 4와 5가 제자리에 있음을 이미 확인했기 때문입니다. 세번째 진행은 가장 큰 세 원소들이 옳은 자리에 있음을 보장하면서 끝납니다. 네번째 진행은 단 한개의 비교로 구성됩니다. 1과 2를 비교합니다. 1<2이므로, 이 엘리먼트들은 제자리에 있음을 확인합니다. 이로써 버블정렬은 끝납니다.


    procedure bubblesort(a[0], ... a[n-1]: real numbers with n≥2)

    for i = 0 to n-2

    for j = 0 to n-i-1

    if a[j] > a[j+1] then interchange a[j] and a[j+1]

    return {a[0]... , a[n-1] is in increasing order}


    <두 종류의 버블정렬, 위는 큰녀석을 리스트 젤 위로 갔다 놓고 그 것과의 비교를 제외하는 버블정렬
    아래는 작은 녀석을 리스트 젤 아래로 갔다놓고 그 것과의 비교를 제외하는 버블정렬이다.>


    삽입 정렬THE INSERTION SORT


    삽입 정렬은 간단한 정렬 알고리즘입니다. 하지만 효율적인 알고리즘은 아닙니다. n개의 엘리먼트들을 정렬하기 위해, 삽입정렬은 두번째 엘리먼트부터 시작합니다. 삽입정렬은 이 두번째 엘리먼트를 첫번째 엘리먼트와 비교하여 첫번째 엘리먼트보다 큰지 확인합니다. 이 때, 처음과 두번째 엘리먼트는 옳은 순서가 됩니다. 세번째 엘리먼트는 첫번째 엘리먼트와 비교하여 첫번째 엘리먼트보다 큰지 확인하고 그렇다면 두번째 엘리먼트와 비교합니다. 이로써 세번째 엘리먼트는 처음 세 엘리먼트들 가운데에 옳은 자리에 들어갑니다.

    일반적으로, 삽입정렬의 j번째 단계는, j번째 엘리먼트를 이전까지 잘 정렬된 j-1번째 엘리먼트들 사이에서 옳은 자리를 찾는 동작을 수행합니다. j번째 엘리먼트를 리스트에 삽입하기 위해서는, 선형 탐색기법이 사용됩니다. (43번째 예제를 확인하세요). j번째 엘리먼트는 차례차례 잘 정렬된 j-1번째 엘리먼트까지 리스트의 처음부터 이 엘리먼트보다 작지 않은 엘리먼트를 찾을때까지 또는 모든 j-1 엘리먼트들을 비교할 때까지 수행합니다. j번째 엘리먼트는 적절한 자리에 위치하게되며 처음부터 j번째 엘리먼트들 까지 정렬됩니다. 알고리즘은 마지막 엘리먼트가 이미 정렬된 n-1 개의 엘리먼트들의 리스트과 비교하여 옳은 자리에 위치할 때까지 계속됩니다. 삽입정렬은 다음의 스도코드 알고리즘5와 같습니다.

    예제 5

    삽입정렬을 이용하여 다음의 리스트 3, 2, 4, 1, 5를 증가순으로 배치하세요.

    삽입정렬은 먼저 2와 3을 비교합니다. 3>2이므로, 2를 첫번째 위치로 놓습니다. 따라서 리스트는 (2, 3), 4 1, 5가 됩니다. (괄호는 이미 정렬된 리스트를 뜻합니다.) 이 때 2와 3은 옳은 순으로 되었습니다. 그다음 세번째 엘리먼트인 4를 4>2와 4>3 비교를 수행하면서 정렬된 리스트에 삽입합니다. 4>3이므로, 4는 그대로 세번재 자리에 위치하게됩니다. 이때 (2, 3, 4), 1, 5가 되며 처음부터 세번째 엘리먼트들의 순서가 옳다는 것을 알았습니다. 그다음 네번째 엘리먼트 1을 옳은 자리에 놓기위한 작업을 수행합니다. 이미 정렬된 엘리먼트들 2, 3, 4 사이로 말입니다. 1<2이므로, 우리는 다음 리스트 (1,2,3,4),5 를얻습니다. 마지막으로 우리는 5를 이미 정렬된 1,2,3,4 리스트 내의 원소들과 차례차례 비교합니다. 5>4이므로, 리스트의 마지막에 원래 그대로 위치하게되며, 전체적으로 오름차순인 리스트를 제공합니다.

    procedure insertion sort(a[0], a[1], ..., a[n-1]: real numbers with n≥2)
    for j = 1 to n-1
    i = 0
    while a[j] > a[i]
    i = i + 1
    m = a[j]
    for k = 0 to j-i-1
    a[j-k] = a[j-k-1]
    a[i] = m
    return {a1, a2, ... ,an is in increasing order}
     

    <삽입 정렬 이해와 구현>

    댓글 0

Designed by Tistory.