| 129번째 줄: | 129번째 줄: | ||
한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. | 한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. | ||
==== 랜덤 접근 가능 ==== | ==== 랜덤 접근 가능 ==== | ||
모든 자료에 O(1)으로 접근이 | 모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다. | ||
===== 배열 ===== | ===== 배열 ===== | ||
가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C(프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. | 가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C(프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. | ||
2015년 5월 24일 (일) 10:06 판
들어가기 전
일단 이게 입문인지부터 생각해보자
빨간 컵에 칠성사이다가 담겨져 있고 파란 컵에 스프라이트가 담겨져있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 수수께끼나 넌센스 문제가 아니다.
이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스 처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. 이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.
| 의사코드 펼치기 |
|---|
1 function 바꾸기(첫번째컵, 두번째컵): 2 잠시담아둘컵 ← 첫번째컵 3 첫번째컵 ← 두번째컵 4 두번째컵 ← 잠시담아둘컵 5 end function 6 7 function 지금상황(): 8 파란컵 ← "칠성사이다" 9 빨간컵 ← "스프라이트" 10 바꾸기(파란컵, 빨간컵) 11 print 파란컵 12 print 빨간컵 13 end function |
using System;
namespace 사이다컵바꾸기
{
class Program
{
static void Main(string[] args)
{
// 빨간 컵과 파란 컵에 칠성사이다와 스프라이트가 담겨져 있다.
string 빨간컵 = "칠성사이다";
string 파란컵 = "스프라이트";
Console.WriteLine("=====바꾸기 전=====");
Console.WriteLine("빨간컵 : {0}", 빨간컵);
Console.WriteLine("파란컵 : {0}", 파란컵);
// 새롭게 준비한 노란 컵
string 노란컵;
// 스프라이트를 빨간 컵에 붓기 위해 칠성사이다를 노란컵에 붓는다.
// 그 다음 파란 컵의 스프라이트를 빨간 컵에 붓는다.
// 그 다음 노란 컵에 임시로 담아둔 칠성 사이다를 파란 컵에 붓는다.
노란컵 = 빨간컵;
빨간컵 = 파란컵;
파란컵 = 노란컵;
Console.WriteLine("=====바꾼 후=====");
Console.WriteLine("빨간컵 : {0}", 빨간컵);
Console.WriteLine("파란컵 : {0}", 파란컵);
}
}
}
여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. 숫자가 아니고 객체면? 포인터 주소값을 더하고 빼면... ... 사실 덧셈보다 더 빠른 방법은 XOR 회로를 사용하는법이 있다. 값이 같지 않으면 a=a^b b=a^b a=a^b를 넣어두면 정수가 아니더라도, 산술적 연산이 아니라 비트 배열 자체가 바뀌기 때문에 값이 교환된다.하지만 병렬 프로그래밍에서는 무리DA☆ZE★
알고리즘의 시간 복잡도
방을 정리한다고 해보자. 방에 널려있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. 이렇게 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이걸 알고리즘의 시간 복잡도라 한다.
알고리즘의 시간 복잡도는 계산 횟수가 많아지면 높아진다. 그런데 이 계산 횟수의 정확한 측정이 어렵기 때문에, 보통 Big O 표기법이라는 걸 이용해서 표시한다.
예를 들어, 입력된 데이터의 갯수가 [math]\displaystyle{ n }[/math]개일 때 [math]\displaystyle{ 2n+7 }[/math]번 계산하는 알고리즘과 [math]\displaystyle{ 2n }[/math]번 계산하는 알고리즘이 있다고 하자. [math]\displaystyle{ n }[/math]이 커지면 둘 사이의 차이는 사실상 없어진다. 즉 [math]\displaystyle{ O(2n+7)=O(2n) }[/math]이다. 좀 더 나아가면 계산 횟수가 [math]\displaystyle{ n }[/math]에 비례하므로, 그냥 [math]\displaystyle{ O(n) }[/math]라고 표현할 수 있다. 일반적으로, 이 중 가장 간단한 형태인 [math]\displaystyle{ O(n) }[/math]로 표기한다. 이와 비슷하게, [math]\displaystyle{ 2n^3+n^2 }[/math]번 계산하는 알고리즘의 시간 복잡도는 [math]\displaystyle{ O(n^3) }[/math]로 나타낼 수 있다.
자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. 위에서 아래로 갈수록 시간 복잡도가 높아진다.
| 시간 복잡도 | 설명 |
|---|---|
| [math]\displaystyle{ O(1) }[/math] | 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다. |
| [math]\displaystyle{ O(\log n) }[/math] | 로그 형태 |
| [math]\displaystyle{ O(n) }[/math] | 선형 |
| [math]\displaystyle{ O(n\log n) }[/math] | 선형로그 형태 |
| [math]\displaystyle{ O(n^2), O(n^3),\cdots }[/math] | 다차 형태 |
| [math]\displaystyle{ O(2^n) }[/math] | 지수 형태 |
| [math]\displaystyle{ O(n!) }[/math] | 팩토리얼 형태 |
예를 들어 아래의 링크드 리스트에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(n) }[/math], 해시 테이블에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(1) }[/math]이다. 이는 평균적으로 해시 테이블에서의 탐색이 링크드 리스트에서의 탐색보다 빠르다는 뜻이다.
알고리즘의 정당성 증명
갑자기 왠 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다.
수학적 귀납법
다들 수학 공부하면서 한 번씩은 들어봤을 그것이다. 수학적 귀납법을 이용한 증명은 크게 단계 나누기와 첫 단계 증명, 귀납 증명으로 나눈다. 자세한 내용은 해당 항목 참고.
반복문 불변식
반복문의 내용이 매 번 실행될 때마다 중간 결과가 올바른 답을 도출하기 위한 결과로 잘 나오는지를 판별하는 조건이다. 반복문이 마지막에 올바른 답을 내놓으려면 항상 이 식이 변하지 않아야 한다(그러므로 불변식이라고 한다).
불변식을 이용해 다음과 같이 반복문의 정당성을 증명할 수 있다.
- 반복문 진입시에 불변식이 성립함을 보인다.(초기 조건)
- 반복문 내용이 불변식에 영향을 주지 않음을 보인다.(유지 조건)
- 반복문 종료후 불변식이 성립하면 항상 올바른 답이 나옴을 보인다.
귀류법
수학에서도 많이 사용되는 만능의 증명법, 귀류법이다. 자세한 내용은 해당 항목 참고.
비둘기집의 원리
경우의 수에서 자주 언급되는 그 원리 맞다. 해당 항목 참고.
구성적 증명
위에 언급한 증명 방법들과는 달리, 구성적 증명은 답의 존재성을 보이는게 아닌, 답을 구하는 방법 그 자체를 보이는 것이다. 쉽게 말해, 그냥 답을 구하는 알고리즘의 실행 과정을 설명한다고 생각하면 된다.
이 문서에서 알고리즘을 표현하기위해 사용한 언어
아래 나오는 모든 코드는 C언어를 기본으로 하며, 다른 언어들은 알아서 추가해주길 바란다. 실제 문제 풀이 예제를 제외한 알고리즘을 의사코드로 작성할 수 있다면 각 언어별 코드보다 위에 의사코드 버전을 추가해주길 바란다.
플로우 차트
기호
자료구조
데이터를 저장하는 방식을 말한다. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필수적이다.
선형 자료구조
한 종류의 데이터가 선처럼 길게 나열된 자료구조이다.
랜덤 접근 가능
모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다.
배열
가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. C언어에서는 대괄호를 사용한다.
int array1[]; //int *array1과 비슷함.
int array2[10]; //크기를 가지는 배열
int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열
C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다.
해시
해시는 해시 함수로 구현한다. 해시 함수는 마치 배열처럼, 어떤 자료를 찾을 때 [math]\displaystyle{ O(1) }[/math]의 시간만을 소요한다. 해시함수에 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다. 하지만, 언제나 [math]\displaystyle{ O(1) }[/math]이 보장되는 것은 아니다. 자세한 것은 해시 테이블 참고.
랜덤 접근 불가능
모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다.
스택
먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 옵션으로 가질 수도 있다.
아래는 배열로 구현한 스택이다.[1]
//헤더 부분
void push(int); //push 함수 정의
int pop();
//소스 부분
int array[500]; //스택의 최대 크기는 500
int top = -1; //스택의 현재 크기는 0;
void push(int n)
{
top = top + 1;
array[top] = n;
}
int pop()
{
int value = array[top];
top = top - 1;
return array[top];
}
사용법은 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다.
push(1), push(2), push(3);
printf("%d %d %d", pop(), pop(), pop());
출력 결과는 3 2 1과 같을 것이다.
큐
먼저 들어간 자료가 먼저 나오는 자료구조. 선입선출(先入先出) 구조라고도 한다. 자료를 넣는 Enqueue 함수와 Dequeue 함수를 가진다.
밑의 큐는 연결 리스트로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다.
void enqueue(int);
int dequeue();
struct linkedList
{
int value;
struct linkedList *next;
};
struct linkedList *front; //큐의 맨 앞을 가리킨다.
struct linkedList *back; //큐의 맨 뒤를 가리킨다.
void enqueue(int n) //큐에 자료를 넣는 함수
{
if(front == NULL) //큐가 비어있을 경우
{
*front = {n, NULL}; //맨 앞에 자료를 넣고
back = front; //맨 뒤와 맨 앞을 같게 한다.
}
else
{
back -> *next = {n, NULL}; //맨 뒤 다음에 자료를 넣는다.
back = back -> next; //넣은 자료를 맨 뒤로 한다.
}
}
int dequeue() //큐에서 자료를 빼는 함수
{
int res = front -> value;
front = front -> next;
return res;
}
데크
간단하게 말하자면 스택과 큐의 융합형태. 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 보통 입력이나 출력 중 하나를 한 쪽 입구만 가능하게 제한하는 형태가 많이 쓰인다.
링크드 리스트
연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 가장 간단하게 구현한 것은 위의 큐. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다.
비선형 자료구조
선형 자료구조가 아닌 모든 자료구조이다.
그래프
수학, 과학 시간에 많이 보던 그 그래프와는 사뭇 다르다. 고등학교 교육과정에서 이산수학이 빠지고 행렬도 빠짐에 따라 같이 빠지게 되는 비운의 단원알고리즘을 배우다 보면 자주 나오는 구조. 점들, 그리고 점들을 연결하는 선들로 이루어진 지도 비스무리한 걸 연상하면 편하다. 이때의 점을 노드, 선을 엣지라고 부른다. 간단한 구조체를 만들어 보자.
struct Edge //노드보다는 엣지로 나타내는 편이 대부분의 경우에 더 좋다.
{
int snode; //시작 노드
int enode; //종료 노드
//int cost; //가중치를 가지는 엣지에 사용된다.
};
위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다.
그래프 순회 알고리즘
그래프를 순회하는 방법이다. 각 방법마다 장단점이 있으니 상황에 따라 적절한 알고리즘을 선택하는 것이 중요하다.
깊이 우선 탐색
Depth First Search, DFS
너비 우선 탐색
Breadth First Search, BFS
트리
트리 순회 알고리즘
전위 순회
중위 순회
후위 순회
이진 검색 트리
문자열
기초 정렬 알고리즘
정렬 알고리즘은 크기순, 사전순과 같이 정렬하는 알고리즘을 말한다. 효율적인 알고리즘들 중 대부분은 데이터가 사전에 정렬되어 있을 것을 요구하는 것이 많다.
뿅뿅뿅뿅뿅 일단 이걸 보고 뭘 배우면 좋을 지 생각해보자.
영상을 보다보면 마지막의 보고(Bogo) 정렬은 결과를 보여주지 않는걸 보고 의아해 할 수도 있는데, 보고 정렬은 모든 값을 랜덤하게 줄세우는걸 반복하다보면 언젠가는 정렬이 된다는 식으로 동작하는 알고리즘이라서 그렇다(...) 알고리즘의 구성도 랜덤배치->정렬여부 확인의 무한루프. 당연하지만 효율성은 바닥을 긴다. 잘하면 한방에 정렬되지만, 영원히 정렬되지 않을 수도 있다. 기글 하드웨어의 한 유저가 10개의 값으로 테스트하니 결과를 보기까지 4천만번의 읽기작업이 수행되었다고 한다.[2]설마 이런데도 배우고 싶다고는 안하겠지?
거품(Bubble) 정렬
세상에서 가장 만만한 정렬(...) 바로 뒤의 원소와 비교해 더 크다면 뒤로 간다. 구현이 쉬운 만큼 성능이 구리다. 알고리즘이 쉬워서 입문용으로 나오는거지 사실 정렬이 되어있든 아니든 대체적으로 느리고 캐시도 못 타고 여러모로 안 좋다. 공부할 목적으로만 쓰고 실제로 정렬을 돌려야한다면 쓰지 말자.
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};
void sort()
{
int i, j;
for(i = 0; i < 10; i++)
for(j = i; j < 9; j++)
if(arr[j] > arr[j + 1]) //j번째 원소가 다음 원소보다 크다면 바꾼다.
{
int temp;
temp = arr[j + 1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
선택(Selection) 정렬
삽입(Insertion) 정렬
다음 단계로
축하한다. 우리는 일단 밑바탕을 배운것이다. 이제 다음 단계로 넘어갈 차례이다. 이제부터 슬슬 긴장해야 한다.
각주
- ↑ C++ STL의 그것보다 빠를 것이다. 다만 확장이 어려울 뿐.
- ↑ http://gigglehd.com/zbxe/10760945