UpWrite

요세푸스 문제 # 문제에 대한 자세한 개요는 검색해보는 것을 추천. # 대충 요약하면 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의 위치가 배열의 뒷부분으로 이동되어 앞부분에 공간이 있음에도 오버플로우가 발생한다는 것이다. 배열 기반 큐의 문제 해결 방법 # 배열 기반의 큐에서 이를 해결하는 방법은 두가지다. # 하나는 오버플로우가 발생했을 때..

큐 # 큐는 영어로 줄이나 대기 행렬을 의미하는 단어로, 먼저 들어온 데이터가 먼저 빠져나가는 구조의 리스트이다. # 영어로는 'FIFO(First In First Out)' 혹은 'LILO(Last In Last Out)' 구조의 자료구조로 불린다. # 입구와 출구가 각각 있는 구조라고 생각하면 이해하기 편하다. (이때 입구로 나가거나, 출구로 들어오는건 불가능하다고 가정한다.) # 일반적으로 줄의 출구 즉 큐의 맨 앞을 Front, 줄의 입구 즉 큐의 맨 끝을 Rear라고 한다. # 일반적으로 큐에 데이터를 넣는 행위를 Enqueue 혹은 Add, 큐에서 데이터를 빼는 행위를 Dequeue 혹은 Remove라고 한다. # 큐도 배열이나 연결 리스트를 이용해서 구현할 수 있다. # 하지만 큐를 배열로 ..

연결 리스트 기반 스택 # 스택을 연결 리스트를 이용해서 구현하면 스택의 크기를 신경쓰지 않아도 된다는 장점이 있다. # 연결 리스트 기반의 스택은 pTop(=pHead) 포인터가 가리키는 노드를 바꿔주는 것으로 구현이 가능하다. # push가 되면 새로운 노드를 리스트의 맨 앞에 연결한 뒤 pTop을 새로운 노드를 가리키게 한다. # Pop이 되면 pTop의 노드를 삭제하고 pTop이 그 다음 노드를 가리키게 한다. STL의 스택 # STL에서는 선형 구조의 컨테이너를 통해 스택 구조를 이용할 수 있다. (배열 기반도 가능하고, 연결 리스트 기반도 가능하다는 뜻) 연결 리스트 기반 스택의 ADT 1. 스택에 데이터를 넣는다. (Push) 2. 스택에서 데이터를 뺀다. (Pop) 3. 스택 맨 위의 데이..

스택 # 스택이란 먼저 들어온 자료가 마지막에 나오고, 마지막에 들어간 자료가 가장 먼저 나오는 구조를 가진 일종의 리스트이다. # 영어로는 'FILO(First In Last Out)', 'LIFO(Last In First Out)' 구조의 자료구조라고 불린다. # 현실의 쌓여있는 책더미나 동전 지갑, 한쪽만 뚤려있는 통등을 생각하면 이해하기 편하다. # 일반적으로 스택에 가장 나중에 들어온 데이터의 위치를 Top, 가장 처음에 들어온 데이터의 위치를 Bottom이라 한다. # 일반적으로 스택에 데이터를 넣는 행위를 Push, 데이터를 빼는 행위를 Pop, Top의 데이터를 확인하는 행위를 Peek이라 한다. # 스택이 비어있을 때 데이터를 빼려고 하면 Underflow가 발생하고, 스택이 가득 차있을..