Twinparadox Factory

앞선 글에서(링크) 이야기했던 대로, BuildHeap Algorithm은 다음과 같은 순서로 알고리즘이 진행된다. 가장 먼저 i=[n/2]=15로 시작하여 DownHeap을 호출해, i가 1이 될 때까지 총 15회 DownHeap을 호출한다.이 때 i에 대응되는 노드를 '시작 노드'라고 했을 때, DownHeap은 시작 노드의 값을 자식 노드들의 값과 비교해 힙 조건이 만족되는 순간까지 시작 노드의 값을 아래 쪽으로 자리를 바꾸며 이동시키는 작업을 실시한다. 즉, 시작 노드를 루트 노드로 간주하여 부분 힙를 구성하고,그 부분 힙을 합쳐나가는 과정을 거치는 것이다. 힙을 만드는 알고리즘 BuildHeap의 시간 복잡도가 O(n)인 이유는 아래와 같이 증명할 수 있다. n=31(노드 수 31개)인 경우, ..

힙(혹은 히프)은 최솟값(또는 최댓값)을 빠른 시간에 접근하게 만들어진 자료구조로, 최댓값을 접근하려면 최대힙을, 최솟값을 접근하려면 최소힙을 사용한다. 두 힙은 대칭적인 관계를 갖고 있기 때문에, 하나를 이해하면 다른 힙은 쉽게 이해할 수 있다. 힙에 대해 정확히 모르는 사람들을 위해서 이해를 돕기 위한 그림과 힙의 조건에 대해서 이야기를 잠깐 하겠다. 힙은 위 그림처럼, 각 노드의 값이 자식 노드들의 값보다 크거나 작은(클 경우 최대힙, 작을 경우 최소힙) 완전이진트리를 뜻한다. 거의 대부분이 정렬 파트를 다루면서 힙 정렬을 통해 이 구조에 대해서 아는 경우가 대부분이다. 오늘은 힙이 어떤 식으로 생겼는지 보는 것보다는, 힙 자료구조를 구성하는데 요구되는 시간복잡도가 O(n)인 것에 대해서 이야기를 ..

알고리즘 문제를 풀면서 접했던 문제 중 하나로 순서가 정해지지 않은(정렬되지 않은) 방대한 데이터를 입력 받아 특정 구간에서의 최솟값을 구하는 문제가 있었다. 하나씩 모두 비교하는 방법을 사용하는 건 구현은 간단하지만, 전체 구간에 대한 최솟값을 구하는 경우 O(N)의 시간 복잡도를 갖게 되고, 거기에 이러한 쿼리가 최대 M회 실시된다고 하면 O(NM)이며, 쿼리가 N에 근접하는 문제의 경우 O(N^2)의 시간 복잡도로 실행 시간 초과가 발생할 수 있다. 구간별 최솟값을 구해두고 쿼리에 대응하는 방법을 고안해도, 최초 구성 단계에서의 시간 복잡도의 문제가 있고, 내용을 바꾸는 쿼리가 존재한다면 재구성하는 과정에서 시간 투자가 필요하기 때문에, 아무래도 기존의 단순 비교 방식을 이용한 구간 내 최솟값 산출..

입력 받은 배열을 O(n)으로 히프 트리 구조로 생성할 수 있지만, 여기서는 일단 O(nlogn)으로 진행되는 히프트리 구성을 실시했다. (이 부분에 대해서는 차후 포스팅할 생각) 최대 히프트리를 구현했고, 최대 히프트리를 바탕으로 오름차순 정렬을 하는 코드다. 내림차순 정렬을 보고 싶다면, list 배열에 넣는 인덱스 순서만 바꿔주면 되고 공부 삼아 최소 히프트리를 구현하는 것도 나쁘지 않을 것이다. 숙련자가 보기에는 이 소스는 잘 짜여진 소스는 아니라는 것을 말해주고 싶다. 처음 자료구조를 배우던 시절 구조에 대해서만 깨우치고 만든 소스라서, 불필요한 메모리 할당도 있고 히프 트리 구성에서 시간 복잡도 손실을 보기는 하지만, 히프트리를 바탕으로 힙정렬(혹은 히프정렬)을 구현하는 것까지는 문제되지 않아..

템플릿 이용해서 스택을 일반화해봤다. 클래스 활용도 연습을 해볼 겸, 템플릿 사용도 연습을 해볼 겸...다른 기능 없이 아주 일반적인 push, pop, 생성자만 구현했다.다음엔 리스트도 해볼 생각. #include using namespace std; template class Stack { int tos; T data[100]; public: Stack(); void push(T element); T pop(); }; template Stack::Stack() { tos = -1; } template void Stack::push(T element) { if (tos == 99) { cout

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 6 C언어로 쉽게 풀어쓴 자료구조9장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 24. 퀵 정렬에서 함수가 수행되면서 정렬의 매 패스마다 다음과 같은 형식으로 화면에 출력하도록 함수를 수정하라. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 5 C언어로 쉽게 풀어쓴 자료구조9장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 23. 제일 작은 값을 선택하는 선택 정렬 알고리즘을 제일 큰 값을 선택하도록 변경하라. 정수 배열은 여전히 오름차순으로 정렬되어야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #define SWAP(a,b) {int t; t=a; a=b..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 3 C언어로 쉽게 풀어쓴 자료구조9장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 21. 삽입 정렬에서 입력과 출력이 모두 동적 연결 리스트로 주어지는 경우의 삽입 정렬 함수를 구현하라. 12345678910111213141516171819202122232425#ifndef __SINGLE_LINKED_LIST_H__#define __SINGLE_LINKED_LIST_H__ typedef int element;typedef struct ListNode{ element..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 4 C언어로 쉽게 풀어쓴 자료구조9장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 22. 선택 정렬의 코드를 수정하여 선택 정렬의 각 단계를 출력하도록 하라. 아래 그림에서 왼쪽 괄호 안에 있는 숫자는 정렬이 되어 있는 숫자들이다. 오른쪽은 정렬을 해야 할 숫자들이다. 선택 정렬의 단계에서 다음과 같이 출력하도록 selection_sort 함수를 수정하라. 이를 위하여 사용자로부터 숫자들을 입력받을 수 있도록 하라. 1234567891011121314151617181..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 2 C언어로 쉽게 풀어쓴 자료구조9장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 20 C언어에서는 다음과 같이 함수 포인터를 파라미터로 갖는 함수를 만드는 것도 가능하다.먼저 간단한 두 개의 함수를 작성한다. ascend(int x, int y)는 xy면 TRUE를, 아니면 FALSE를 반환한다. insertion_sort 함수에 ascend 함수를 파라미터로 전달하면 오름차순 정렬이 되도록 하고, descend 함수를 파라미터로 전달하면 내림차순 정렬이 되도록 하..