게임 개발 기록

앞선 게시글에서 해시 테이블을 이용하여 필요한 키를 저장하고 검색하는 방법에 대해 알아보았다.그러나 다수의 키가 같은 해시 값을 갖는 충돌 문제가 발생한다는 점도 배웠다.이전 예시에서는 같은 해시 값을 갖는 키에 대해서는기존 키를 덮어써서 가장 최근에 추가된 키만 유지되도록 했었다.그러나 이 방식은 다수의 키글 저장할 수 없는 문제가 있다.그러므로 이러한 문제를 해결하고해시 테이블에 모든 키를 저장할 수 잇는 몇 가지 방법에 대해 알아보자.  해시 테이블에서 충돌 해결 방법1. 체이닝 2. 열린 주소 지정 2-1 .선형 탐색 2-2. 이차함수 탐색3. 뻐구기 해싱   체이닝앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.그래서 특정 해시 값 위치에 이미 원소가 존재한다면새로운 값과 예전 값 중 ..

해시 테이블과 블룸 필터를 알면 좋은 이유 대용량 데이터를 다루는 응용 프로그램에서 발생할 수 있는 룩업 관련 문제에 대해 이해할 수 있다. 주어진 문제에 대해 결정적 룩업 솔루션이 적합한지, 또는 비결정적 룩업 솔루션이 적합한지를 구분할 수 있다. 시나리오에 근거한 효율적인 룩업 솔루션을 구현할 수 있다. C++ STL에서 제공되는 일반적인 솔루션을 구현할 수 있다. 룩업은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미한다. 데이터 베이스 시스템이나 병원 관리 시스템에 저장된 방대한 자료 중에서 원하는 자료를 찾아 가져오는 작업과 같은 사례에 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요할 때가 있는데, 해시 테이블과 블룸 필터라는 두 가지..

트리 트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성한다. 트리이 계층 구조를 화면에 도식적으로 나타내려면 말 그대로 나무 형태로 나타낼 수 있으며, 이때 에지는 나뭇가지처럼 표현된다. 트리의 중심이 되는 노드를 루트 노드라고 부르고, 이 노드는 보통 가장 맨 위에 나타낸다. 즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 정 반대로 뿌리 모양처럼 생기게 된다. 그 외에도 다양한 트리 모양이 있다. 연습 문제 : 조직도 구조 만들기 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; // 새로운 트리를 만드는 정적 함수로 트리 구조를..

컨테이너 어댑터 이번 게시글에서는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너를 알아볼 것이다. 기존 컨테이너를 감싸는 래퍼를 제공하는 데에는 몇 가지 이유가 있다. 코드에 좀 더 의미를 부여하고 싶거나, 또는 특별한 인터페이스를 새롭게 제공하고 싶은 경우가 대표적이다. 이러한 자료 구조 중의 하나가 스택이다. 스택은 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용한다. 기능적인 측면에서 스택은 컨테이너의 한족 끝에서만 데이터를 삽입하거나 삭제할 수 있으며, 한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다. 벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다. 그러나 벡터나 덱을 직접 스택처..

그리디 - 분할 가능 배낭 문제 그리디 방법으로 풀 수 있는 문제로 널리 알려진 배낭 문제에 대해 알아보겠다. 먼저 0-1 배낭 문제(0-1 knapsack problem)이라고도 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다. 그러나 0-1 배낭 문제를 조금 변경한 분할 가능 배낭(fractional kanpsack problem)은 그리디 방식으로 해결할 수 있다. 이 두 가지 문제를 살펴보면서, 문제 정의의 작은 차이가 문제 해결 방법에 큰 변화를 가져올 수 있다는 점을 확인하자. 0-1 배낭 문제 물건들의 집합 O = { ... }이 있고, 여기서 i번째 물건 O[i]의 무게는, W[i]이고, 가격은 V[i]이다. 그리고 최대 무게를 T까지 견딜 수 있..

그리디 알고리즘 그리디 알고리즘은 매 단계에서 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다. 즉, 그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다. 예를 들어, 네비게이션이 인천국제공항에서 강남역까지 차로 이동하는 최단 경로를 보여주는 것 처럼 말이다. 이 경로상에 있는 임의의 두 지점을 선택할 경우, 이 두 지점의 최단 이동 거리는 처음에 구한 전체 최단 경로를 따라 이동함으로써 구할 수 있다. 전체 최단 경로는 사실상 이 경로상에 존재하는 다수의 지점 사이를 최단 거리 경로로 모두 연결시켜 놓은 것이라고 볼 수 있다. 그러므로 어느 두 지점 사이의 최단 경로를 구하기 위하여 다음과 같은 방법을 사용할 수 있다. 즉, 출발 지점에서 아직 방문하지 않은..

C++ Standard Library 의 deque deque deque란? 덱(deque)은 양방향 큐(double-ended queue)의 약자이다. 벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이든다. std::deque를 사용하면 이러한 단점을 극복할 수 있다. 덱의 구조 C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며, 어떻게 구현해야 하는지는 정의하지 않는다. deque는 list 혹은 vector보다 구현이 약간 복잡한데, deque는 다른 컨테이너만큼 단순하지는 않기 때문에 실제 구현은 좀 더 다른 형태일 수 있고, 많은 최적화 기법이 적용되었을 수 있다. 그러나 기본 개념은 같다. 즉, 이러한 컨테이너를 구현하려면 연속된 메모리 청..

C++ Standard Library 의 list std::list list란? std::forward_list는 아주 기본적인 형태로 구현된 연결리스트이다. std::forward_list는 다른 유용한 기능 중에서도 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않는다. 이는 메모리를 적게 쓰고 성능을 유지하기 위함이다. 이외에도 std::forward_list의 반복자는 매우 적은 기능만 지원한다. 컨테이너의 크기를 얻어오거나 자료 구조 맨 뒤에 새로운 데이터를 추가하는 등의 기능은 매우 유용하고 빈번하게 사용되지만, std::forward_list에서는 지원되지 않는다. 그러므로 std::forward_list의 단점을 보완하기 위해 std::list를 C++에서 ..

1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐 (Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 1.2힙이란? 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태) 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 힙의 종류 최대 힙(Max Heap) 부..

자료구조와 알고리즘이란? 자료구조는 데이터의 구조이고,알고리즘은 작업 과정의 묘사이다. 시간 복잡도 정의하기 실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같다. 시간 복잡도 유형빅 - 오메가 (Ω(n)) : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법빅 - 세타 (Θ(n)) : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법빅 - 오 (O(n)) : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법코딩 테스트에서 어떤 시간 복잡도 유형을 사용해야 할까? 코딩 테스트에서는 빅 - 오 표기법 (O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다.응시자가 작성한 프로그램으로 다양한 테..