2016-04-28_조재찬_스터디일지_자료구조

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

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인지 확인.

탐색 끝.

 

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

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

이진 탐색 알고리즘에서 검색의 범위는 다음과 같이 좁혀짐을 알 수 있다.

(first가 오른쪽, last가 왼쪽으로 이동하며 탐색 범위를 좁혀감)

first와 last가 만나면 탐색 대상이 하나남았다는 것이고

서로 역전되면 탐색대상을 찾지못했다는 뜻이 된다.

이를 소스로 옮기면, 다음과 같이 while문의 조건이 필요할 것이다.

while(first <= last)

{

}

탐색 과정

1. 탐색 대상의 중앙을 찾음 // mid = (first + last) / 2;

2. 중앙 인덱스에 탐색 대상이 있는지 확인, 찾으면 값을 반환

찾지 못하면, 대소비교

3. 대소비교 결과에 따라 왼쪽 또는 오른쪽 인덱스들을 버림

last=mid-1;   

first=mid+1;    

여기서 -1과 +1을 해주는 이유는 아래 그림을 보고 한정되는 탐색대상을 보면 알 수 있다.

하지만 더 큰 이유는 -1,+1을 해주지않으면 탐색대상을 찾지 못하는 경우에 무한 루프에 빠지기 때문이다.

(first <= mid <= last가 성립)

이진 탐색 소스

#include <stdio.h>

int BSearch(int ar[], int len, int target)

{

int first=0;   // 탐색 대상의 시작 인덱스 값

int last=len-1;   // 탐색 대상의 마지막 인덱스 값

int mid; 

while(first<=last)

{

mid=(first+last)/2;   // 탐색 대상의 중앙을 찾는다. 

if(target==ar[mid])   // 중앙에 저장된 것이 타겟이라면

{

return mid;

}

else    // 타겟이 아니라면 

{

if(target<ar[mid])   // 대소비교

last=mid-1;   // 뒷부분을 탐색 대상에서 제외

else

first=mid+1;   // 앞부분을 탐색 대상에서 제외

}

}

return -1;   // 찾지 못했을 때 반환되는 값 -1

} 

int main(void)

{

int arr[]={1, 3, 5, 7, 9};

int idx;

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

if(idx==-1)

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

else

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

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

if(idx==-1)

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

else

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

return 0;

}