C/C++ 2진 탐색(Binary Search) 예제 코드

알고리즘 2018. 5. 24. 22:04

이진탐색(2진탐색)은 정렬된 데이터에서 원하는 데이터를 빠르게 찾는 방식이다.


예를들어 1부터 100까지 숫자가 있다면 75를 찾아 보자.


일반적인 방식은 1부터 하나하나 데이터를 비교해가며 찾아야 한다.


O(N)에 복잡도를 가진다.


하지만 2진탐색을 사용하면 가장 중간데이터인 50부터 찾아서 비교해보고 50보다 찾아야 할 데이터인 75보다 작다.


그래서 50보다 큰수이기 때문에 50과 가장끝 데이터인 100중 가장 중간 데이터인 75를 비교해본다.


이렇게 중간데이터를 가지고 대소비교를 해가면서 데이터를 찾으면 


O(logN) 의 복잡도를 가진다.


훨씬 빠른 데이터 탐색을 할 수 있다.


코드 구현역시 간단한 편이다.




아래는 이진탐색 예제 코드이다.


아래와 같이 반복문을 가지고 시작과 끝부분의 데이터를 바꿔가며 찾는 방식이 있으며 재귀함수로도 구현이 가능 하다.


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
#include<stdio.h>
 
//size 크기의 data배열안에서 d를 찾기
//값이없으면 -1반환
//값이 있으면 data배열의 index 반환
int binarySearch(int data[], int size, int d)
{
    int s = 0; //시작
    int e = size - 1; //끝
    int m;
    while (s <= e) {
        m = (s + e) / 2;
        if (data[m] == d) return m;
        else if (data[m] > d) e = m - 1;
        else s = m + 1;
    }
    return -1;
}
 
int main() {
    int data[] = { 1,3,6,8,11,23,111,114,213 };
    int dataSize = sizeof(data) / sizeof(int);
    int ans = binarySearch(data, dataSize, 114);
    printf("%d\n", ans);
}
 
cs

저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
1부터 n까지 합계 함수(for와 재귀)  (0) 2018.03.30
Posted by 꿈만은공돌
,

C/C++ 병합정렬(Merge Sort) 코드

알고리즘 2018. 5. 24. 21:44


병합정렬 위키 링크 


병합정렬은 O(NlogN) 에 시간복잡도를 가진다.

1,000 개의 데이터를 정렬 한다면 1,000 X log1,000 = 1,000 X 10 = 10,000 이다.

만약 1,000,000개의 데이터를 정렬 한다면 1,000,000 X log1,000,000 = 1,000,000 X 20 = 20,000,000 이다.

2천만으로 1ms정도 안에 처리가 가능한 수준이다.


버블 정렬이나 선택정렬 등은 O(N^2) 의 시간 복잡도를 가진다. 

1,000개의 데이터를 정렬 한다면 1,000 X 1,000 = 1,000,000 이 된다.

1,000,000개의 데이터를 정렬 한다면 1,000,000 X 1,000,000 = 1,000,000,000,000 이다.

1조나 되기때문에 1ms에 처리가 불가능 하다.

 

데이터에 숫자가 많으면 버블 정렬에 비해 속도가 엄청 빠르다.

하지만 임시 메모리를 두고 데이터를 복사해야하기 때문에 메모리 사용이 버블 정렬에 비해 크다.


데이터의 갯수가 1,000 개 수준이라면 버블 정렬을 이용해도 되지만 그 이상 만개가 된다면 병합정렬이나 퀵정렬을 고려해보아야 한다.




퀵정렬에 비해 병합정렬은 코드가 간단해서 구현하기가 쉬운편이고 퀵정렬에 비해 속도가 안정적이다.


병합정렬은 데이터를 반씩 쪼개서 반씩 정렬을 하는 방식이다.


4 1 2 3 을 오름차순 정렬 한다고 하면


4 과 1를 정렬하면 1 4 가 되고 

2와 3을 정렬 하면 2 3 이된다.

1 4 와  2 3을 정렬 하는데

각각 앞에서 부터 정렬을 시작한다.

1과 2를 비교하여 1이 작기 때문에 1을 넣고 그다음 4와 2를 비교하여 2가 작기 떄문에 1 2 로 저장하고

4와 3을 비교하여 3이 작기 때문에 1 2 3 이되고 마지막 4를 추가하여 1 2 3 4 가 된다.


모든 경우를 비교하지 않기때문에 속도가 빠르다.


기본적으로 병합정렬은 재귀함수로 구현한다.


반으로 쪼개서 다시 재귀함수로 호출하고


호출한 결과를 가지고 정렬을 한다.


이걸 계속 반복하는 방식이다.


- 바로 쓸 수 있는 병합 정렬(Merge Sort) 코드 오름차순 정렬 -


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e)/2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m+1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}
cs


- 실제 사용 예제 -


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
#include<stdio.h>
void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e) / 2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m + 1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}
 
int main() {
    int data[] = { 1,5,2,4,3,7,-1,10,6 };
    mergeSort(data, 0, sizeof(data) / sizeof(int)-1);
    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}
cs



저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
1부터 n까지 합계 함수(for와 재귀)  (0) 2018.03.30
Posted by 꿈만은공돌
,

분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘

알고리즘 2018. 4. 2. 21:15

1부터 n까지 합을 구하는 방법을 for문으로 하는 방식과 단순 재귀함수를 이용하는 방식을 이전 블로그(http://hijuworld.tistory.com/3)에서 다뤘는데 이번에는 분할 정복 방식을 이용해서 구하는 함수에 대해서 알아 보겠습니다.



1
2
3
4
5
6
7
8
int divSum(int n) {
    if (n == 1)
        return 1;
    if (n % 2 == 1)
        return divSum(n - 1) + n;
    else
        return divSum(n / 2)*2 + (n / 2)*(n / 2);
}
cs


1부터 n까지 합을 반으로 쪼개면 다음과 같습니다.

뒷부분에 공통적으로  이 개 존재합니다. 이를 하나로 묶으면


 이 공통적으로 존재하기 때문에 하나로 묶으면 아래와 같이 정리가 됩니다.





앞부분  은 처음 구하려고 한 1 부터 N까지에  절반인 1부터  까지의 합니다.


그래서 아래와 같은 점화식을 구할 수 있습니다.





해당 점화식을 코드로 옮긴 것은 위의 코드 입니다.


해당 함수의 빅오는  와 같습니다.

for문을 이용해서 합을 구하는 방식은 O(n) 입니다.

아래 코드를 가지고 테스트를 해보면 해당 분할 정복 방식이 코드는 복잡해 보이지만 속도 면에서는 월등히 압서는 것을 볼 수 있습니다.


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
46
47
48
49
50
51
#include <iostream>
#include <time.h>
using std::cout;
using std::endl;
 
int divSum(int n)  //분할 정복 방식
{
    if (n == 1)
        return 1;
    if (n % 2 == 1)
        return divSum(n - 1) + n;
    else
        return divSum(n / 2)*2 + (n / 2)*(n / 2);
}
int forSum(int n) // for 이용 방식
{
    int sum=0;
    for (int i = 1; i <= n; i++)
        sum += i;
    return sum;
}
int main() {
    clock_t start, end;
    double result;
    //분할 정복 방식
    start = clock(); 
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    end = clock(); 
    result = (double)(end - start);
    printf("분할정복 시간 측정 : %f\n", result);
 
    //for문 이용방식
    start = clock();
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    end = clock();
    result = (double)(end - start);
    printf("for 시간 측정 : %f\n", result);
    return 0;
}
cs


-실행 결과 - 

분할정복 시간 측정 : 0.000000

for 시간 측정 : 2746.000000

계속하려면 아무 키나 누르십시오 . . .


측정 결과를 보면 분할정복 방식은 1ms 미만이라 0으로 나오며 for문을 이용한 방식은 2746ms로 시간차이가 많이 나는 것을 알 수 있습니다.


많은 양의 숫자를 더할때는 분할 정복을 이용하는 것을 추천 합니다.



참고 서적 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (저자 구종만 지음, 인사이트 출판)


'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
1부터 n까지 합계 함수(for와 재귀)  (0) 2018.03.30
Posted by 꿈만은공돌
,

티스토리툴바