본문 바로가기

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.