지금 내가 공부하고 있는 교재는 "윤성우의 열혈 자료구조" 이다.
난 그저 복습과 요약 차원에서 글쓰는 거니깐 책을 사서 보는게 좋다.
일단 c언어가 어느정도 되는 사람이 사야할 책이다.
c언어도 잘 못하는 분이 이책을 사면 멘붕이 올 수가 있다(이건 오바인가?)
툴은 무료툴인 코드블락을 이용해서 공부 중이다.
코드블락 다운 링크 : http://www.codeblocks.org/
1. 자료구조란 무엇인가??
자료구조란?? 데이터를 표현하고 저장하는 방법에 대한 설명이다.
크게 선형 구조와 비선형 구조로 나뉜다.
선형 구조는 자료를 표현 및 저장하는 방식이 선형이다.
선형이 뭐지?! 여자이름인가? 하는 사람은 솔로 기간이 긴.....;;
선형은 선의 형태의 약자다.
선의 형태... 즉, 자료가 일렬로 저장되어 있다는 것이다.(배열 같이)
비선형 구조는 당연 선의 형태가 아닌 일렬로 저장되어 있지 않은 구조다 (너무 당연한가 ?)
2. 알고리즘이란 무엇인가?
뜬금없이 자료구조 이야기 하다가 알고리즘이 나오는 이유는 자료구조와 알고리즘은 서로 필요하기 때문이다.
자료구조가 데이터 저장방법을 설명한다면 알고리즘은 저장된 데이터를 활용하는 법이기 때문이다.
데이터가 어찌 저장되어 있느냐에 따라 알고리즘도 달라진다.
3. 알고리즘의 성능분석 방법
요즘은 빅데이터 시대이다.
데이터가 어~~~~~~~~~~~~ㅁ청 많다는 것이다.
이걸 얼마나 빠르고 정확하게 찾아내고 처리해줄수 있는지가 알고리즘의 성능인데.
보통 알고리즘 성능을 따질 때는 시간 복잡도와 공간 복잡도를 따진다.
시간 복잡도 - 속도가 얼마나 빠른가?
공간 복잡도 - 메모리를 얼마나 필요로 하는가??
물론 최고는 속도도 빠르고 메모리는 적게 먹는게 젤 좋은거지만 둘 중 고르라면
속도가 빠른 것을 선호하는 편이다.
공간 복잡도는 메모리가 워낙 싸서 한개 더 달면 된다 -_-;
고로 알고리즘의 성능 분석은 주로 시간 복잡도(속도)를 따질 것이다.
그럼 이제 어찌 속도를 평가할 수 있을까??
데이터를 죽어라 만들어서 초를 젤까??
뭐 그것도 나름 방법이긴 하다. 하지만 이왕이면 머리를 써보자.
어떤 데이터를 찾는다고 할 때 공통으로 들어가는게 뭘까??
당연 = 이다.(코드상으로는 == 이지만...)
내가 찾는 데이터가 같은게 있냐 없냐? 있다면 어디에 있냐?
이걸 최대한 빠르게 찾는게 목적아닌가??
그럼 = 횟수가 적을수록 좋은 알고리즘이라 할 수 있다.
이걸로 시간 복잡도를 계산할 것이다.
--------------------------------------------------------------------------------
1. 순차 탐색 알고리즘
그럼 가장 먼저 볼 알고리즘은 순차 탐색(Linear Search) 알고리즘이다.
순차 탐색이란 그야말로 처음부터 끝까지 쭈~~욱 비교해가며 찾는 것이다.(가장 단순하다)
인덱스 0 ~ 데이터 있는 최대 값까지 순차적으로 죽어라고 비교해서 찾는거다(단순 무식 과격)
기본적인 코드를 보자.
--------------------------------------------------------------------------------
#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;
}
--------------------------------------------------------------------------------
소스는 오렌지미디어에서 다운 받되
직접 실행 시켜가며 바꿔가며 해보자.
소스 받는 곳 : http://www.orentec.co.kr/jaryosil/DA_ST_1/add_form.php
소스가 어렵지 않으니 이해하는데 별 어려움은 없을 것이다.
순차 탐색은 데이터가 많아질수록 속도가 느려진다.
우연히 내가 찾는게 맨 처음에 있으면 젤 먼저 찾겠지만.
제일 뒤에 있다면 데이터 갯수만큼 비교해야하는 비극이 일어난다.
-------------------------------------------------------------------------------
2. 이진 탐색 알고리즘
이진 탐색 알고리즘은 데이터 위치를 절반씩 줄여가면서 비교하는 방식이다.
이 알고리즘의 필수 요소는 배열에 저장된 데이터가 "정렬"되어 있어야 한다는 것이다.
즉, 정렬 안되어 있는 데이터에는 아무짝에도 쓸모 없는(?) 알고리즘이다.
정렬은 오름차순이던 내림차순이던 상관은 없다.
방법은 이러하다.
1)배열 인덱스의 시작과 끝을 더한다.
2) 더한 값을 2로 나눈다.
3) 나온 값의 인덱스에 있는 데이터를 찾고자 하는 값과 비교한다.
4) 찾고자 하는 값과 기준값이 같다면 한번에 찾은것이다(오오미 지리것소)
5) 찾고자 하는 값이 기준값보다 크다면 기준 인덱스의 오른쪽 배열로 넘어간다.
5-1) 찾고자 하는 값이 작다면 기준값보다 작다면 기준 인덱스의 왼쪽 배열로 넘어간다.
6) 이 짓을 찾을 때까지 한다.(아악 반복이라니)
7) 1개 남은 것까지 비교했는데도 없으면 없는거다(아오 빡쳐)
소스를 보자.
-------------------------------------------------------------------------------
#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;
}
--------------------------------------------------------------------------------
확실히 순차탐색보다는 코드가 좀 길다(이게 길다고 하면 한강으로....는 농담)
중간에 보면 -1,+1 하는 부분이 있다.
이게 뭐하는 짓이지? 왜 빼고 더하지? 생각해 보자.
mid는 기준이 되었던 인덱스가 있는 값이다.
기준이 되었던 것이 같지 않다면(같으면 그게 범인이야!!) 어차피 한번 비교한거니깐
빼거나 더해서 그 값을 배제하고 찾는 것이다.
책에는 그림도 있어서 이해가 더 쉽고 빠르지만 내가 결코 그림그리기가 귀찮아서 이러는게
아니고 책을 사서 보라는 의도...........다.
-------------------------------------------------------------------------------
3. 순차 탐색과 이진 탐색의 알고리즘의 비교
여기서 비교 하는 것은 최악의 시간을 비교하는 것이다.(즉, 다 봤는데 찾는 데이터가 없어!!)
순차 탐색은 데이터 갯수 만큼 시간이 걸릴테니 당연 젤 느리다 -_-
이진 탐색은 윗 소스를 조금 바꿔서 카운트를 셀꺼다.(물론 나도 소스 코드를 퍼오는 것이지만....;;;;)
--------------------------------------------------------------------------------
#include <stdio.h>
int BSearch(int ar[], int len, int target)
{
int first=0;
int last=len-1;
int mid;
int opCount=0; // 비교연산의 횟수를 기록
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;
}
opCount+=1; // 비교연산의 횟수 1 증가
}
printf("비교연산 횟수: %d \n", opCount); // 탐색 실패 시 연산횟수 출력
return -1;
}
int main(void)
{
int arr1[500]={0,}; // 모든 요소 0으로 초기화
int arr2[5000]={0,}; // 모든 요소 0으로 초기화
int arr3[50000]={0,}; // 모든 요소 0으로 초기화
int idx;
// 저장되지 않은 정수 1을 찾으라고 명령
idx=BSearch(arr1, sizeof(arr1)/sizeof(int), 1);
if(idx==-1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
// 저장되지 않은 정수 2를 찾으라고 명령
idx=BSearch(arr2, sizeof(arr2)/sizeof(int), 2);
if(idx==-1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
// 저장되지 않은 정수 3을 찾으라고 명령
idx=BSearch(arr3, sizeof(arr3)/sizeof(int), 3);
if(idx==-1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
--------------------------------------------------------------------------------
모든 배열에 0밖에 없는데 다른 정수를 넣어봐야 끝까지 비교하고 찾지도 못할 것이다.
순차 탐색의 비교 연산 횟수는 위와 같은 경우면 500, 5000, 50000 번 이다.(쩔어)
이진 탐색의 바교 연산 횟수는 9, 13, 16 번이다.(오오미 나 팬티 좀 갈아 입고 올께)
하지만 데이터가 정렬되어 있어야 하는 단점이 있다.(0 밖에 없는 것도 정렬된거다 ㅡㅡ;;)
이와 같이 알고리즘과 자료구조는 잘 적용하는 문제지 뭐가 젤 좋고 젤 후진 건 없다.
이로써 1강 요약은 끝~
댓글 없음:
댓글 쓰기