게임 개발 기록

오픈 어드레싱 방법(Open addressing method)오픈 어드레싱 방법은 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨있다. 선형 조사법과 이차 조사법선형 조사법이란?충돌이 발생했을 때 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이다. 예를 들어서 다음과 같이 정의된 함수 f(x)가 있고 테이블의 내부 저장소가 배열이라고 가정해보자. 해쉬 함수 key % 7 그러면 키가 9인 데이터는 해쉬 값이 2이므로 인덱스가 2인 위치에 저장된다. 이어서 키가 2인 데이터가 등장했다고 가정하면, 이 경우 해쉬 값이 2이기 때문에 앞서 저장한 키가 9인 데이터와 충돌이 발생한다. 이렇듯 충돌이 발생했을 때 인덱스 값이 3인 바로 옆자리를 살피는 것이 선형 조사법이다. 따라서..

테이블이란? 테이블이란 영어를 단순 번역하면 표이다. 하지만 자료구조에서 으래 말하는 테이블의 이해하기 좋은 대표적인 예는 사전을 생각하면 된다. 사전에서 단어는 Key가 되고, 단어의 뜻이나 내용은 Value가 된다. 즉 테이블에 저장되는 데이터는 Key와 Value가 하나의 짝을 이루는 것이다. 배열을 기반으로 하는 테이블 테이블 자료구조를 배열을 기반으로 제작하여 누구나 쉽게 이해할 수 있는 예제는 아래와 같다. #include #pragma warning(disable:4996) typedef struct _empInfo { int empNum; int age; } EmpInfo; int main(void) { EmpInfo empInfoArr[1000]; EmpInfo ei; int eNum; ..

AVL은 균형 잡힌 이진트리 종류 중 하나 입니다.이진트리의 종류는 대략적으로 다음과 같습니다- AVL- 2-3 트리- 2-3-4 트리- Red-Black 트리- B 트리  자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor) 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 균형 인수를 통해서 해당 트리의 균형을 잡기 위한 척도를 잡을 수 있다.AVL트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.  이 그림과 반대로 오른쪽 트리의 깊이가 3이고 왼쪽 트리의 깊이가 1라면균형 인수는 -2일것이다.  AVL 트리의 균형이 무너지는 상태(= 이를 리밸런싱이 필요한 상황이라한다. )를바로잡는 회전은 4가지로 정리가 된다.  LL회..

struct Int{ int n; bool check;};void BubbleSort(vector arr){ int swapCount = 0; int compareCount = 0; vector minusIdx; for (int i = 0; i i; j--) { if (arr[j-1].n > arr[j].n) { swap(arr[j-1], arr[j]); //arr[i].check = true; arr[j].check = true; swapCount++; } compareCo..

int main(){ IntStack s; InitializeSTK(&s, 8); for (int i = 0; i stk = (int*)calloc(max, sizeof(int)); s->max = max; s->cur = -1; return 0;}int PushSTK(IntStack* s, int x){ if (s->cur >= s->max-1) { printf("\n\n스택이 가득 찼습니다!\n추가할 수 없습니다!\n\n"); return -1; } s->cur++; s->stk[s->cur] = x; printf("\n%d의 값이 정상 저장되었습니다!\n", s->stk[s->cur]); return 0;}int PopSTK(IntStack* s, int* x){ if (s->cur stk[s-..

완벽한 해싱 n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한 해싱이라 볼 수 있다.입력한 데이터가 뭔지 모두 알고 있을 경우에만 가능하다. 대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있다.  유니버설 해싱 유니버설 해싱은 "랜덤 해싱"으로 이해하면 더 쉽다.난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 되는 예로 퀵 정렬을 들 수 있다.이와 같이 난수의 개념을 해싱 함수에 적용한 것이다. 입력이 어떤 것들인지 정확히 알 수 없는 무작위인 경우에 항상 해시값들을 고르게 분포시켜주는 함수를 만드는 것은 어렵다.때문에 유니버설 해싱에서는 해시 함수에 난수를 적용한다.  암호화 해시 함수 다양한 길이의 ..

삽입 정렬(Insertion Sort): 이해와 구현  이번에 소개하는 삽입 정렬은보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다.하지만 전혀 다른 방법으로 정렬을 이뤄나간다.이와 관련해서 다음 그림을 보자.  위 그림의 배열은 정렬이 완료된 부분과 완료되지 않은 부분으로 나뉘어 있다.이렇듯 삽입 정렬은 정렬 대상을 두 부분으로 나눠서,정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에'삽입'해 가면서 정렬을 진행하는 알고리즘이다.그럼 다음 그림을 통해서 5,3,2,4,1의 오름차순 정렬 과정을 보이겠다.   위 그림의 가장 윗부분에서 보이듯이,첫 번쨰 데이터와 두 번째 데이터를 비교하여,정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬..

동적 계획법의 접근 방식 1단계: 동적 계획법 필요조건 분석하기 부분집합의 합과 같은 문제에 직면하게 되면먼저 이 문제를 동적 계획법으로 해결할 수 있는지를 확인해야 한다.일반적으로 주어진 문제가 다음 속성을 가지고 있다면 동적 계획법으로 해결할 수 있다. 중복되는 부분 문제 : 일반적인 분할 정복 기법과 마찬가지로,최종해(final solution)는 여러 개의 부분 문제 조합으로 표현될 수 있어야 한다.그러나 분할 정복과는 달리 특정 부분 문제가 여러번 발생할 수 있다.최적 부분 구조 : 주어진 문제에 대한 최적해(optimal solution)는부분 문제의 최적해로부터 생성될 수 있다.  위 그림을 보면 크기가 n인 부분집합은 크기가 n - 1인 부분집합에 새로운 원소 하나를 추가하여 만들 수 있다..

우선순위 큐의 구현 방법 우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다. 배열 기반 구현연결 리스트 기반 구현힙을 이용하는 방법 배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있다.참고로 다음 그림에서, 저장된 숫자는 데이터인 동시에 우선순위 정보라고 가정하였다.숫자 1이 가장 높은 우선순위를 뜻하며, 이보다 값이 커질수록 우선순위는 낮아진다고 가정하였다.  배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킨다.이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸하는 것이 어려운 일이 아니다.하지만 다음과 같은 단점이 따른다. 데이터를 삽입 및 삭제하는 과정에서데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다. 이..

동적 계획법이란?1. 메모이제이션2. 타뷸레이션3. 부분집합의 합 문제4. 문자열과 시퀀스에 대한 동적 계획법해당 게시물은 다음 작업을 수행할 수 있는 지식을 담았다. 주어진 문제에 동적 계획법을 적용할 수 있는지 분석하는 능력메모이제이션과 타뷸레이션 기법을 서로 비교하여 적절한 방법을 선택함메모이제이션을 위한 적절한 캐시 사용 방법을 찾을 수 있음직관적인 전수 조사 방법을 사용하여 주어진 문제를 분석점진적으로 최적화 알고리즘을 구현하면서 동적 계획법 해법을 개발할 수 있는 능력 해당 게시글에서는 동적 계획법에 대해 소개하겠다.그리고 컴퓨터 과학 분야에서 널리 알려진몇몇 문제를 동적 계획법으로 해결하는 방법에 대해 알아보겠다. 많은 프로그래머가 좋아하기도하고 동시에 두려워하기도 하는 동적 계획법은분할 정..