반응형 IT 이론/자료구조&알고리즘9 소팅 알고리즘 정리 (Bubble, Quick, Insert, Select, Heap) 본 글을 위 소팅 알고리즘을 한번 씩은 다뤄 본 사람들을 대상으로 기억을 되살리기 위해 적은 글이므로, 처음 보는 사람들은 좀 더 자세하게 포스팅된 글을 참고하기 바란다.설명의 편의를 위해 모든 정렬은 오름차순을 기준으로 한다. 1. Bubble Sort (버블 소트)구현하기가 가장 편해 정말 작은 input이 들어오거나, 효율성이 필요 없거나, 개발을 빠르게 해야 할 때 사용한다. 첫 번째와 두 번째 열을 비교하여 두 번째 열이 첫 번째 열 보다 작다면 두 열을 swap한다. 그 다음 두 번째 열과 세 번째 열을 비교하고, 그 다음은 세 번째, 네 번째를 비교하며 마찬가지 과정을 거친다. 이렇게 하면 가장 큰 값이 가장 마지막으로 이동되게 된다. 이젠 가장 뒷 열을 제외하고 나머지 열을 상대로 이런 과.. 2014. 10. 17. [C언어 소스] 완전이진트리 순회(Complete Binary Tree Traversal) 본 예제는 트리가 Complete Binary Tree일때만 사용 할 수 있는 예제이다. Complete Binary Tree란 Level을 기준으로 최하단을 제외한 모든 노드가 두개의 자식노드를 가지면서, 최 하단 또한 좌측 순서대로 2개씩 모두 차 있는 트리를 이야기 한다. 책에서는 어떻게 정의 하는지 모르겠으나, 대충 아래의 그림을 보면 이해 할 수 있을 것이다. 트리가 완전 이진 트리일 경우 모든 노드들은 수학적인 규칙을 가진다. 레벨 순으로 1 2 3 4 5 6 이렇게 번호를 매길 경우, 왼쪽 자식 노드 번호 = (부모 노드 번호) * 2오른쪽 자식 노드 번호 = (부모 노드 번호) * 2 +1 이라고 할 수 있다. 이런 규칙 덕분에 실제 형태는 트리 형태이더라도 표현은 1차원 배열로 표현이 가.. 2014. 10. 15. [C언어 소스] 피보나치 수열(Fibonacci number) #include int fib(int n) { if(n 2013. 11. 7. File System Implement 하드디스크는 page array이다. 메모리와 연관지어서 생각하면 된다. 프로세스를 메모리상에 allocation 하는것과 파일을 디스크에 allocation 하는것은 같은 원리이다. Memory에서는 contiguous allocation 방식이 있었고 non-contiguous인 paging방식이 있다. 하드디스크도 똑같다. 하드디스크엔 추가적으로 한개 더 있다. fopen함수를 쓰면 파일 포인터를 return한다. 이 포인터는 OS에서 정의하는 파일 table의 인덱스정보이다. 파일을 read할땐 실제로는 두개의 자료구조가 열린다. per-process open-file table, system-wide open file table. 일단 system-wide open file table이 한개 열.. 2013. 6. 12. Briefly compare the two heap-construction algorithms Make heap : bottom up, O(n), off-line algorithm, heapsort에 유용 Heap insert : top-down, O(nlogn), on-line algorithm, priority queue에 유용 Make heap은 shift_down을 사용하고 Heap insert(construct heap)은 insert_hep을 사용한다. shift_down은 구성된 ECBT에서 하위 서브트리부터 순서를 재조정하여 Heap을 구성하는 함수이고, insert_heap은 ECBT를 구성 해 가며 노드를 하나씩 추가해 나가는 것이다. sorting을 목적으로 할 경우 Make heap은 주어진 키값으로 ECBT를 구성 해 놓은 후 순서를 맞추기 때문에 새로운 값이 갑자기 추가되.. 2013. 6. 6. Branch and bound, BFS 0/1 Knapsack Knapsack 알고리즘이란, 무게(크기)가 한정된 가방이 있고, 넣을 수 있는 물건의 무게(크기)와 가격이 정해져 있을 때 어떤 물건을 버리고 어떤 물건을 넣어야 최대한의 이익을 얻을 수 있는가를 구하는 알고리즘이다. Branch and Bound에 대해서는 TSP에서 설명 했으므로 바로 문제를 풀어보자. 목적에 따라 bound를 구하는 방법만 다를 뿐 다 같은 맥락이다. 1. W = 11 i pi wi pi/wi 1 20 2 10 2 21 3 7 3 12 2 6 4 35 7 5 input 값는 이런 식으로 주어진다. pi는 물건 i에 대한 profit, wi는 weight, pi/wi는 단위무게당 profit이다. 이 input은 pi/wi이 큰 순서대로 sorting되어 들어오며, sorting되지.. 2013. 6. 6. Branch and bound 기법을 이용한 TSP Branch(가지)와 Bound(범위) 기법이란 "최적의 경우"를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다' 라는 범위(Bound)를 정 해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. 이 알고리즘으로 풀 수 있는 문제는 대표적으로 Knapsack과 TSP가 있는데, 인터넷에 있는 예제들은 대부분 Knapsack에 관한 예제이므로, 여기선 TSP를 풀어 보도록 하자. 0 5 2 4 1 6 0 5 4 3 2 3 0 4 5 2 3 4 0 1 4 2 1 3 0 위와 같은 input이 있다. 그래프는 그리지 않겠다. 이번 알고리즘은 확실히 Matrix로 보는게 더 편하다. 매트릭스를 어떻게 보는지 모르는 분들을 위해 간단하게 설명 드리자면 (1, 1),.. 2013. 5. 28. [C언어 소스] Backtracking을 이용한 N-Queen 문제 해결법 일단 N-Queen문제가 뭘까? 이 문제의 목적은 잘 모르겠으나 알고리즘을 공부하다 보면 자주 보이는 문제이다. 이 문제를 푸는 방법도 참 여러가지다. 일단 이 문제는 이름대로 장기판에 여왕말을 놓는 문제인데, 이 여왕말이 다 적이다. 어떤 여왕말이든 다른 여왕말을 먹을 수 있다는 것이다. 하지만 그걸 못 먹도록 하는게 이 문제의 핵심이다. 즉, 모든 여왕말이 다른 여왕말이 바로 공격할 수 있는 거리에 있는 것이다. 그 말인 즉슨 어떤 여왕말이 다른 여왕말을 먹으면 그 여왕말은 또 다른 말에게 먹히기 때문에 아무도 움직일 수 없는 상태인 것이다. 예를 들어 4x4의 체스 판에서는 Q Q Q Q 이런 구도라면 어떤 여왕말도 쉽사리 움직 일 수 없다. 그리고 5x5라면 Q Q Q Q Q 이런식의 결과가 나올.. 2013. 5. 26. Chainging Coin System 관련 Suppose you are in the wonder land in which the coin changing system is not governed by the greedy strategy. There are only 4 coins cl = 1, c2 = 3, c3 = 7, and c4 = 11 in the country. (a) Construct N[0..21] and P[0..21] for changing 21 wons. (b) Write a recursive program "void print_coins (int x)" to print optimal coins for x wons. You must assume that array P[0..21] is global to this program. (.. 2013. 4. 15. 이전 1 다음 반응형
