편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
{{쉽게 알 수 있다 시리즈|이 문서는 정말 쉽습니다.|문서의 내용이 너무 쉬워서 오늘부터 프로그래밍 할 수 있을 것 같습니다.}} | {{쉽게 알 수 있다 시리즈|이 문서는 정말 쉽습니다.|문서의 내용이 너무 쉬워서 오늘부터 프로그래밍 할 수 있을 것 같습니다.}} | ||
[[분류: | [[분류:컴퓨터_프로그래밍]] | ||
[[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | [[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | ||
== 들어가기 전 == | == 들어가기 전 == | ||
빨간 컵에 [[칠성사이다]]가 담겨져 있고 파란 컵에 [[스프라이트]]가 담겨져 있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 | {{--|일단 이게 입문인지부터 생각해보자}} | ||
빨간 컵에 [[칠성사이다]]가 담겨져 있고 파란 컵에 [[스프라이트]]가 담겨져 있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 [[수수께끼]]나 [[넌센스]] 문제가 아니다. | |||
이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. | 이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. <del>이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.</del> | ||
{| class="collapsible collapsed" | {| class="collapsible collapsed" | ||
|- | |- | ||
31번째 줄: | 29번째 줄: | ||
|} | |} | ||
< | <source lang="csharp" class="mw-collapsible mw-collapsed"> | ||
using System; | using System; | ||
64번째 줄: | 62번째 줄: | ||
} | } | ||
} | } | ||
</ | </source> | ||
여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값 을 b에 저장한다. | 여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값(즉 원래 a값)을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. <del>숫자가 아니고 객체면? 음료수는 더하고 빼면 섞이잖아</del> <del>[[우린 안될 거야 아마|포인터 주소값을 더하고 빼면... ...]]</del> 사실 덧셈보다 더 빠른 방법은 XOR 회로를 사용하는법이 있다. 값이 같지 않으면 a=a^b b=a^b a=a^b를 넣어두면 정수가 아니더라도, 산술적 연산이 아니라 비트 배열 자체가 바뀌기 때문에 값이 교환된다.<s>하지만 병렬 프로그래밍에서는 무리DA☆ZE★</s> | ||
== 알고리즘을 왜 알아야 하나? == | |||
== 왜 알아야 하나? == | |||
프로그램을 통해 구하는 결과를 '건물'이라고 치면, 알고리즘은 '설계도'라고 할 수 있다. | 프로그램을 통해 구하는 결과를 '건물'이라고 치면, 알고리즘은 '설계도'라고 할 수 있다. | ||
이 한 마디로 | 이 한 마디로 그 중요성에 대해서는 더 이상의 설명은 생략한다. | ||
다만, 건물을 짓는데 다양한 방법이 동원되는 것처럼 알고리즘도 다양하게 적용될 수 있다. 결과가 동일하더라도 사용하는 알고리즘에 따라 프로그램의 속도나 처리방식 등이 크게 차이나는 경우도 있다. 그에 대한 설명은 아래를 참조. | 다만, 건물을 짓는데 다양한 방법이 동원되는 것처럼 알고리즘도 다양하게 적용될 수 있다. 결과가 동일하더라도 사용하는 알고리즘에 따라 프로그램의 속도나 처리방식 등이 크게 차이나는 경우도 있다. 그에 대한 설명은 아래를 참조. | ||
== 시간 복잡도 == | == 알고리즘의 시간 복잡도 == | ||
방을 정리한다고 해보자. 방에 널려 있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. | 방을 정리한다고 해보자. 방에 널려 있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. 이렇게 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이걸 알고리즘의 시간 복잡도라 한다. | ||
알고리즘의 시간 복잡도는 계산 횟수가 많아지면 높아진다. 그런데 이 계산 횟수의 정확한 측정이 어렵기 때문에, 보통 [[Big O 표기법]]이라는 걸 이용해서 표시한다. | |||
예를 들어, 입력된 데이터의 갯수가 <math>n</math>개일 때 <math>2n+7</math>번 계산하는 알고리즘과 <math>2n</math>번 계산하는 알고리즘이 있다고 하자. <math>n</math>이 커지면 둘 사이의 차이는 사실상 없어진다. 즉 <math>O(2n+7)=O(2n)</math>이다. 좀 더 나아가면 계산 횟수가 <math>n</math>에 비례하므로, 그냥 <math>O(n)</math>라고 표현할 수 있다. 일반적으로, 이 중 가장 간단한 형태인 <math>O(n)</math>로 표기한다. 이와 비슷하게, <math>2n^3+n^2</math>번 계산하는 알고리즘의 시간 복잡도는 <math>O(n^3)</math>로 나타낼 수 있다. | |||
< | |||
자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. 위에서 아래로 갈수록 시간 복잡도가 높아진다. | |||
자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. | |||
{| class='wikitable' | {| class='wikitable' | ||
! 시간 복잡도 !! 설명 | ! 시간 복잡도 !! 설명 | ||
223번째 줄: | 99번째 줄: | ||
|} | |} | ||
예를 들어 아래의 [[ | 예를 들어 아래의 [[쉽게_배우는_프로그래밍_입문/알고리즘#자료구조#선형 랜덤 접근 불가능#데크#링크드 리스트|링크드 리스트]]에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 <math>O(n)</math>, [[쉽게_배우는_프로그래밍_입문/알고리즘#자료구조#선형 랜덤 접근 가능#해시|해시 테이블]]에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 <math>O(1)</math>이다. 이는 평균적으로 해시 테이블에서의 탐색이 링크드 리스트에서의 탐색보다 빠르다는 뜻이다. | ||
== 이 문서에서 알고리즘을 표현하기위해 사용한 언어 == | |||
아래 나오는 모든 코드는 '''[[C(프로그래밍 언어)|C언어]]'''를 기본으로 하며, 다른 언어들은 알아서 [[추가바람|추가해주길 바란다]]. 단, C언어로 구현하기 너무 까다로운 소스의 경우에는 [[C++]]을 사용할 수도 있다. 문제 풀이 예제를 제외한 알고리즘을 [[의사코드]]로 작성할 수 있다면 각 언어별 코드보다 위에 의사코드 버전을 추가해주길 바란다. | |||
== 플로우 차트 == | |||
=== 기호 === | |||
== 자료구조 == | == 자료구조 == | ||
데이터를 저장하는 방식을 말한다. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필수적이다. | 데이터를 저장하는 방식을 말한다. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필수적이다. | ||
=== 선형 자료구조 === | === 선형 자료구조 === | ||
한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. | 한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. | ||
==== 랜덤 접근 가능 ==== | ==== 랜덤 접근 가능 ==== | ||
모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다. | 모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다. | ||
===== 배열 ===== | ===== 배열 ===== | ||
가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C (프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. | 가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C(프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. | ||
< | <source lang="C"> | ||
int array1[]; //int *array1과 비슷함. | int array1[]; //int *array1과 비슷함. | ||
int array2[10]; //크기를 가지는 배열 | int array2[10]; //크기를 가지는 배열 | ||
int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열 | int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열 | ||
</ | </source> | ||
C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다. | C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다. | ||
[[파이썬]]에서는 그냥 리스트 자료구조를 사용한다. | [[파이썬]]에서는 그냥 리스트 자료구조를 사용한다. | ||
< | <source lang="Python"> | ||
array1 = [] # 빈 리스트. | array1 = [] # 빈 리스트. | ||
array2 = [0, 1, 2, 3, 4] # 길이가 5인 리스트. C언어나 파이썬은 숫자를 0부터 센다. | array2 = [0, 1, 2, 3, 4] # 길이가 5인 리스트. C언어나 파이썬은 숫자를 0부터 센다. | ||
array3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 리스트 안에 리스트가 중첩되어 있다. | array3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 리스트 안에 리스트가 중첩되어 있다. | ||
# 리스트 안에는 리스트를 포함하여 어떤 객체도 넣을 수 있다. | # 리스트 안에는 리스트를 포함하여 어떤 객체도 넣을 수 있다. | ||
</ | </source> | ||
===== 해시 ===== | ===== 해시 ===== | ||
266번째 줄: | 136번째 줄: | ||
[[파이썬]]의 해시는 “딕셔너리”(Dictionary)라고 부른다. | [[파이썬]]의 해시는 “딕셔너리”(Dictionary)라고 부른다. | ||
< | <source lang="Python"> | ||
dict1 = {1:"하나", "apple":"사과", "리스트":[1, 2, 3]} | dict1 = {1:"하나", "apple":"사과", "리스트":[1, 2, 3]} | ||
</ | </source> | ||
==== 랜덤 접근 불가능 ==== | ==== 랜덤 접근 불가능 ==== | ||
모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다. | 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다. | ||
===== 스택 ===== | ===== 스택 ===== | ||
[[파일:Data stack.svg|섬네일|스택 자료구조]] | [[파일:Data stack.svg|섬네일|스택 자료구조]] | ||
먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 가질 | 먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 옵션으로 가질 수도 있다. | ||
아래는 | 아래는 배열로 구현한 스택이다.<ref>C++ STL의 그것보다 빠를 것이다. 다만 확장이 어려울 뿐.</ref> | ||
< | <source lang="C"> | ||
//헤더 부분 | |||
int | void push(int); //push 함수 정의 | ||
int | int pop(); | ||
int push(int n) | //소스 부분 | ||
int array[500]; //스택의 최대 크기는 500 | |||
int top = -1; //스택의 현재 크기는 0; | |||
void push(int n) | |||
{ | { | ||
top = top + 1; //혹은 top++; | |||
array[top] = n; | |||
} | } | ||
int pop() | int pop() | ||
{ | { | ||
int value = array[top]; | |||
return | top = top - 1; | ||
return value; | |||
} | } | ||
</ | </source> | ||
스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다. | 사용법은 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다. | ||
< | <source lang="c"> | ||
push(1), push(2), push(3); | push(1), push(2), push(3); | ||
printf("%d %d %d", pop(), pop(), pop()); | printf("%d %d %d", pop(), pop(), pop()); | ||
</ | </source> | ||
출력 결과는 3 2 1과 같을 것이다. | 출력 결과는 3 2 1과 같을 것이다. | ||
[[파이썬]]의 리스트 자료구조로 스택 클래스를 만들면 다음과 같을 것이다. | [[파이썬]]의 리스트 자료구조로 스택 클래스를 만들면 다음과 같을 것이다. | ||
< | <source lang="Python"> | ||
class stack: | class stack: | ||
def __init__(self): | def __init__(self): | ||
323번째 줄: | 195번째 줄: | ||
def pop(self): | def pop(self): | ||
return self.items.pop() | return self.items.pop() | ||
</ | </source> | ||
이렇게 작성한 스택 클래스로 문자열을 뒤집는 함수를 만들면 다음과 같다. | 이렇게 작성한 스택 클래스로 문자열을 뒤집는 함수를 만들면 다음과 같다. | ||
< | <source lang="Python"> | ||
def reverseString(str): | def reverseString(str): | ||
s = stack() | s = stack() | ||
334번째 줄: | 206번째 줄: | ||
result += s.pop() | result += s.pop() | ||
return result | return result | ||
</ | </source> | ||
함수의 실행 결과는 다음과 같다. | 함수의 실행 결과는 다음과 같다. | ||
< | <source lang="Python"> | ||
>>> print(reverseString("apple")) | >>> print(reverseString("apple")) | ||
elppa | elppa | ||
>>> | >>> | ||
</ | </source> | ||
===== 큐 ===== | ===== 큐 ===== | ||
379번째 줄: | 219번째 줄: | ||
밑의 큐는 [[연결 리스트]]로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다. | 밑의 큐는 [[연결 리스트]]로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다. | ||
< | <source lang="C"> | ||
void enqueue(int); | void enqueue(int); | ||
int dequeue(); | int dequeue(); | ||
411번째 줄: | 251번째 줄: | ||
return res; | return res; | ||
} | } | ||
</ | </source> | ||
[[파이썬]]에서 리스트 자료구조로 큐를 구현하는 클래스를 | [[파이썬]]에서 리스트 자료구조로 큐를 구현하는 클래스를 작성하자면 다음과 같을 것이다. | ||
< | <source lang="Python"> | ||
class queue: | class queue: | ||
def __init__(self): | def __init__(self): | ||
433번째 줄: | 271번째 줄: | ||
def size(self): | def size(self): | ||
return len(self.items) | return len(self.items) | ||
</ | </source> | ||
===== 데크 ===== | ===== 데크 ===== | ||
457번째 줄: | 277번째 줄: | ||
===== 링크드 리스트 ===== | ===== 링크드 리스트 ===== | ||
연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 또한, 중간에서 삽입과 삭제를 할 수 있다. 가장 간단하게 구현한 것은 위의 [[큐]]. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다 | 연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 또한, 중간에서 삽입과 삭제를 할 수 있다. 가장 간단하게 구현한 것은 위의 [[큐]]. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다. | ||
==== 선형구조 자료 탐색법 ==== | ==== 선형구조 자료 탐색법 ==== | ||
463번째 줄: | 283번째 줄: | ||
===== 순차 탐색 ===== | ===== 순차 탐색 ===== | ||
말 그대로 시작점부터 순차적으로 탐색하는 것이다. 전부 탐색한다고 생각할 때,연산량은 O(n)이다.<br | 말 그대로 시작점부터 순차적으로 탐색하는 것이다. 전부 탐색한다고 생각할 때,연산량은 O(n)이다.<br> | ||
솔직히 이건 해당 언어만 알면 누구나 코드를 만들어낼 수 있을 수준이기에,소스 코드 부분은 생략한다. | 솔직히 이건 해당 언어만 알면 누구나 코드를 만들어낼 수 있을 수준이기에,소스 코드 부분은 생략한다. | ||
472번째 줄: | 292번째 줄: | ||
배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정하자. | 배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정하자. | ||
배열: 1 3 4 7 8 13 17<br | 배열: 1 3 4 7 8 13 17<br> | ||
1st:총 배열의 가운데인 7을 선택.<br | 1st:총 배열의 가운데인 7을 선택.<br> | ||
7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행. <br | 7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행. <br> | ||
2nd:7~17의 배열중 가운데인 13을 선택.<br | 2nd:7~17의 배열중 가운데인 13을 선택.<br> | ||
13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행.<br | 13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행.<br> | ||
3rd:7과 13의 가운데에 있는 8을 선택.<br | 3rd:7과 13의 가운데에 있는 8을 선택.<br> | ||
8=8 이고 배열은 5번째이므로 답은 5이다. | 8=8 이고 배열은 5번째이므로 답은 5이다. | ||
단,이를 위해서는 특수한 기준으로 '''정렬'''되어 있어야 한다. 정렬법에 대해서는 아래쪽 확인. | 단,이를 위해서는 특수한 기준으로 '''정렬'''되어 있어야 한다. 정렬법에 대해서는 아래쪽 확인. | ||
아래의 소스에서는 모든 입력코드가 오름차순으로 정렬되어 있다고 가정한다. | 아래의 소스에서는 모든 입력코드가 오름차순으로 정렬되어 있다고 가정한다. | ||
< | <source lang="c"> | ||
//헤더 부분 | //헤더 부분 | ||
int solve(int,int); | int solve(int,int); | ||
502번째 줄: | 322번째 줄: | ||
return -1; //찾는 값이 없을 경우 -1을 준다. | return -1; //찾는 값이 없을 경우 -1을 준다. | ||
} | } | ||
</ | </source> | ||
이것을 변형하면,배열의 어디부터가 어떤 숫자 이상인지 혹은 초과인지 알 수 있다.<br | 이것을 변형하면,배열의 어디부터가 어떤 숫자 이상인지 혹은 초과인지 알 수 있다.<br> | ||
전자가 Lower bound,후자가 Upper bound이다. 이들은 아예 <algorithm>에 포함된 함수가 있으니 한번 봐두자. | 전자가 Lower bound,후자가 Upper bound이다. 이들은 아예 <algorithm>에 포함된 함수가 있으니 한번 봐두자. | ||
< | <source lang="cpp"> | ||
//헤더 | //헤더 | ||
#include<algorithm> | #include<algorithm> | ||
514번째 줄: | 334번째 줄: | ||
std::upper_bound(A,A+n,k,[compare]) | std::upper_bound(A,A+n,k,[compare]) | ||
//[compare]은 비교 기준이며,이게 생략된 경우 오름차순이라고 간주한다. | //[compare]은 비교 기준이며,이게 생략된 경우 오름차순이라고 간주한다. | ||
</ | </source> | ||
=== 비선형 자료구조 === | === 비선형 자료구조 === | ||
선형 자료구조가 아닌 모든 자료구조이다. | 선형 자료구조가 아닌 모든 자료구조이다. | ||
다만,사전적인 정의를 하자면 '''i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조'''를 의미한다. | 다만,사전적인 정의를 하자면 '''i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조'''를 의미한다. | ||
==== 그래프 ==== | ==== 그래프 ==== | ||
[[파일:6n-graf.svg|섬네일|이런 거.]] | [[파일:6n-graf.svg|섬네일|이런 거.]] | ||
함수의 그래프와는 전혀 다르다. | 함수의 그래프와는 전혀 다르다. {{ㅊ|고등학교 교육과정에서 이산수학이 빠지고 행렬도 빠짐에 따라 같이 빠지게 되는 비운의 단원}} 알고리즘을 배우다 보면 자주 나오는 구조로, 점들, 그리고 점들을 연결하는 선들만으로 이루어진 [[지도]] 비스무리한 걸 연상하면 편하다. 이때의 점을 '''정점(vertex)''', 선을 '''간선(edge)'''이라고 부른다.<ref>사실 우리가 수학에서 잘만 써먹던 대로 ‘꼭짓점’과 ‘변’이라고 하면 된다. 그거랑 정확히 똑같은 개념이다. 그런데 이상하게 이 동네에서는 ‘정점’과 ‘간선’이라는 새로운 용어를 쓴다. 이래 놓고 “수학에서 말하는 그래프랑 다르다”는 식으로 생각하는 바보도 있으니 기가 막힐 노릇이다. 그래프 이론은 엄연히 수학의 일부이다.</ref> 간단한 구조체를 만들어 보자. | ||
간단한 구조체를 | |||
< | <source lang="C"> | ||
struct Edge //정점보다는 간선으로 나타내는 편이 대부분의 경우에 더 좋다. | struct Edge //정점보다는 간선으로 나타내는 편이 대부분의 경우에 더 좋다. | ||
{ | { | ||
535번째 줄: | 351번째 줄: | ||
//int cost; //가중치를 가지는 간선에 사용된다. | //int cost; //가중치를 가지는 간선에 사용된다. | ||
}; | }; | ||
</ | </source> | ||
위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다. | 위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다. | ||
그래프를 다르게 구현하는 경우도 있는데,바로 인접 행렬로 구현하는 방법과 인접 리스트로 구현하는 방법이다. | 그래프를 다르게 구현하는 경우도 있는데,바로 인접 행렬로 구현하는 방법과 인접 리스트로 구현하는 방법이다.<br> | ||
다음은 데이터를 받아서 저장하는 가중치 그래프라고 가정하자. 이 경우는 인접 행렬로 구성하는 방법이다. | 다음은 데이터를 받아서 저장하는 가중치 그래프라고 가정하자. 이 경우는 인접 행렬로 구성하는 방법이다. | ||
< | <source lang="C"> | ||
#include<stdio.h> | #include<stdio.h> | ||
553번째 줄: | 368번째 줄: | ||
int a,b,w //a와 b는 간선이 연결된 곳,w는 가중치 | int a,b,w //a와 b는 간선이 연결된 곳,w는 가중치 | ||
scanf("%d %d %d",&a,&b,&w); | scanf("%d %d %d",&a,&b,&w); | ||
G[a][b]=G[b][a]=w; | |||
} | } | ||
} | } | ||
</ | </source> | ||
인접 리스트로 구성이 가능하긴 하지만 너무 복잡해서 구현하기 까다롭다. 그래서 그래프도 함수로 정의되어 있다. | 인접 리스트로 구성이 가능하긴 하지만 너무 복잡해서 구현하기 까다롭다. 그래서 그래프도 함수로 정의되어 있다. | ||
< | <source lang="cpp"> | ||
//헤더 부분 | |||
#include<vector> | #include<vector> | ||
std::vector<int> G[101]; | std::vector<int> G[101]; | ||
//소스 부분 | //소스 부분 | ||
G[i].push_back (x); //i와 x는 연결된 그래프이다. | G[i].push_back (x); //i와 x는 연결된 그래프이다. | ||
</ | </source> | ||
이 때,탐색시간은 인접 리스트 방식의 구현이 더 짧다.(단,v가 정점이고 e가 간선이라고 가정한다.)<br | 이 때,탐색시간은 인접 리스트 방식의 구현이 더 짧다.(단,v가 정점이고 e가 간선이라고 가정한다.)<br> | ||
인접 행렬:O(v*e)<br | 인접 행렬:O(v*e)<br> | ||
인접 리스트:O(v+e) | 인접 리스트:O(v+e) | ||
639번째 줄: | 454번째 줄: | ||
여기서 DFS를 구현하는 함수의 모양은 다음과 같다. 단,그래프는 인접리스트를 활용했다고 가정한다. | 여기서 DFS를 구현하는 함수의 모양은 다음과 같다. 단,그래프는 인접리스트를 활용했다고 가정한다. | ||
<source lang="cpp"> | |||
< | |||
bool visited[101]; //방문 여부를 체크하는 배열 | bool visited[101]; //방문 여부를 체크하는 배열 | ||
void dfs(int k) | void dfs(int k) | ||
654번째 줄: | 466번째 줄: | ||
return; | return; | ||
} | } | ||
</ | </source> | ||
예제(그림)의 경우 방문 순서는 1, 2, 3, 4, 5, 7, 6, 8, 9 이다. | 예제(그림)의 경우 방문 순서는 1, 2, 3, 4, 5, 7, 6, 8, 9 이다. | ||
683번째 줄: | 484번째 줄: | ||
예제(그림)의 경우 방문 순서는 1, 2, 5, 6, 3, 4, 7, 8, 9 이다. | 예제(그림)의 경우 방문 순서는 1, 2, 5, 6, 3, 4, 7, 8, 9 이다. | ||
==== 트리 ==== | ==== 트리 ==== | ||
707번째 줄: | 491번째 줄: | ||
코드를 작성해보자. | 코드를 작성해보자. | ||
< | <source lang=c> | ||
struct Node; | struct Node; | ||
721번째 줄: | 505번째 줄: | ||
struct List *Sons; | struct List *Sons; | ||
}; | }; | ||
</ | </source> | ||
자식 노드의 수가 몇 개인지 모르기 때문에, 각 노드의 자식노드 리스트를 단방향 링크드 리스트를 이용해 저장하였다. 위의 struct Node가 하나 이상 있는 것이 트리이다. | 자식 노드의 수가 몇 개인지 모르기 때문에, 각 노드의 자식노드 리스트를 단방향 링크드 리스트를 이용해 저장하였다. 위의 struct Node가 하나 이상 있는 것이 트리이다. | ||
===== 트리 관련 용어 ===== | ===== 트리 관련 용어 ===== | ||
734번째 줄: | 518번째 줄: | ||
** 단말 노드 | ** 단말 노드 | ||
**: 자식 노드가 존재하지 않는 노드. 가지의 끝이라고 생각하면 된다. | **: 자식 노드가 존재하지 않는 노드. 가지의 끝이라고 생각하면 된다. | ||
** | ** 형재 노드 | ||
**: 부모 노드가 같은 노드. | **: 부모 노드가 같은 노드. | ||
* 가지(Branch) | * 가지(Branch) | ||
802번째 줄: | 586번째 줄: | ||
=== 문자열 === | === 문자열 === | ||
문자 | 문자 여러개가 나열되어 있는 것으로, 보통 배열로 표현한다. C에서, 문자열의 끝은 특정 문자(NULL, ASCII 0번 문자)로 정해져 있다. Java에서는 아예 기본 자료형으로 제공된다. | ||
== 기초 정렬 알고리즘 == | == 기초 정렬 알고리즘 == | ||
809번째 줄: | 593번째 줄: | ||
{{YouTube|kPRA0W1kECg}} | {{YouTube|kPRA0W1kECg}} | ||
{{ㅊ|뿅뿅뿅뿅뿅}} 일단 이걸 보고 뭘 배우면 좋을지 생각해보자. 참고로 이걸 돌릴 수 있는 프로그램이 [http://panthema.net/2013/sound-of-sorting 동영상에 적힌 웹사이트]에 있다. 직접 속도조절을 해보면서 뭐가 빠른지, 어떻게 작동하는지 등등을 유심히 관찰하자. {{--|근데 영어다.}} 참고로 소리를 직접 켜야 들을 수 있다. | {{ㅊ|뿅뿅뿅뿅뿅}} 일단 이걸 보고 뭘 배우면 좋을지 생각해보자. 참고로 이걸 돌릴 수 있는 프로그램이 [http://panthema.net/2013/sound-of-sorting 동영상에 적힌 웹사이트]에 있다. 직접 속도조절을 해보면서 뭐가 빠른지, 어떻게 작동하는지 등등을 유심히 관찰하자. {{--|[[영포자도 쉽게 알 수 있는 영어|근데 영어다.]]}} 참고로 소리를 직접 켜야 들을 수 있다. | ||
영상을 보다보면 마지막의 보고(Bogo) 정렬은 결과를 보여주지 않는걸 보고 의아해 할 수도 있는데, 보고 정렬은 모든 값을 랜덤하게 줄세우는걸 반복하다보면 '''언젠가는''' 정렬이 된다는 식으로 동작하는 알고리즘이라서 그렇다(...) 알고리즘의 구성도 랜덤배치->정렬여부 확인의 무한루프. 당연하지만 효율성은 바닥을 긴다. 잘하면 한방에 정렬되지만, 영원히 정렬되지 않을 수도 있다. [[기글 하드웨어]]의 한 유저가 10개의 값으로 테스트하니 결과를 보기까지 '''4천만번'''의 읽기작업이 수행되었다고 한다.<ref>http://gigglehd.com/zbxe/10760945</ref><s>설마 이런데도 배우고 싶다고는 안하겠지?</s> | 영상을 보다보면 마지막의 보고(Bogo) 정렬은 결과를 보여주지 않는걸 보고 의아해 할 수도 있는데, 보고 정렬은 모든 값을 랜덤하게 줄세우는걸 반복하다보면 '''언젠가는''' 정렬이 된다는 식으로 동작하는 알고리즘이라서 그렇다(...) 알고리즘의 구성도 랜덤배치->정렬여부 확인의 무한루프. 당연하지만 효율성은 바닥을 긴다. 잘하면 한방에 정렬되지만, 영원히 정렬되지 않을 수도 있다. [[기글 하드웨어]]의 한 유저가 10개의 값으로 테스트하니 결과를 보기까지 '''4천만번'''의 읽기작업이 수행되었다고 한다.<ref>http://gigglehd.com/zbxe/10760945</ref><s>설마 이런데도 배우고 싶다고는 안하겠지?</s> | ||
819번째 줄: | 603번째 줄: | ||
C언어 예제는 다음과 같다. | C언어 예제는 다음과 같다. | ||
< | <source lang="C"> | ||
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | ||
826번째 줄: | 610번째 줄: | ||
int i, j; | int i, j; | ||
for(i = 0; i < 10; i++) | for(i = 0; i < 10; i++) | ||
for(j = i | for(j = i; j < 9; j++) | ||
if(arr[ | if(arr[j] > arr[j + 1]) //j번째 원소가 다음 원소보다 크다면 바꾼다. | ||
{ | { | ||
int | int temp; | ||
temp = arr[j + 1]; | |||
arr[j] = arr[ | arr[j+1] = arr[j]; | ||
arr[ | arr[j] = temp; | ||
} | } | ||
} | } | ||
</ | </source> | ||
[[파이썬]]으로 거품 정렬을 구현하는 예제 함수는 다음과 같다. | [[파이썬]]으로 거품 정렬을 구현하는 예제 함수는 다음과 같다. | ||
< | <source lang="Python"> | ||
def bubbleSort(x): | def bubbleSort(x): | ||
length = len(x)-1 | length = len(x)-1 | ||
847번째 줄: | 631번째 줄: | ||
x[j], x[j+1] = x[j+1], x[j] | x[j], x[j+1] = x[j+1], x[j] | ||
return x | return x | ||
</ | </source> | ||
=== 선택(Selection) 정렬 === | === 선택(Selection) 정렬 === | ||
856번째 줄: | 640번째 줄: | ||
C언어 예제 소스는 다음과 같다. | C언어 예제 소스는 다음과 같다. | ||
< | <source lang="C"> | ||
int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6}; | int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6}; | ||
void sort() | void sort() | ||
{ | { | ||
int i,j,t | int i,j,t; | ||
for (i=0;i<9;i++) | for (i=0;i<9;i++) | ||
for (j=i;j<10;j++) // 이 때 j는 무조건 i보다 크다 | |||
for (j=i | if (arr[i]>arr[j]) { // j번째(뒷) 원소가 i번째(앞) 원소보다 작을 때 | ||
if (arr[ | t=arr[i]; | ||
arr[i]=arr[j]; | |||
arr[j]=t; | |||
} | } | ||
} | } | ||
</ | </source> | ||
[[파이썬]]으로 선택 정렬을 구현하는 함수는 다음과 같다. | [[파이썬]]으로 선택 정렬을 구현하는 함수는 다음과 같다. | ||
< | <source lang="Python"> | ||
def selectionSort(x): | def selectionSort(x): | ||
length = len(x) | length = len(x) | ||
886번째 줄: | 666번째 줄: | ||
x[i], x[j] = x[j], x[i] | x[i], x[j] = x[j], x[i] | ||
return x | return x | ||
</ | </source> | ||
=== 삽입(Insertion) 정렬 === | === 삽입(Insertion) 정렬 === | ||
895번째 줄: | 674번째 줄: | ||
* 구현방법 1 | * 구현방법 1 | ||
< | <source lang="C"> | ||
int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6}; | int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6}; | ||
912번째 줄: | 691번째 줄: | ||
} | } | ||
} | } | ||
</ | </source> | ||
[[파이썬]]으로 삽입정렬을 구현하는 함수는 다음과 같다. | [[파이썬]]으로 삽입정렬을 구현하는 함수는 다음과 같다. | ||
< | <source lang="Python"> | ||
def insertSort(x): | def insertSort(x): | ||
for i in range(1, len(x)): | for i in range(1, len(x)): | ||
926번째 줄: | 705번째 줄: | ||
x[j+1] = key | x[j+1] = key | ||
return x | return x | ||
</ | </source> | ||
== 다음 단계로 == | == 다음 단계로 == | ||
축하한다. 우리는 일단 밑바탕을 배운것이다. 이제 [[ | 축하한다. 우리는 일단 밑바탕을 배운것이다. 이제 [[프로그래밍/알고리즘|''다음 단계'']]로 넘어갈 차례이다. 이제부터 슬슬 긴장해야 한다. | ||
{{각주}} | {{각주}} | ||
{{쉽게 배우는 프로그래밍 입문}} |