UpWrite

힙 # 힙이란 부모노드에 저장된 값이 자식노드의 값(혹은 우선순위)보다 항상 큰 (혹은 항상 작은) 완전이진트리이다. # 즉 힙은 다음의 세가지 조건을 만족하는 자료구조이다. 1) 항상 완전이진트리의 형태이다. 2) 부모 노드의 키값이 자식 노드의 각각의 키값보다 항상 크다. (혹은 항상 작다.) 3) 자식 노드의 키값은 자식 노드의 자식 노드보다 항상 크다. (혹은 항상 작다.) 즉 재귀적인 구조를 갖는다. # 힙에서 형제 노드끼리의 값은 비교하지 않는다. # 루트노드의 값이 항상 가장 큰 힙을 최대 힙 (Max Heap)이라 하고, 항상 가장 작은 힙을 최소 힙(Min Heap)이라 한다. # 힙과 이진탐색트리의 삽입, 삭제, 탐색시의 시간 복잡도를 비교해보면 이진탐색트리는 평균적인 경우 삽입 : L..

이진탐색트리(Binary Search Tree) # 이진 탐색 트리란 이진 트리 중 탐색을 위해서 고안된 것으로 다음과 같은 조건을 갖는다. 1) 노드N에 대해서 N의 왼쪽 하위트리에 있는 노드는 N보다 작고, N의 오른쪽 하위트리에 있는 노드는 N보다 크다. 2) 노드N에 대해서 N의 왼쪽 서브트리도, 오른쪽 서브트리도 이진 탐색트리이다. # 이진탐색트리는 정렬 기준에 대해 약하게 정렬되어 있다고 할 수 있다. # 이를 이용해 완전히 정렬된 상태를 얻고 싶다면 이진탐색트리를 중위순회하면 된다. # 이진탐색트리는 최악의 경우 탐색, 삽입, 삭제 작업에 대해서 N의 효율을 보인다. # 이는 이진탐색트리의 최악의 경우는 데이터가 한쪽 방향으로만 쏠려 연결리스트와 같은 모습이 되기 떄문이다. # 하지만 평균적..

수식 트리 # 이진트리의 활용법 중 하나인 수식트리 # 문자열로 수식을 입력받아 그 결과를 리턴해준다. # 큐와 스택은 앞에서 만든걸 활용했다. C++로 구현한 수식트리 #pragma once #include "Queue_list.h" #include "stack_list.h" #include #include #if defined(UNICODE) || defined(_UNICODE) #define tcout std::wcout #define tcin std::wcin #else #define tcout std::cout #define tcin std::cin #endif struct node { TCHAR data; node* left; node* right; }; node* MakeNode(TCHAR ..

스레이드 이진 트리 # 스레이드 이진 트리라는 말보다는 스레드 이진 트리라는 표현이 더 많이 쓰이는 것 같지만, 왠지 운영체제의 스레드와 혼동이 되므로 스레이드라 썼다. # 스레이드 이진 트리는 이진트리의 순회를 재귀함수로 구현하면 시스템 스택을 사용하므로 비효율적이기 때문에 이를 영링크를 활용하여 비재귀적으로 바꾼 트리이다. # ... 라는데 아래의 구현이 더 효율적일지는 잘 모르겠고, 일단 순회에 있어서 재귀호출을 사용하지 않게 하는데만 집중했다. # 아무리 생각해도 구현의 난이도가 쓸데없이 높아서 사용이 많이 될지는 모르겠다. # 저번 포스트의 전위, 중위, 후위 순회 부분만 비재귀로 바꿨다. 구현 코드 #pragma once template struct node { T data; node* pre..

이진트리 # 최소한의 기능만 가진 이진트리 (라지만 꼭 있어야 하는 기능들이 아직 없는듯한...) # 아무래도 미완성 느낌이 강하긴 하지만 추후에 내용을 추가하기로 결정. # 현재로서는 트리에 노드를 추가하려면 수작업으로 노드를 찾아가서 노드를 추가하는 식으로 작업하도록 되어있다. # 순회의 목적에 따라 함수포인터를 전달하도록 되어있기 때문에 이를 사용한 메인 함수도 함께 첨부했다. # 다음 포스트는 '스레이드 이진트리'와 '수식 트리'까지 다루고, 바로 '우선순위 큐와 힙', '그래프'로 넘어간 뒤, # 알고리즘 부분으로 넘어가서 탐색과 정렬에 관련된 자료구조를 다뤄야 할 듯 하다. C++로 구현한 포인터 기반 이진트리 BinaryTree.h #pragma once template struct node..

완전이진트리 # 기본적인 형태만 잡은 것으로 데이터의 삽입과 삭제는 마지막 노드에 대해서만 이루어진다고 가정했다. # 배열 기반 완전이진트리의 순회를 구현하는데 중점을 두었다. # 완전이진트리를 Absolute Binary Tree라고 생각하고 ABT라고 썼는데 CBT가 맞음... (...) C++로 구현한 배열 기반 완전이진트리 #pragma once #include template class ABT_array { T* capacity; int size; int iLastIndex; T tRet; int OrderIndex; private: int ParentIndex(int index); // 지정한 노드의 부모 노드의 인덱스를 반환 int LeftIndex(int index); // 지정한 노드의 ..

요세푸스 문제 # 문제에 대한 자세한 개요는 검색해보는 것을 추천. # 대충 요약하면 41명의 사람에 대해서 3명당 한명씩 죽이는 걸 반복했을 때, 마지막 한명이 되어 살아남으려면 몇번째 자리에 있어야 하는가? 라는 문제. # 점화식을 이용한 수학적 풀이와 이진법을 이용한 풀이도 있지만 이 포스팅에서는 생략했다. 이쪽이 궁금하면 검색해보는 것을 추천. # 프로그래밍적으로는 원형 리스트를 이용해서 푸는 문제라서 이 시점에서 풀어보았다. # 구현한 것은 max명의 사람에 대해서 die명당 한명씩 죽일때 live명의 생존자를 보여준다. # die가 0이면 첫번째 사람부터 차례대로 죽는 경우가 되고, die가 1이면 첫번째 사람 다음 사람부터 차례대로 죽는 경우가 된다. # 1명이상 건너뛰는 경우는 2이상 입력..

덱 # 리스트의 양쪽 끝 모두에서 입출력을 할 수 있는 자료구조이다. # 큐와 스택의 개념을 일반화시킨 자료구조라고 할 수 있다. # 연결 리스트나 배열 기반으로 만들 수 있는데 배열 기반으로 하면 원형큐의 형태로 만들어 중앙부분부터 채워넣는다. # 덱이 비어있는 상태에서 데이터를 빼려고 하면 널포인터를 반환한다. 덱의 변형 # 한 쪽 끝에서의 삽입 작업에 제한을 둔 덱을 입력제한덱(Input restricted deque) 혹은 스크롤(Scroll)이라 한다. # 구현은 앞부분에 삽입하는 것을 제한하는 형태로 만들었다. # 한 쪽 끝에서의 제거 작업에 제한을 둔 덱을 출력제한덱(Output restricted deque) 혹은 셸프(Shelf)라고 한다. # 구현은 뒷부분에서 제거하는 것을 제한하는 형..

수식 계산기 # 중위 표현식으로 적혀진 수식을 후위 표현식으로 변환하여 계산한 결과를 리턴한다. # 수식은 문자열로 입력 받는다. # 수식은 괄호가 없고 한자리 수의 사칙연산임을 가정했다. # 즉, +-보다 */를 먼저 계산하도록 한 것 뿐이다. # 원래는 괄호까지 처리할 수 있어야 하는데 자꾸 문제가 생겨서 나중에 시간나면 처리하기로 했다. # 스택과 큐는 연결 리스트 기반을 사용했다. # run함수에 수식을 전달하면 계산 결과를 리턴받을 수 있다. 스택&큐 구현은 생략 (앞의 포스트 참조) 계산기 구현 #pragma once #include "Queue_list.h" #include "stack_list.h" #include #include #if defined(UNICODE) || defined(_..

회문 확인하기 # 문자열을 큐와 스택에 각각 넣고, 빼서 확인하면 큐에 넣은 문자열은 그대로 나오고, 스택에 넣은 문자열은 뒤집어져서 나온다. # 이렇게 나온 문자를 각각 확인해서 모두 같으면 그 문자열은 회문이다. # 입력된 문자열의 길이를 확인할 수 있으므로 배열 기반 스택, 큐를 사용했다. # 배열 기반 큐를 원형큐로 만드는 부분은 삭제했다. 배열 기반 스택 #pragma once template class StackArray { T* capacity; int size; int top; public: bool Push(T data); bool Pop(); T& Peek(); int Count(); int CapacitySize(); public: StackArray(int size); virtual..