UpWrite

완전이진트리 # 기본적인 형태만 잡은 것으로 데이터의 삽입과 삭제는 마지막 노드에 대해서만 이루어진다고 가정했다. # 배열 기반 완전이진트리의 순회를 구현하는데 중점을 두었다. # 완전이진트리를 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); // 지정한 노드의 ..

일러두기 # 선형구조에서는 데이터를 저장하고 꺼내는 것이 중요한 작업이었지만 비선형구조에서는 저장된 데이터가 그 구조로 잘 표현되어 있는지가 더 중요하다. # 즉, 삽입과 삭제는 데이터의 표현을 위해 기본적으로 제공되는 것이고, 목적에 맞는 검색과 순회가 가능한지가 더 중요하다. 트리의 구현 # 저장과 삭제가 빈번하게 이루어져야 한다면 트리를 배열을 기반으로 구현하는 것은 비효율적이다. # 하지만 데이터의 구조가 완전이진트리라면 배열로 구현하는 것이 검색과 순회에 있어서 더 효율적일 수 있다. # 그리고 이러한 구조의 완전이진트리는 다음에 소개할 힙에 활용된다. 배열로 구현한 완전 이진트리의 특징 # 뿌리 노드의 인덱스가 0일 경우 1) 인덱스 [K]에 있는 노드의 왼쪽 자식은 인덱스 [2*K+1]에 오..

트리의 정의 # 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. # 트리란 정점(vertex)과 정점과 정점 사이를 연결시켜주는 간선(edge)으로 이루어진 순환 구조가 없는 특별한 형태의 연결 그래프(Graph)의 일종이다. # 즉, 트리는 이 다음에 다룰 그래프의 특수한 형태이다. 이 정의는 그래프를 공부하고 나면 더 잘 이해가 될 것이다. # 트리는 다음 조건들을 만족하는 하나 이상의 노드로 구성된 유한 집합이다. 1) 모든 노드가 시작되는 특정한 뿌리 노드(root node)가 존재한다. 2) 노드와 노드 사이의 간선이 하나만 존재한다. 3) 각 노드들 사이에 순환이 존재하지 않는다. 4) 뿌리 노드를 제외한 다른 노드들도 자신을 뿌리 노드로 하는 트리..

요세푸스 문제 # 문제에 대한 자세한 개요는 검색해보는 것을 추천. # 대충 요약하면 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..

대기 손님 시뮬레이션 # 설명 생략(..) 큐 (대기자 목록 때문에 조금 수정) #pragma once template struct node { T data; node* next; }; template class QueueList { node* pFront; node* pRear; node* pCursor; int iCount; public: int Add(T data); int Remove(); T Peek(); int Count(); //대기 목록 보여주기용 void ResetCursor(); node* Next(); public: QueueList(); virtual ~QueueList(); }; template QueueList::QueueList() { pFront = nullptr; pRear..

스택을 이용해서 문자열 뒤집기 # 입력받은 문자열의 길이를 확인할 수 있으므로 배열 기반 스택을 사용했다. #include "stack_array.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 int main() { TCHAR str[256] = { 0, }; tcout str; int strLen = _tcslen(str); StackArray rStr(strLen); for (int i = 0; i < strLen; i++) { rStr.Push(..

원형큐 # 일반적인 큐가 시작과 끝이 있는 선분의 형태라면 원형큐는 시작과 끝을 이어 고리형태를 이루게 한 구조이다. 배열 기반 큐의 문제점 # 배열 기반의 큐를 선형큐로 만들면 문제가 되는 것이 두가지 있다. # 첫째는 front를 항상 0번 인덱스로 유지하기 위해서는 Remove때마다 데이터를 이동시켜야 한다는 것이다. # 이를 해결하기 위해서는 Remove시에 front의 인덱스를 다음 인덱스로 이동시켜야만 한다. # 두번째 문제는 Add와 Remove를 반복할 시 Front와 Rear의 위치가 배열의 뒷부분으로 이동되어 앞부분에 공간이 있음에도 오버플로우가 발생한다는 것이다. 배열 기반 큐의 문제 해결 방법 # 배열 기반의 큐에서 이를 해결하는 방법은 두가지다. # 하나는 오버플로우가 발생했을 때..