MOLOKINI

합병정렬(Merge Sort) 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다. 이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다. - 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다. 1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다. 2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다. 3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다. 합병정렬의 특징 삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 ..

쉘 정렬(Shell Sort) 쉘 정렬은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법입니다. 쉘 정렬의 속도는 삽입정렬의 O(n^2)보다 빠릅니다. 쉘 정렬의 속도는 약 O(n^1.5) : 몇개로 그룹들을 나누느냐에 따라 실행속도가 달라집니다. 삽입정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것입니다. 만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 이미 정렬된 요소들이 많은 이동을 해야만이 제자리로 삽입될 수 있습니다. - 정렬 위치 이후의 모든 요소들이 한 칸씩 옆으로 이동해야 정렬이 됨 쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있습니다. 1. 정렬해야 할 ..

버블정렬 (Bubble Sort) 버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행합니다. 이렇게 되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 되는데 이 과정을 스캔이라고 합니다. 이 스캔 과정을 반복하며 숫자가 정렬될 때까지 반복 수행합니다. 레코드의 이동 과정이 마치 물 속에서 거품이 보글보글 떠오르는 것과 유사하다고 하여 버블정렬이라고 부릅니다. 1. 인접한 2개의 레코드 비교, 작은 숫자를 앞으로 교환 2. 가장 큰 수가 오른쪽 끝으로 가게 됨 3. 1의 과정을 다시 진행하여 모든 숫자가 정렬될 때 까지 반복 스캔 과정 버블정렬의 특징 버블정렬은 안정성이 있고, 비효율적인 정렬입니..

삽입정렬 (Insertion Sort) 삽입정렬은 손안의 카드를 정렬하는 방법과 유사합니다. 즉, 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다. - 새로 삽입될 카드의 수 만큼 반복하면 전체 카드가 정렬 1. 리스트의 처음부터 값을 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단 2. 해당 위치에 이 숫자를 삽입하게 되면 정렬된 부분의 크기는 하나씩 커지며 자리이동 3. 정렬되지 않은 부분은 크기가 하나 줄어듦 의 순서를 반복합니다. 삽입정렬의 특징 삽입정렬은 안정성이 있으며, 비효율적입니다. 처리속도는 선택정렬과 마찬가지로 O(n^2)입니다. 삽입정렬 코드

선택정렬 (Selection Sort) 선택정렬은 가장 이해하기 쉬운 정렬 방법입니다. 리스트 중 가장 작은 숫자를 선택하여 왼쪽 부터 정렬시켜 나가는 작업을 반복하는 정렬입니다. 아래는 선택정렬의 순서입니다. 선택정렬의 특징 선택정렬은 안정성이 없고 비효율적이지만 구조가 단순하여 구현이 간단하다는 장점이 있습니다. 레코드 갯수의 -1번 반복하여 정렬을 완료합니다.처리속도 O(n^2) - 안정성 : 입력 데이터에 동일한 키 값을 갖는 레코드가 여러개 존재할 경우 이들의 상대적인 위치가 정렬 후에도 그대로 바뀌지 않는 것을 안정성 있는 정렬 이라고 합니다. 선택정렬 구현 [출처] 게임프로그램을 위한 C++ Day-69 : 자료구조1 - 선택 정렬|작성자 1따봉1비행기

트리 (Tree) 지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(Linear Data Structure)만을 공부했습니다. - 선형 자료 구조는 자료들이 직선과 같이 나열되어 있는 구조를 의미합니다. 만약 선형이 아니고 자료가 계층적인 구조를 가지고 있다면 어떻게 해야할까요? - 조상과 자손, 전체와 부분, 상사와 부하직원, 컴퓨터의 디렉토리 구조 등의 계층적 관계입니다. - 이런 계층적인 관계를 표현하기에는 선형 자료 구조로는 한계가 있습니다. 트리는 이러한 계층적인 구조를 표현하는데 사용하는 자료구조입니다. - 인공지능 문제에서도 트리가 사용됩니다. 의사결정트리 등 트리의 용어들을 알아보겠습니다. 노드 : 트리의 구성요소들 루트노드 : 부모가 없는 노드, 트리는 하나의 루트노드만 가집니다. 리프..

덱 (Deque) 덱은 Double-Ended Queue의 줄임말로 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐를 의미합니다. 덱은 스택과 큐의 연산들을 모두 가지고 있습니다. 예를 들면 add_front, delete_front 연산은 스택의 push, pop add_rear, delete_front 연산은 큐의 enqueue, dequeue 연산과 같습니다. 추가로 덱은 get_front, get_rear, delete_rear를 가지고 있습니다. (대소문자의 큰 의미는 없습니다) 덱은 보통 이중 연결 리스트로 구현됩니다. - 그 이유는 전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문입니다. - 이중 연결 리스트의 첫 번째 노드와 마지막 노..

큐 (Queue) 스택의 경우 나중에 들어온 데이터가 먼저 나가는 구조인데 반해 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 구조입니다. 이러한 구조를 선입선출(FIFO : First-In First-Out)이라고 합니다. 큐의 예로는 매표소에서 표를 사기 위해 한줄로 늘어선 열을 들 수 있겠습니다. 큐의 연산은 enqueue : 큐의 뒤에 요소를 추가한다 dequeue : 큐의 앞에서 요소를 삭제한다 큐는 뒤(Rear)에 요소를 추가하고 앞(Front)에서 삭제합니다. 이러한 형태입니다. 데이터가 들어온 순서대로 앞에서 삭제되는 것을 확인하실 수 있습니다. 큐를 배열로 구현할 경우 rear와 front가 무한히 늘어나고, Dequeue 연산 이후 주기적으로 모든 요소들을 왼쪽으로 다시 이동시켜주..

스택 (Stack) 스택을 영어사전에서 찾아보면 '건초, 밀집 따위를 쌓아놓은 더미, 낟가리'를 의미한다고 되어있습니다. 예를 들면, 식당에 접시더미, 책상에 쌓여있는 책 정도로 볼 수 있습니다. 스택은 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있습니다. 이러한 형태를 후입선출(LIFO : Last-In First-Out)이라고 합니다. 스택에는 두가지 연산이 있습니다. Push : 삽입 연산 Pop : 삭제 연산 이러한 구조입니다. 즉, 스택의 맨 위에서만 입출력이 일어납니다. 가장 전형적인 스택의 사용 예로는 함수 호출에서 복귀주소를 기억하거나 undo 기능을 구현할 때에도 스택이 사용됩니다. 아래는 스택의 C++ 구현 코드입니다. 코드..

스키닝 계층구조 + 뼈대 애니메이션을 한단계 진보시킨 기법이다. 메시를 뼈대와 결합시킬 때 생성하는 행렬을 어떻게 만드느냐 하는 것이 핵심 설계 그 아래 세개의 클래스는 ZSWSkinnedMesh, ZFFSkinnedMesh, ZVSSkinnedMesh는 스키닝을 지원하는 방식에 따라서 나눈 것. ZSWSkinnedMesh : 소프트웨어적으로 CPU연산을 통한 스키닝 방식 ZFFSkinnedMesh : Direct3D의 매트릭스 팔레트를 사용한 API 고정함수 방식 ZVSSkinnedMesh : 아직 안만들었는데, 정점셰이더를 사용해서 만들 예정 구현 - ZSkinnedMesh class ZSkinnedMesh : public ZMesh { protected: vector m_idxBones; /// 메..