삼전동해커

반복문의 수행 횟수를 입력크기의 다항식으로 표현할 수 있는 알고리즘을 다항 시간 알고리즘이라고 한다. 이동 평균 알고리즘에서도 N^2과 N으로 표현되었으니 다항 시간 알고리즘이라고 할 수 있겠다. 지수 탐색 알고리즘의 경우는 재귀함수를 사용해서 입력으로 주어지는 숫자의 개수에 따라 수행시간이 달라진다. 하지만 소인수 분해 알고리즘은 크기에 따라 수행시간이 달라진다. 소인수 분해 알고리즘은 입력 값(n)이 1이 될 때까지 가능한 모든 숫자로 n을 나눈다. n의 크기에 따라 반복문의 수행횟수가 달라진다. n이 소수일 경우, n은 div가 n-1이 될 때까지 어떤 수로도 나누어지지 않는다. 따라서 반복문의 횟수는 n-1이 된다. n이 아무리 커도 입력은 n 1개 뿐인데 수행시간이 달라진다는 건 어떤 의미인가...

이동 평균 구하는 알고리즘을 짯다. 적은 모집단을 가지고 할 때는 반복문을 가지고 하는게 시간 복잡도 측면에서 그렇게 큰 문제가 안되는데 크기가 커지면 문제가 된다. 일단 반복문으로 구하는 알고리즘을 보자. 예시로 12개월 치의 몸무게가 주어졌고 매달 3개월간의 이동 평균을 구하는 문제이다. 대충 이렇게 돌아간다. 1월과 2월은 3개월치의 자료형이 없으니 빼고, 3월부터 시작한다. 3월에는 1,2,3월의 자료형을 가지고 계산하니 배열의 인덱스로 보면 0,1,2이다. 그래서 i = 2부터 시작하는 이유도 인덱스 2가 3월이기 때문이고, j도 0,1,2가 1,2,3월을 가리킨다. 하지만 므두셀라 할아버지는 태어난 날부터 매일매일 몸무게를 쟀습니다. 그는 969세까지 살았다고 합니다. 즉, 353,685일을 ..

#include #include #define LEN 100 typedef int Data; typedef struct _cQueue{ int front; int rear; Data queArr[LEN]; }CQueue; typedef CQueue Queue; void QueueInit(Queue *pq){ pq->front = 0; pq->rear = 0; } int QIsEmpty(Queue * pq){ if(pq->front == pq->rear) return 1; else return 0; } int NextPosIdx(int pos){ if(pos == LEN - 1) return 0; else return pos+1; } void Enqueue(Queue *pq,Data data){ if(Ne..

병합 정렬(Merge Sort) 병합 정렬은 분할 정복이라는 알고리즘 디자인 기법에 근거하여 만들어 졌다. 분할 정복이란 복잡한 문제를 복잡하지 않은 문제로 분할해 정복하는 방법이다. 정복 후에는 결합 과정이 필요하다. 1.분할 : 해결이 용이한 단계까지 문제를 분할해 나간다. 2.정복 : 해결이 용이한 수준까지 분할된 문제를 해결한다. 3.결합 :분할해서 해결한 결과를 결합하여 마무리한다. 8개의 데이터를 4개로, 4개를 2개로, 2->1 로 나누어 정렬하고 크기에 맞춰 결합을 한다. 나눌 때 사용되는 방법은 재귀 함수가 있겠다. 위 사진이 병합 정렬을 도식화한 것이다. 정렬 함수를 살펴보자. void MergeSort(int *arr,int left,int right); 첫번째 인자로 정렬대상이 담긴..

퀵 정렬도 병합 정렬을 기반으로 구현한다. 마찬가지로 left와 right가 있다. left는 정렬대상의 가장 왼쪽 right는 정렬대상의 가장 오른쪽 pivot이라는 변수도 사용한다. pivot 중심점, 기준이라 볼 수 있다. 가장 왼쪽에 위치한 변수를 피버로 둔다. 여기말고 다른 위치를 피벗으로 해도 상관없다. pivot을 이용한 low와 high개념을 사용하자. low는 pivot을 제외한 가장 왼쪽 high는 피벗을 제외한 가장 오른쪽 결과적으로는 right와 high는 같은 위치에 있다. 하지만 가장 오른쪽을 피벗으로 두면 left와 low가 같은 위치에 있게된다. low의 오른쪽 방향 이동은 피벗보다 큰 값을 만날 때까지 이동한다는 의미. high의 왼쪽 방향 이동은 피벗보다 작은 값을 만날 ..

#include typedef char HData; typedef int Priority; typedef int PriorityComp(HData d1,HData d2); typedef struct _heap{ PriorityComp * comp; int numofData; HData heapArr[100]; }Heap; void HeapInit(Heap * ph,PriorityComp pc){ ph->numofData = 0; ph->comp = pc; } int HIsEmpty(Heap * ph){ if(ph->numofData == 0) return 1; else return 0; } int GetParentIDX(int idx){ return idx/2; } int GetLChildIDX(int ..

많이 알고있는 버블 정렬이다. 우선순위가 낮은, 큰 값을 맨뒤로 보내는 방법이다.(오름차순) 간단하게 구현할 수 있다. 하지만 간단한 만큼 시간 복잡도는 높아진다. 반복문이 많을수록 시간 복잡도는 높아진다. 이번엔 선택 정렬을 구현해 보자. 이 또한 시간 복잡도 면에서는 굉장히 비효율적이다. 삽입 정렬을 보자.

앞서 구현한 힙은 데이터를 기준으로 우선순위가 결정되는게 아니라 먼저 우리가 결정해서 알려줘야 했다. 원래 우선순위의 판단기준은 데이터 자체로 판단해야 한다. HInsert(&heap,'A',4); HInsert(&heap,'B',3); HInsert(&heap,'C',2); HInsert(&heap,'D',1); HInsert(&heap,'E',5); 이 부분에서 우선순위를 직접 결정해서 함수에 넘겨주었다. 이번엔 우선순위 기준을 가진 함수를 만들어 프로그래머가 만든 기준을 바탕으로 데이터의 우선순위를 결정해보자. #include typedef char HData; typedef int Priority; typedef struct _heapElem{ Priority pr; HData data; }Hea..

우선순위 큐는 앞에서 배운 큐와 비슷하지만 다른 점이 있다. 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다는 점이다. 우선순위는 프로그래머가 목적에 맞게 결정하면 된다. 그래서 우선순위 정보는 정수로 저장되어야 한다. 배열로 큐를 만들어 저장할 경우, 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치 시킨다. 이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸이 어렵지 않다. 단점은 데이터를 삽입 및 삭제하는 과정에서 데이터를 앞뒤로 밀거나 당기거나 해야한다. 또한 우선순위에 맞는 위치를 찾기 위해 모든 데이터와 우선순위 비교 연산을 해야 한다는 점이다. 연결 리스트의 경우도 비슷하게 우선순위에 맞는 위치를 찾기 위해 모든 데이터와 우선순위 비교 연산을 해야한다. 그래서 힙이라는 방식을 이용..

순회하는 방식에는 3가지가 있다. 1.전위 순회 2.중위 순회 3.후위 순회 루트 노드를 기준으로 루트 노드를 언제 방문하는가의 차이이다. 책에서는 중위 순회를 먼저 구현했다. 이렇게 2레벨에서는 간단하지만 3레벨 이상에서는 어떻게 할지 구현해보자. 순회에서 가장 중요한 개념은 재귀 함수이다. 위 그림과 같이 루트 노드 기준 왼쪽 서브 트리를 방문한다. 왼쪽 서브 트리의 맨위를 루트 노드로 생각하고 다시 왼쪽 서브 트리를 방문한다. 그러다 공 노드를 만나게 되면 재귀 함수를 탈출해 루트 노드를 만난다. 다음에 오른쪽 서브 트리를 방문한다. 1.왼쪽 서브 트리 순회 2.루트 노드 방문 3.오른쪽 서브 트리 순회 이런 식이다. 이렇게 0의 왼쪽 1이 루트 노드인 서브 트리 방문 -> 1의 왼쪽 서브 트리 방..