기록은 기억을 지배한다

동적계획법 DP(Dynamic Programming) 이란 어떤 문제를 풀기 위해 과거에 구한 해를 활용하는 방식의 알고리즘을 말한다. 말로 설명하면 이해하기 어려울 수 있기 때문에 가장 대표적인 예시 피보나치 수열을 살펴보겠다. 피보나치 수열은 첫항과 둘째항이 1, 1로 그다음 항부터는 앞의 두 항을 더하는 식이다. f(n) = f(n-1) + f(n-2) 수식으로 표현하면 위와 같다. 123456789101112131415161718192021222324#includeusing namespace std;int f[100]={0}; int fib(int n){ if(n==0) return 0; else if(n==1) return 1; else if(f[n]) return f[n]; else{ f[n]..

BFS(Breath First Search)는 말그대로 너비를 우선 탐색한다. DFS는 연결된 노드를 계속 들어가며 재귀호출하는 방식이었지만 BFS는 이와 달리 queue를 이용해서 루트노드에 연결되어있는 모든 노드를 다 탐색 후에 다음 깊이로 들어간다. 소스로 확인하면 다음과 같다. 1234567891011121314151617181920212223242526272829303132333435#include#includeusing namespace std;int map[10][10]={0};int visit[10]={0};queue q;int num; void bfs(int v){ cout

위와같이 값이 알파벳으로 되어있는 트리를 만들 것이다. (출처 : 백준 1991번 트리순회) 1.노드 생성 이진트리를 구성하기 위해 node라는 구조체를 만든다. 1 2 3 4 5 struct node { node* left; node* right; char value; }; cs 구조체 안에는 위와 같이 실제값, 왼쪽노드를 가리키는 left포인터, 오른쪽 자식을 가리키는 right포인터로 구성된다. 2.트리 생성 새로운 node를 생성 할 때에는 1 2 3 4 5 node *tree; tree = (node*)malloc(sizeof(node)); tree->value = 'A'; tree->left = NULL; tree->right = NULL; cs 위와같이 포인터로 생성하고 동적할당을 해준다. ..

DFS (Depth First Search) 깊이 우선탐색으로 말 그대로 탐색할 수 있는 만큼 깊게 들어가 순차적으로 탐색하는 방법이다. 아래와 같은 그래프 형태에서 한 시작점 노드(v)에서 연결된 모든 노드(w1,w2,w3)들 중 w1부터 탐색하는데 한번 w1를 탐색하면 해당노드(w1)에 연결된 노드들을 우선적으로 찾아 계속 연결된 노드를 탐색한다. w1의 탐색이 완료되면 다시 v기준으로 w2를 탐색하고 이를 반복한다. 이를 소스로 구현하면 다음과 같다.12345678910111213141516171819202122232425262728293031323334353637#includeusing namespace std;int maps[10][10];int visited[10]={0};int num;voi..

안녕하세요 오늘은 자료구조의 연결 리스트를알아보겠습니다. 리스트란 순서를 가진 항목들의 모임이라고 할 수 있습니다. 예를 들어 요일(월화수목금토일), 한글자음(ㄱㄴㄷ...) 등 순서가 있는 항목들로 이루어진 집합입니다. 기존의 배열과는 다르게 메모리를 동적으로 할당하여 메모리의 낭비없이 자유롭게 삽입 및 삭제가 가능하고, 그 크기가 제한되지 않습니다. 다만, 구현이 복잡한 단점이 있습니다. 위의 그림처럼 하나의 박스를 노드(Node)라고 하는데, 한 노드에는 데이터필드와 링크필드로 구성되어있습니다. 데이터필드는 해당 노드의 값이고 링크필드는 다음에 오는 노드를 가리키는 포인터값이 들어갑니다. 가장 첫 노드를 가리키는 포인터는 헤드포인터, 가장 마지막노드가 가리키는 link값은 NULL이 들어갑니다. 1 ..

안녕하세요, 이번엔 자료구조의 아주 기본인 큐를 배워보도록 하겠습니다. 큐(Queue)란 사전적 의미로 줄, 대기행렬, 꼬리 등의 의미가 있는데요, 놀이공원 같은 곳에서 먼저 줄을 서면 먼저 입장하게 되는데 큐는 이러한 방식입니다. 지난번에 배운 스택과 어떤 차이점이 있을까요? 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나기 때문에 최근에 넣은 데이터가 먼저 나오는 스택(LIFO 방식)과 달리 큐는 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 방식으로, 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제가 가능한 구조입니다. 스택과의 매우 큰 차이를 아시겠나요? 그림으로 보면 다음과 같습니다. 위 그림처럼 한쪽(front)에서는 삭제가 가능하고, 다른 한쪽(rear)에서는 삽입..

안녕하세요 오늘은 삽입정렬을 C언어로 구현해보겠습니다. 삽입정렬이란 기존의 배열의 모든 값을 앞부터 정렬된 배열과 비교하여 들어갈 위치를 찾고, 그 위치에 삽입하며 정렬해나가는 방법입니다. 바로 소스를 통해 알아보겠습니다. 1234567891011121314151617181920#include int main(){ int arr[5]={5, 16, 1, 4, 12}; int temp; for(int i=0;i arr[j+1])&&(j>=0)){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; j--; } } for(int i=0;i

안녕하세요 이번엔 다양한 정렬법중 선택정렬을 C언어로 구현해보겠습니다. 선택정렬이란, 배열내의 모든 항을 순차적으로 탐색하여 가장 작은 값을 제일 앞의 값과 바꿔가며 정렬하는 방법입니다. 선택정렬은 다른 정렬에 비해 비교적 구현이 쉽지만, 속도가 느린 단점이 있습니다. 다음은 소스코드입니다. 1234567891011121314151617181920212223#include int main(){ int arr[5]={13, 5, 6, 2, 9}; int min=100; int min_index,temp; for(int i=0;i

안녕하세요 , 이번엔 C언어 알고리즘의 기초인 버블정렬(bubble sort)를 C로 구현하겠습니다. 정렬에는 삽입정렬, 버블정렬, 선택정렬 등 여러가지 방법이 있습니다. 그 중 버블정렬이란, 배열 내의 처음부터 인접한 두 데이터를 비교하며 값이 큰 데이터를 뒤로 바꾸면서 배열의 끝까지 반복하여 정렬하는 법입니다. 여러 정렬법중에 코드는 가장 간단하지만 시간이 가장 오래걸린다는 단점이 있습니다. 이를 C로 구현해보았습니다. 123456789101112131415161718192021222324#include int main(){ int arr[5]={10, 3, 15, 12, 1}; int temp; //swap을 위해 선언 for(int i=0;i

안녕하세요 이번엔 C언어로 Stack을 구현해보겠습니다. 자료구조의 매우 기초적인 개념인 Stack이란 영어로 쌓아놓은 더미란 뜻입니다. LIFO(Last In First Out) 방식으로 가장 최근에 들어온 데이터가 가장 먼저 나가게 됩니다. 스택의 구조는 위와 같이 더미처럼 구성되어 있고 push&pop을 통해 데이터를 입력 또는 출력 할 수 있습니다. 단, 출력시에는 더미의 가장 위에있는 데이터를 빼온 다는 것이 매우 중요합니다. 이제 C언어로 구현해보도록 하겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #..