연결리스트에 앞서 추상 자료형을 설명한다.
추상 자료형이 뭐지?? -_-?
추상....... 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것
이라고 하는데 뭔소린지 모르겠다.
기능을 나열한 것을 뭐라 표현할 수 있을까??
예를 들면 TV에 대한 공통된 기능을 보자.
1. tv를 켠다.
2. 채널을 바꾼다.
3. 볼륨을 바꾼다.
4. tv를 끈다.
위 기능은 tv라면 다 있어야 하는 기능이다. 이것을 추상 자료형이라고 한다.
이제 이 추상자료형(ADT : Abstract Data Type)을 자료구조 학습에 포함 시킨다.
1. 리스트 자료구조의 ADT를 정의한다.
2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다.
3. ADT를 근거로 리스트를 구현한다.
리스트란 무엇인가? 리스트라는 자료구조는 구현 방법에 따라 2가지로 나뉜다.
1. 순차 리스트 - 배열을 기반으로 구현된 리스트
2. 연결 리스트 - 메모리의 동적 할당을 기갑으로 구현된 리스트
이번 장에는 1번 배열을 기반으로 구현된 순차 리스트를 알아볼까 한다.
순차 리스트의 중요한 특성은 아래와 같다.
데이터를 나란히 저장함, 중복된 데이터의 저장을 막지 않음
그럼 리스트 자료구조의 ADT를 정의해 보자.
*void ListInit(List * plist)
-초기화할 리스트의 주소 값을 인자로 전달한다.
-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
*void LInsert(List * plist, LData data)
-리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
*int LFirst(List * plist, LData * pdata)
-첫 번째 데이터가 pdata가 가르키는 메모리에 저장된다.
-데이터의 참조를 위한 초기화가 진행된다.
-참조 성공시 true(1), 실패시 false(0) 반환
*int LNext(List * plist, LData * pdata)
-참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
-순차적인 참조를 위해서 반복 호출이 가능하다
-참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야한다.
-참조 성공시 true(1), 실패시 false(0) 반환
*LData LRemove(List * plist)
-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
-삭제된 데이터는 반환한다
-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
*int LCount(List * plist)
-리스트에 저장되어 있는 데이터의 수를 반환한다.
아래는 위의 정의를 구현한 소스 코드다.
---------------------------------------------------------------------------------
이건 c 부분
#include <stdio.h>
#include "ArrayList.h"
//초기화할 리스트의 주소 값을 인자로 전달
void ListInit(List * plist)
{
(plist->numOfData) = 0;
(plist->curPosition) = -1;
}
//리스트에 데이터 저장
void LInsert(List * plist, LData data)
{
if(plist->numOfData > LIST_LEN)
{
puts("저장이 불가능합니다.");
return;
}
plist->arr[plist->numOfData] = data;
(plist->numOfData)++;
}
//첫번째 데이터를 pdata가 가르키는 메모리에 저장
int LFirst(List * plist, LData * pdata)
{
if(plist->numOfData == 0)
return FALSE;
(plist->curPosition) = 0;
*pdata = plist->arr[0];
return TRUE;
}
//참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장
int LNext(List * plist, LData * pdata)
{
if(plist->curPosition >= (plist->numOfData)-1)
return FALSE;
(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
//LFirst 또는 LNext 함수의 마지막 반환 데이터를 반환
LData LRemove(List * plist)
{
int rpos = plist->curPosition;
int num = plist->numOfData;
int i;
LData rdata = plist->arr[rpos];
for(i=rpos; i<num-1; i++)
plist->arr[i] = plist->arr[i+1];
(plist->numOfData)--;
(plist->curPosition)--;
return rdata;
}
//리스트에 저장되어 있는 데이터의 수를 반환
int LCount(List * plist)
{
return plist->numOfData;
}
---------------------------------------------------------------------------------
헤더 부분
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1 //'참'을 표현하기 위한 매크로 정의
#define FALSE 0 //'거짓'을 표현하기 위한 매크로 정의
/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData; //LDdata에 대한 typedef 선언
typedef struct __ArrayList //배열기반 리스트를 정의한 구조체
{
LData arr[LIST_LEN]; //리스트의 저장소인 배열
int numOfData; //저장된 데이터의 수
int curPosition; //데이터 참조 위치를 기록
} ArrayList;
/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;
void ListInit(List * plist); //초기화
void LInsert(List * plist, LData data); //데이터 저장
int LFirst(List * plist, LData * pdata); //첫 데이터 참조
int LNext(List * plist, LData * pdata); //두 번째 이후 데이터 참조
LData LRemove(List * plist); //참조한 데이터 삭제
int LCount(List * plist); //저장된 데이터의 수 반환
#endif
---------------------------------------------------------------------------------
내가 공부하면서 잘 이해가 안갔던 것은 삭제 부분 이었다.
이 부분만 따로 한번 더 보자
1. 삭제할 데이터를 찾는다.
2. 삭제할 데이터를 임시로 저장한다.
3. 삭제 뒷부분의 데이터 전부를 -1칸 이동시킨다.
4. 데이터 수를 -1 줄인다.
5. 참조위치를 -1 한다.
6. 임시 저장한 데이터를 반환한다.(뭐를 지웠는지 보여주기 위함)
책에는 그림으로도 설명되어 있어서 더 이해가 빠르다.
왠만하면 책도 사서 보자.
책은 "윤성우의 열혈 자료구조" 이다.
2013년 5월 20일 월요일
2013년 5월 10일 금요일
2장 - 재귀(Recursion)
2강은 재귀다. 재귀 함수는 자기가 자신을 호출하는 것이다.
이....이게 뭔소리지??
일단 코드를 보고 이해해보자.
---------------------------------------------------------------------------------
#include <stdio.h>
void Recursive(int num)
{
if(num<=0)
return;
printf("Recursive call! %d \n", num);
Recursive(num-1);
}
int main(void)
{
Recursive(3);
return 0;
}
---------------------------------------------------------------------------------
재귀 함수는 탈출 조건이 반드시 있어야 한다. 그렇지 않으면 무한루프에 빠질테니...;;
이번엔 재귀 함수를 이용해서 팩토리얼을 구해보자.
1. 재귀 함수를 이용한 팩토리얼
팩토리얼이란??
4! 이면 4 x 3 x 2 x 1 을 하는 것이다.
이걸 다르게 보면 n! = n x (n-1) x (n-2) x ..... x 2 x 1 이고,
이걸 압축해 보면 n! = n x (n-1)!
그리고 0! 은 1이므로 이걸로 재귀함수의 탈출 조건으로 삼자.
소스 코드를 보자~
---------------------------------------------------------------------------------
#include <stdio.h>
int Factorial(int n)
{
if(n==0)
return 1;
else
return n * Factorial(n-1);
}
int main(void)
{
printf("1! = %d \n", Factorial(1));
printf("2! = %d \n", Factorial(2));
printf("3! = %d \n", Factorial(3));
printf("4! = %d \n", Factorial(4));
printf("9! = %d \n", Factorial(9));
return 0;
}
---------------------------------------------------------------------------------
너무 간단한가? ㅡㅡ;;; 하긴 나도 책에 있는 것을 복습 차원에서 또 쓰는 것이니....;;
소스코드를 베껴 쓰기보단 재귀 함수를 어찌 활용하는지 과정이 더 중요하다.
이번에는 피보나치 수열을 재귀 함수로 표현(?) 해보자.
먼저 피보나치 수열의 패턴을 생각해보자.
피보나치 수열이란?
첫째값과 둘째값을 더해서 셋째값을 구하고 한칸씩 이동하여 계속 반복하는 것이다.
이걸 식으로 나타내면
수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값
이걸 소스코드로 표현해보면.
--------------------------------------------------------------------------------
#include <stdio.h>
int Fibo(int n)
{
if(n==1)
return 0;
else if(n==2)
return 1;
else
return Fibo(n-1)+Fibo(n-2);
}
int main(void)
{
int i;
for(i=1; i<15; i++)
printf("%d ", Fibo(i));
return 0;
}
---------------------------------------------------------------------------------
2. 이진 탐색을 재귀 함수로 표현
이진 탐색도 값을 찾을 때까지 계속 동일한 패턴으로 반복하는 것이니 재귀 함수로 표현할 수 있다.
그럼 반복 패턴을 정리해보자.
1. 탐색 범위의 중앙에 목표값이 있나?
2. 없으면 범위를 반으로 줄이고 찾을 때까지 반복
3. 시작 위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last 보다 커지는 경우 끝
이걸 소스 코드로 표현해보면
---------------------------------------------------------------------------------
#include <stdio.h>
int BSearchRecur(int ar[], int first, int last, int target)
{
int mid;
if(first > last)
return -1; // -1의 반환은 탐색의 실패를 의미
mid = (first+last) / 2; // 탐색대상의 중앙을 찾는다.
if(ar[mid] == target)
return mid; // 검색된 타겟의 인덱스 값 반환
else if(target < ar[mid])
return BSearchRecur(ar, first, mid-1, target);
else
return BSearchRecur(ar, mid+1, last, target);
}
int main(void)
{
int arr[] = {1, 3, 5, 7, 9};
int idx;
idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
if(idx == -1) //탈출 조건
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 2);
if(idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
---------------------------------------------------------------------------------
3. 하노이 타워
하노이 타워는 3개의 기둥을 이용해 1번에 있는 탑을 3번의 탑으로 이동 시키는 것이다.
규칙은 작은 원반이 큰 원반 아래에 위치할 수 없고, 한번에 한개만 이동시킬 수 있다.
이 규칙을 지켜가며 생각해보자.
1. 1번 기둥에 있는 가장 아래에 있는(가장 큰) 원반을 3번 기둥으로 옮겨야 한다.
이건 역으로 n개의 원반 중 n-1개만큼 2번 기둥으로 옮겨야 한다는 뜻이다.
2. 제일 큰 원반을 1번에서 3번 기둥으로 이동
3. 이제는 2번 기둥에 있는 n개 원반 중 다시 n-1개의 원반을 1번 기둥으로 이동
4. 2번 기둥에 있던 제일 큰 원번을 3번 기둥으로 이동
이걸 계속 다 쌓을 때까지 반복~
n의 개수가 1이 되면 그것만 3번 기둥으로 옮기면 되니깐 n이 1이 될 때 탈출 조건
이걸 기반으로 소스 코드로 표현해 보자.
---------------------------------------------------------------------------------
#include <stdio.h>
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반1을 %c에서 %c로 이동 \n", from, to);
}
else
{
HanoiTowerMove(num-1, from, to, by); // 3단계 중 1단계
printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); // 3단계 중 2단계
HanoiTowerMove(num-1, by, from, to); // 3단계 중 3단계
}
}
int main(void)
{
// 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
HanoiTowerMove(3, 'A', 'B', 'C');
return 0;
}
---------------------------------------------------------------------------------
재귀 함수를 이용하고 활용하는 것은 많은 연습과 경험이 필요할 것 같다.
기억해야 할 점은 반복 패턴을 찾고, 탈출 조건을 만드는 것이다.
그럼 오늘 공부도 여기까지~
이....이게 뭔소리지??
일단 코드를 보고 이해해보자.
---------------------------------------------------------------------------------
#include <stdio.h>
void Recursive(int num)
{
if(num<=0)
return;
printf("Recursive call! %d \n", num);
Recursive(num-1);
}
int main(void)
{
Recursive(3);
return 0;
}
---------------------------------------------------------------------------------
재귀 함수는 탈출 조건이 반드시 있어야 한다. 그렇지 않으면 무한루프에 빠질테니...;;
이번엔 재귀 함수를 이용해서 팩토리얼을 구해보자.
1. 재귀 함수를 이용한 팩토리얼
팩토리얼이란??
4! 이면 4 x 3 x 2 x 1 을 하는 것이다.
이걸 다르게 보면 n! = n x (n-1) x (n-2) x ..... x 2 x 1 이고,
이걸 압축해 보면 n! = n x (n-1)!
그리고 0! 은 1이므로 이걸로 재귀함수의 탈출 조건으로 삼자.
소스 코드를 보자~
---------------------------------------------------------------------------------
#include <stdio.h>
int Factorial(int n)
{
if(n==0)
return 1;
else
return n * Factorial(n-1);
}
int main(void)
{
printf("1! = %d \n", Factorial(1));
printf("2! = %d \n", Factorial(2));
printf("3! = %d \n", Factorial(3));
printf("4! = %d \n", Factorial(4));
printf("9! = %d \n", Factorial(9));
return 0;
}
---------------------------------------------------------------------------------
너무 간단한가? ㅡㅡ;;; 하긴 나도 책에 있는 것을 복습 차원에서 또 쓰는 것이니....;;
소스코드를 베껴 쓰기보단 재귀 함수를 어찌 활용하는지 과정이 더 중요하다.
이번에는 피보나치 수열을 재귀 함수로 표현(?) 해보자.
먼저 피보나치 수열의 패턴을 생각해보자.
피보나치 수열이란?
첫째값과 둘째값을 더해서 셋째값을 구하고 한칸씩 이동하여 계속 반복하는 것이다.
이걸 식으로 나타내면
수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값
이걸 소스코드로 표현해보면.
--------------------------------------------------------------------------------
#include <stdio.h>
int Fibo(int n)
{
if(n==1)
return 0;
else if(n==2)
return 1;
else
return Fibo(n-1)+Fibo(n-2);
}
int main(void)
{
int i;
for(i=1; i<15; i++)
printf("%d ", Fibo(i));
return 0;
}
---------------------------------------------------------------------------------
2. 이진 탐색을 재귀 함수로 표현
이진 탐색도 값을 찾을 때까지 계속 동일한 패턴으로 반복하는 것이니 재귀 함수로 표현할 수 있다.
그럼 반복 패턴을 정리해보자.
1. 탐색 범위의 중앙에 목표값이 있나?
2. 없으면 범위를 반으로 줄이고 찾을 때까지 반복
3. 시작 위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last 보다 커지는 경우 끝
이걸 소스 코드로 표현해보면
---------------------------------------------------------------------------------
#include <stdio.h>
int BSearchRecur(int ar[], int first, int last, int target)
{
int mid;
if(first > last)
return -1; // -1의 반환은 탐색의 실패를 의미
mid = (first+last) / 2; // 탐색대상의 중앙을 찾는다.
if(ar[mid] == target)
return mid; // 검색된 타겟의 인덱스 값 반환
else if(target < ar[mid])
return BSearchRecur(ar, first, mid-1, target);
else
return BSearchRecur(ar, mid+1, last, target);
}
int main(void)
{
int arr[] = {1, 3, 5, 7, 9};
int idx;
idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
if(idx == -1) //탈출 조건
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 2);
if(idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
---------------------------------------------------------------------------------
3. 하노이 타워
하노이 타워는 3개의 기둥을 이용해 1번에 있는 탑을 3번의 탑으로 이동 시키는 것이다.
규칙은 작은 원반이 큰 원반 아래에 위치할 수 없고, 한번에 한개만 이동시킬 수 있다.
이 규칙을 지켜가며 생각해보자.
1. 1번 기둥에 있는 가장 아래에 있는(가장 큰) 원반을 3번 기둥으로 옮겨야 한다.
이건 역으로 n개의 원반 중 n-1개만큼 2번 기둥으로 옮겨야 한다는 뜻이다.
2. 제일 큰 원반을 1번에서 3번 기둥으로 이동
3. 이제는 2번 기둥에 있는 n개 원반 중 다시 n-1개의 원반을 1번 기둥으로 이동
4. 2번 기둥에 있던 제일 큰 원번을 3번 기둥으로 이동
이걸 계속 다 쌓을 때까지 반복~
n의 개수가 1이 되면 그것만 3번 기둥으로 옮기면 되니깐 n이 1이 될 때 탈출 조건
이걸 기반으로 소스 코드로 표현해 보자.
---------------------------------------------------------------------------------
#include <stdio.h>
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반1을 %c에서 %c로 이동 \n", from, to);
}
else
{
HanoiTowerMove(num-1, from, to, by); // 3단계 중 1단계
printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); // 3단계 중 2단계
HanoiTowerMove(num-1, by, from, to); // 3단계 중 3단계
}
}
int main(void)
{
// 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
HanoiTowerMove(3, 'A', 'B', 'C');
return 0;
}
---------------------------------------------------------------------------------
재귀 함수를 이용하고 활용하는 것은 많은 연습과 경험이 필요할 것 같다.
기억해야 할 점은 반복 패턴을 찾고, 탈출 조건을 만드는 것이다.
그럼 오늘 공부도 여기까지~
1장 - 자료구조와 알고리즘의 이해
지금 내가 공부하고 있는 교재는 "윤성우의 열혈 자료구조" 이다.
난 그저 복습과 요약 차원에서 글쓰는 거니깐 책을 사서 보는게 좋다.
일단 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강 요약은 끝~
난 그저 복습과 요약 차원에서 글쓰는 거니깐 책을 사서 보는게 좋다.
일단 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강 요약은 끝~
2013년 5월 7일 화요일
후~ 계획을 변경한다.
원래는 TCP/IP를 먼저 하려고 했으나
자료구조 공부가 더 우선 순위라는 생각에 자료구조로 변경하였다.
절대 가상머신으로 깐 우분투 13이 느려서가 아니다(어휴 컴터 좀 사야지 ㅠㅠ)
네트워크 프로그래밍은 주로 유닉스/리눅스 계열에서 하는데
파티션을 할당하기엔 지금 자료의 일부를 지우고 재할당 해야해서.......;;;
컴터 살 때 하드도 하나 추가 구입해야겠다.
어째든 자료구조도 공부해볼까 한다.
학교 다니면서 다 해본 것들이지만 복습차원에서 다시 해본다.
책은 "열혈 자료구조" 이다.
자료구조 공부가 더 우선 순위라는 생각에 자료구조로 변경하였다.
절대 가상머신으로 깐 우분투 13이 느려서가 아니다(어휴 컴터 좀 사야지 ㅠㅠ)
네트워크 프로그래밍은 주로 유닉스/리눅스 계열에서 하는데
파티션을 할당하기엔 지금 자료의 일부를 지우고 재할당 해야해서.......;;;
컴터 살 때 하드도 하나 추가 구입해야겠다.
어째든 자료구조도 공부해볼까 한다.
학교 다니면서 다 해본 것들이지만 복습차원에서 다시 해본다.
책은 "열혈 자료구조" 이다.
피드 구독하기:
글 (Atom)