순차탐색은 쉬웠으니 빠르게 다음 공부할 이진탐색(Binary Search)에 대해서 알아보자.


이진탐색은 한번 비교를 할때마다 비교를 하는 범위가 반으로 줄어든다


이게 순차탐색과 비교해서 알마나 큰 차이가 있냐면


만약 70억개의 데이터를 검색했을때 순차탐색은 최대 70억 번 평균 35억 번을 비교 하는데 


이진탐색은 최대 33번의 비교로 탐색을 완료 할 수가 있다.


대신 조건이 하나 있는데 이진탐색에 사용하는 배열을 정렬되어진 배열이어야 한다는 것이다.



그림으로 알아보도록 하자




먼저 배열의 중앙을 선택하고 찾고자 하는 값보다 큰지 작은지 비교를 합니다.



5는 7보다 작기 때문에 5에서 오른쪽에 있는 요소들로 이동하여 


다시 그중 중앙에 위치한 값을 선택해 비교 합니다.



8은 7보다 크기 때문에 왼쪽으로 이동을 합니다


이런식으로 범위를 좁혀나가다 보면 원하는 값을 찾게 되겠죠



한번 검색을 수행할떄마다 범위가 반으로 줄어든다는 말이 이해가 되지 않는다면 


노트에 펼쳐놓고 위의 그림을 따라서 그리고 검색하지 않는 범위부터 반으로 접어 보면 이해가 갈 것이다.



이진탐색의 시간 복잡도 : O(log n) 



이진탐색의 구현 소스를 보면 생각보다 간단하다. 위에 그림에 있는 if문을 반복할 뿐이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int BinarySearch(int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1, mid;
        // low = 검색 할 범위의 가장 왼쪽
        // high = 검색할 범위의 가장 오른쪽 
 
    // high가 low보다 작아진다면 찾으려는 데이터가 데이터 집합에 없다.
    while (low <= high)
    {
        // 중앙값은 low와 high를 더한 값을 2로 나누면 된다.
        mid = (low + high) / 2;
        // 만약 찾으려는 값이 중앙값보다 작다면 high를 mid - 1로 둔다.
        // 찾는값이 중앙값보다 작기 때문이다.
        // 이때 mid-1 = 다음검색할 범위의 가장 오른쪽이 된다.
        if (dataArr[mid] > findData) high = mid - 1;
        // 만약 찾으려는 값이 중앙값보다 크다면 low를 mid + 1로 둔다.
        // 찾는값이 중앙값보다 크기 때문이다
        // 이때 mid+1 = 다음 검색할 범위의 가장 왼쪽이 된다.
        else if (dataArr[mid] < findData) low = mid + 1;
        // 중앙값과 찾으려는 값이 일치하면 mid를 반환한다.
        else return mid;
    }
    // 데이터를 찾지 못하면 -1를 반환한다.
    return -1;
}
 
int main()
{
    int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
    int length = sizeof dataArr / sizeof dataArr[0];
    int input, ret;
 
        scanf("%d", &input);
        ret = BinarySearch(dataArr, length, input); // 이진탐색 실행
        if (ret != -1) printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1);
        else printf("데이터를 찾을 수 없습니다.\n");
    
    return 0;
}
cs


(참조 http://blog.eairship.kr/246)


주석이 많아서 좀 복잡해 보이는데 주석도 빼버리면 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int BinarySearch(int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1, mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (dataArr[mid] > findData) high = mid - 1;
        else if (dataArr[mid] < findData) low = mid + 1;
        else return mid;
    }
    return -1;
}
 
int main()
{
    int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
    int length = sizeof dataArr / sizeof dataArr[0];
    int input, ret;
 
    scanf("%d", &input);
    ret = BinarySearch(dataArr, length, input); // 이진탐색 실행
 
    if (ret != -1)
        printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1);
    else 
        printf("데이터를 찾을 수 없습니다.\n");
    
    return 0;
}
cs


이런 소스가 된다.


생각보다 간단한 코드다.

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11

순차탐색이 뭐지? 하고 검색해 들어 온 사람들 대부분은 해당 내용을 보면 매우 실망할 것이다.


왜냐하면 이미 반복문을 배우면서 적어도 한번 이상은 써봤을 탐색 방법이기 때문이다.


2년동안 이 방식으로 검색을 하면서 이 알고리즘의 이름이 순차탐색 이라는 것을 난 오늘 알았다.



매우 단순하다



시간 복잡도:  최악O(n) , 평균 (n+1)/2


시간복잡도가 최악인 경우는 원하는 값이 가장 마지막에 있을 경우이다.



데이터가 배열에 있으면 배열의 처음부터 끝까지 차례대로 비교하면서 원하는 


데이터를 찾는 알고리즘이다.


이 알고리즘은 단방향으로 탐색을 하기 때문에 선형탐색(Linear Search)라고 부르기도 한다.



코드는 매우 단순하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
// for문을 돌면서 데이터를 찾는다. 찾느 데이터가 없는 경우 -1 반환
// 찾는 데이터가 있으면 해당 번째 반환
int search(int dataArr[], int length, int findData)
{
    for(int i = 0; i < length; i++)
        if (dataArr[i] == findData) return i;
    return -1;
}
 
 
 
int main()
{
    int arr[] = {23, 25, 14, 5, 66, 72, 13, 224, 51};
    int length = sizeof arr / sizeof arr[0];
    int findData = 0;
    int findIndex = 0;
 
    printf("찾으시는 데이터를 입력해주세요: ");
    scanf("%d", &findData);
 
    findIndex = search(arr, length, findData); // 
 
    if(findIndex == -1) printf("데이터를 찾지 못했습니다.\n");
    else printf("데이터는 %d번째에 있습니다.\n", findIndex);
    
 
    return 0;
}
cs



(참조 http://blog.eairship.kr/245 )




순차탐색은 코드구현이 매우 쉬워서 짧은 기리의 데이터를 검색할때 사용하는 것이 좋은 것 같다.

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11

얼마전 쿠팡에서 서류 합격 메일이 날아왔다. 구글링을 해보니 쿠팡같은 경우 서류는 거의다 통과시켜 놓고 


problem solving test를 통해서 엄청나게 걸러버리는 듯 하다.


개발자로 취직해서 일한지 2년이 가까워 지면서 웹쪽 HTML CSS JS는 많이 해봤지만


순수 자바 쪽은 거의 건들이지 않았다는 것에서 불안감이 엄청나게 느껴졌다.


학교에서 전공수업 잘 듣고 자료구조나 알고리즘 공부 열심히 했으면 붙을 수 있다고 하는데


난 전공자가 아니다;; 학교에서 기초적인걸 배우긴 했지만 자바 클래스 만들고 'Hello word' 띄우는 수준?


안드로이드로 인텐트 날려서 화면 전환하는 정도 까지만 배웠고 이론적인건 소프트웨어공학 원론쯤?


그 외엔 죄다 마케팅이나 경영, 혹은 발표과제로 점수먹는 수업이라든지 실음과 전공수업이나 들었지 ㅋ


말하자면 전공이라기 보단 반공(?)이라고 말하는게 어울릴 듯 하다.



아무튼 자료구조는 스택과 큐밖에 모르고 정렬 알고리즘은 버블정렬 밖에 모르는 상태에서


어렵다고 소문난 쿠팡 테스트를 통과하려면 짧은 시간동안 공부를 많이 해야 겠다 싶었다.


면접 후기라던지 자료구조 기초라던지 알고리즘을 어떻게 공부해야 하는지 찾아 보면서


퀵정렬이라는 것이 있다는걸 태어나서 어제 처음 알게 되었다.



버블정렬만 있으면 만사 오케이인줄 알았고 심지어 프로젝트중에선 DB에서 불러올때 ORDER BY만 떄려버리면 해결이니


정렬 알고리즘을 사용할 필요성도 못느끼고 있었는데....  좀 충격이었다.



심지어 아래 동영상을 보고 가장 먼저 들었던 생각은


"버블정렬 개쓰레기였네??"


일단 정렬의 종류는 여러가지 있는데 아래 영상을 보도록 하자. 가운데 표시된 퀵정렬이 대체로 가장 빠른 결과를 보여준다. <출처: Viktor Bohush, 유튜브>






그리고 퀵정렬에 대해서 좀더 큰화면으로 보자면 <출처: Timo Bingmann / 유튜브>




이렇게 보여질 수 있다.



해당 내용을 직접 포스팅 하려 해보았으나 알고리즘이나 기초지식이 1도 없는 상태에서 이해 할 수 있는 포스팅 만드는데


시간이 너무 오래 걸린다. 퀵정렬이 무엇인지 이곳 저곳 둘러보던중


아주아주아주 설명을 잘 해놓은 게시글을 발견했다.


허접하게 내가 만드는 것 보다는 정말 잘 만든 다른사람의 글을 보는 것이 더 나을 것이라고 판단 했다.



http://navercast.naver.com/contents.nhn?rid=2871&contents_id=90163


위 주소로 들어가보면 퀵정렬에 대해 아주 잘 설명해 놓은 글이 있다.


한번 쭉 읽어 보고 이해가 좀 되겠다 싶다면 슈도코드 부분은 스킵하고 다음 소스를 보도록 하자



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
public static int partition(int arr[], int left, int right) {
 
    int pivot = arr[(left + right) / 2];
 
    while (left < right) {
        while ((arr[left] < pivot) && (left < right))
            left++;
        while ((arr[right] > pivot) && (left < right))
            right--;
 
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
 
    return left;
}
 
 
public static void quickSort(int arr[], int left, int right) {
 
    if (left < right) {
        // 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
        int pivotNewIndex = partition(arr, left, right);
        // quick sort의 설명중
        // 자주 나오는 '재귀', '분할' 이라고 설명되어지는 부분이다.
        quickSort(arr, left, pivotNewIndex - 1);
        quickSort(arr, pivotNewIndex + 1, right);
    }
 
}
 
// 
public static void main(String[] args) {
    int[] arrs = { 69, 10, 30, 2, 16, 8, 31, 22 };
    quickSort(arrs, 0, arrs.length - 1);
    System.out.println("결과");
 
    for (int i : arrs) {
        System.out.print(i + " ");
    }
}
cs


<참조: http://creatordev.tistory.com/70>



처음 올린 링크의 글을 정독했다면 위 소스를 보면서 직접 소스를 디코딩 해보도록 하자.

소스의 처음부터 정렬이 종료될때까지 직접 소스를 따라가면서 정렬을 해보는 것이 이해하는데 가장 큰

도움이 될 것이다.



요즘 웹쪽엔 내가 아는 지식이 후달려서 더 포스팅하기 힘들었는데 노드js나 리엑트js 해보기 전까진


자료구조와 정렬에 대해서 포스팅을 해봐야 겠다. 나에게도 큰 도움이 되는듯 하다.

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18

+ Recent posts

티스토리툴바