자료구조 개요, 알고리즘 성능 분석법, 이진탐색 알고리즘

프로그램이란 데이터를 표현하고, 표현된 데이터를 처리하는 것.

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  // 자료구조화, 데이터의 표현에 저장의 의미가 포함(int형 변수 선언이나, 배열 선언 등)

for(idx=0; idx<10; idx++)  // 배열에 저장된 값의 합을 구하기 위한 알고리즘 측면의 코드

sum += arr[idx];

: 자료구조에 따라 이를 위한 알고리즘은 달라지며, 따라서 알고리즘은 자료구조에 의존적이다.

먼저 자료구조를 결정하고, 이에 대한 효율적 알고리즘을 짜는 것이다.

알고리즘의 성능분석 방법

처리해야 할 데이터의 수 n에 대한, 연산횟수의 함수 T(n)을 가지고 식을 구성

데이터를 처리할 양이 많을 때, 로그식과 같은 알고리즘이 가장 이상적일 것이다.

시간복잡도 : 어떤 알고리즘이 어떠한 상황에서 더 빠르고 느린가

공간복잡도 : 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰거나 많이 쓰는가

알고리즘을 평가할 때는 속도에 대한 것을 우선으로 둔다. 이는 c언어의 입문 과정에서도 배운 내용이다.(공간 최적화와 속도 최적화) 

알고리즘 A와 B를 비교하면 데이터의 수가 적을 땐 B가 더 빠르지만, 일정 데이터 수 이후에는 A가 빠름을 알 수 있다.

하지만 데이터의 수가 적을 때의 시간 차는 미미하기 때문에 보통은 A를 좋은 알고리즘이라 한다.

다만, 구현이 쉽고 데이터의 수가 적을 때는 알고리즘 B를 쓰는 경우도 있다. 선택은 프로그래머의 몫이다.

시간 복잡도의 평가

: 중심이 되는 특정 연산의 횟수를 먼저 구하고, 

데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

순차 탐색 예제

#include <stdio.h>

int LSearch(int ar[], int len, int target) // 순차탐색 함수(배열, 길이, 타겟)

{

int i;

for(i=0; i<len; i++)

{

if(ar[i]==target)

return i;    // 찾은 대상의 인덱스 값 반환

}

return -1;    // 찾지 못했음을 의미하는 값 반환

}

int main(void)

{

int arr[]={3, 5, 2, 4, 9};

int idx;

idx=LSearch(arr, sizeof(arr)/sizeof(int), 4);

if(idx==-1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d \n", idx);

idx=LSearch(arr, sizeof(arr)/sizeof(int), 7);

if(idx==-1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d \n", idx);

return 0;

}

결과: 

타겟 저장 인덱스: 3

탐색 실패

순차 탐색 알고리즘에서 최악의 경우, 시간 복잡도    

: 최악의 경우 마지막 인덱스에서 찾거나 타켓 탐색에 실패할 수 있다.

여기서 중심이 되는 특정 연산은 ==이고 <와 ++은 이에 의존적이다.

따라서 최악의 경우 t(n)=n 이 된다.

평균적인 경우를 구하는 것은 예상하거나 증명하는 것이 쉽지않고 일정한 상황이 아니기 때문에, 

"일반적으론" 최악의 경우를 구하는 것이다.

이진탐색 알고리즘 구현

길이가 9인 배열 정의. 

배열 인덱스의 시작과 끝은 각각 0과 8이다. (arr[0]~arr[8])

이를 오름차순을 기준으로 정렬한다.

{1, 2, 3, 7, 9, 12 , 21, 23, 27}

탐색 대상은 3.

0과 8을 합하여 그 결과를 2로 나눈다. 

결과 인덱스 4, 즉 가운데 인덱스를 기준으로 우리가 찾고자하는 값이 왼쪽 또는 오른쪽 배열에 있는지 확인하다. 

오름차순이기 때문에 어느 매개를 탐색대상으로 해야하는지 분명해진다.

{1, 2, 3, 7, 9, ...}

인덱스4의 숫자는 9이고, 우리가 찾는 대상보다 큰 값이기 때문에 탐색 대상은 왼쪽의 0~3 인덱스로 제한된다.

0과 3을 합하여 그 결과를 2로 나눈다. 1이 나오고 나머지는 버려짐

인덱스 1에 숫자 3이 있는지 확인한다. 숫자 2가 확인

 arr[1] < 3이므로 아래와 같이 인덱스 2,3으로 탐색이 제한된다.

{1, 2, 3, 7, 9, ...}

2와 3을 더하고 다시 2로 나눈다. 몫이 2가 나온다.

인덱스2의 숫자가 3인지 확인.

탐색 끝.

 

이진 탐색 알고리즘은 매 과정마다 탐색 대상을 절반으로 줄여나간다. 

기준을 가지고 정렬해야 하는 대신에  순차 탐색에 비해 좋은 성능을 보이며, 이는 이 알고리즘의 단점이자 장점이다.