그래프 내의 서로 다른 두 정점 사이를 연결하는 가중치의 총합이 최소가 되도록 연결하는 방법 찾기

Dijkstra's Algorithm

양수 가중치 간선만으로 이루어진 그래프에서의 최단 경로 탐색

• 구현
  • 현재 단계 정점에서 미방문 정점으로 진출하는 모든 인접 간선을 완화한다.
  • 간선 완화가 완료되면 현재 단계 정점을 미방문 정점 집합에서 제거하고 인접 정점을 방문한다.
  • 목표 정점에 방문하거나 미방문 정점들의 시험적 거리의 최소값이 무한대, 또는 미방문 정점의 집합이 공집합이 되면 알고리즘을 종료한다.

Bellman-Ford Algorithm

음수 가중치 간선을 포함하는 그래프에서의 최단 경로 탐색, 음수 가중치 사이클 확인 과정 존재

• 구현
  • 매 단계별로 그래프 내의 모든 간선을 완화함으로써 경로를 탐색한다.
  • 음수 사이클의 포함 여부를 확인하기 위해 경로를 구한 뒤, 모든 간선에 대한 완화를 1회 수행한다. 이 때 목표 정점에 도달하기 위한 가중치의 총합이 갱샌되는 경우는 음수 사이클 포함

A* Algorithm

시작 정점으로부터 현재 정점까지의 거리에 휴리스틱 추정값을 더하여 이동 비용을 계산하는 방법

• 구현
  • 현재 단계 정점에서 미방문 인접 정점으로의 이동 비용을 완화한다.
  • 이동 비용 완화가 완료되면 현재 단계 정점을 미방문 정점 집합에서 제거하고, 인접 정점을 방문한다.
  • 목표 정점에 방문하거나 미방문 정점들의 이동 비용의 최소값이 무한대 또는 미방문 정점의 집합이 공집합이 되면 알고리즘을 종료한다.

Floyd-Warshall Algorithm

모든 정점 쌍 간의 최단 경로의 길이 탐색

• 구현
  • 시작 정점을 s, 목표 정점을 e, 경유 정점을 w 라고 하고 두점 사이의 최단 경로를 저장하는 행렬2차원 배열 D 를 만든다
  • 중간 정점 w에 대하여 D[s][e] > D[s][w] + D[w][e] 인 경우 값을 갱신하는 이중 반복문 즉, 최종적으로 삼중 반복문 형태의 반복 계산을 수행한다.

그래프의 신장 트리 중, 간선의 가중치의 총합이 가장 작은 신장 트리

Prim's Algorithm

현재 신장 트리에서 최소 가중치로 진출하는 미방문 정점 탐색

• 구현
  • 시작 정점 하나로 구성되는 최초 부분 신장 트리를 만든다
  • 현재 단계 부분 신장 트리에서 최소 가중치로 방문 가능한 미방문 정점별도 변수 저장을 찾 아 부분 신장 트리에 추가정렬 또는 우선순위 큐 사용
  • 모든 정점이 부분 신장 트리에 포함될 떄 까지 위 과정 반복
    
• 단순 구현시 O(V^2) , 우선 순위 큐 사용시 (O(V+E)log V)

Kruskal's Algorithm

간선 정렬 및 서로소 집합 구조 활용

• 구현
  • 그래프의 간선들을 가중치의 오름 차순으로 정렬한다.
  • 정렬된 간선 리스트우선순위 큐에서 최소 가중치이며, 사이클을 형상하지 않는서로소 집합 구조 간선과 정점을 부분 신장 트리에 추가
    
• O(E log E)

Boruvka's Alogrithm

그래프 축약 활용, 병렬 프로그래밍에서 효과적

• 구현
  • 주어진 그래프의 모든 정점에 대해 정점별 최소 가중치 진출 간석을 찾아 연결하여 포레스트를 만든다. 그래프 축약
  • 포레스트를 구성하는 트리들 사이에 순환이 발생하지 않고, 최소 가중치로 연결되는 간선을 찾아 연결한다.
  • 포레스트가 하나의 트리로 연결될 때 까지 위 과정을 반복한다.
    
• O(E log V)

방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘

Sequential Search

int SequentialSearch(int arr[], int size, int findVal)
{
    int index = 0;
    for (int i = 0; i < size; i++)
    {
        if (arr[i] == findVal)
        //{ 전진 이동법
        //    for (int j = i - 1; j >= 0; j--)
        //        arr[j + 1] = arr[j];
        //}
        //arr[0] = findVal;
        return findVal;
    }
    return 0;
}

배열 또는 리스트에서 특정한 값을 찾는 알고리즘

• 자주 탐색하는 데이터를 배열의 앞쪽에 배치하여 순차탐색의 계산량을 줄이는 방법
• O(n)
  
• 자기 구성 순차탐색 같은 데이터를 여러번 찾는 경우 효율이 떨어지기 때문에 탐색 빈도가 높은 데이터를 배열의 앞쪽에 배치하여 순차 탐색의 연산량을 줄이는 방법을 사용한다.
  • 전진 이동법 : 탐색된 데이터를 가장 앞쪽에 배치
  • 전위법 : 해당 데이터가 탐색될 때 마다 한 칸씩 앞으로 이동

Binary Search

void BinarySearch(int arr[], int num, int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (num = arr[middle])
            return;
        //
        if (num < arr[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }
}

이미 정렬된 상태의 배열에서 특정한 값을 빠르게 찾는 알고리즘

• 배열의 중간 인덱스에 해당하는 요소와 비교하여 배열의 크기를 절반씩 줄여나가는 형태
• O(log n)

Tree traversal

트리 구조 내의 모든 노드를 특정한 순서로 방문하는 알고리즘

• 전위 순회
• 후위 순회
• 후위 순회 트리 탐색 참조

Graph Search

• DFS : 깊이 우선 탐색

  깊이를 우선 기준으로 하여 방문하는 알고리즘

  • 정점을 방문한 뒤, 더이상 연결된 정점이 없을 때까지 인접한 정점을 재귀적으로 방문
  • O(n)
• BFS : 너비 우선 탐색

  현재 정점과 인접한 정점부터 우선으로 방문하는 알고리즘

  • 정점을 방문한 뒤, 연결된 정점을 큐에 넣은 다음 큐에서 하나씩 인출하여 방문
  • O(n)

Hashing

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑함으로써 데이터를 빠르게 탐색

• 해시code 임의의 길이의 데이터를 해시 함수를 통해 변환한 고정 길이의 데이터
• 해시 테이블 해시 코드와 그에 해당하는 데이터를 연관 컨테이너 형태로 저장하는 자료구조
  • 버킷 하나의 해시 코드를 저장하는 메모리 공간
  • 슬롯 하나의 레코드가 저장되는 공간으로 하나의 버킷에 여러 슬롯이 존재할 수 있다.
  • 오버플로 계산된 해시 코드에 해당하는 버킷 내에 저장할 메모리 공간이 없는 상태
• 해시 함수 임의의 길이의 데이터를 고정 길이의 해시 코드로 매핑하는 함수 해시 함수의 성능에 따라 해싱 알고리즘의 효율성이 결정됨
• 해시 충돌 서로 다른 두 데이터가 동일한 해시 코드로 매밍되는 경우
  • 개방 주소법 해시 테이블의 다른 버킷에 데이터를 저장해시 주소 변경
    • 선형탐사 충돌이 일어난 버킷의 다음 버킷에 저장
    • 2차 검색 충돌이 일어난 버킷으로 부터 정해진 값만큼 건너 뛴 버킷에 저장
    • 이중 해싱 충돌이 일어났을 때 다른 해시 함수를 이용해 추가 변환
    • 재해싱 테이블의 리사이징과 함께 새 해시 함수로 새 테이블 생성
  • 폐쇄 주소법체이닝 충돌 버킷에 연결 리스트를 할당하여 연결 해시 주소 유지

void BubbleSort(Data* datas, int length)
{
    for (int i = 0; i < length - 1; i++)
        for (int j = 0; j < length - i - 1; j++)
            if (datas[j].Score > datas[j + 1].Score)
                Swap(datas, j, j + 1);

• 직관적으로 이해하기에 쉽고 구현이 간단하지만 일반적으로 비효율적이다.
• pairwise 비교를 통한 정렬
• O(n^2)

Selecting Sort

void SelectingSort(Data* datas, int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < length; j++)
            if (datas[j].Score > datas[minIndex].Score) minIndex = j;
        if (minIndex != i) Swap(datas, i, minIndex);
    }
}

• 최솟값을 반복적으로 탐색하여 정렬
• O(n^2)

Insertion Sort

void InsertionSort(Data* datas, int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        if (datas[i - 1].Score > datas[i].Score) continue;
        Data current = datas[i];
        for (int j = 0; j < i; j++)
            if (datas[j].Score > current.Score)
            {
                memmove(&datas[j + 1], &datas[j], sizeof(datas[0]) * (i - j));
                datas[j] = current;
                break;
            }
    }
}

• 데이터의 삽입 위치를 탐색하면서 정렬
• O(n^2)
• 최선의 경우 O(n)

Merge sort

void Merge(Data* datas, int start, int middle, int end)
{
    int left = start;
    int right = middle + 1;
    int destIndex = 0;
    Data* dest = new Data[end - start + 1];
    // 왼쪽 부분 집합과 오른쪽 부분 집합에 대하여 순차적 비교
    while (left <= middle && right <= end)
    {
        if (datas[left].Score < datas[right].Score)
            dest[destIndex++] = datas[left++];
        else
            dest[destIndex++] = datas[right++];
    }
    // 나머지 데이터 그대로 이동
    while (left <= middle)
        dest[destIndex++] = datas[left++];
    //
    while (right <= end)
        dest[destIndex++] = datas[right++];
    //
    destIndex = 0;
    //
    for (int i = start; i <= end; ++i)
        datas[i] = dest[destIndex++];
    delete[] dest;
}
void MergeSort(Data* datas, int start, int end)
{
    if (end - start < 1)
        return;
    int middle = (start + end) / 2;
    MergeSort(datas, start, middle);
    MergeSort(datas, middle + 1, end);
    Merge(datas, start, middle, end);
}

• 데이터 균등 분할 후 합치면서 정렬
• O(n log n)
  
• 구현
  • 분할 : 데이터를 균등한 크기를 분할
  • 정복 : 부분 배열의 크기가 충분히 작지 않으면 다시 분할-정복
  • 결합 : 정렬된 부분 배열을 하나로 합친다.

Quick Sort

int Partition(Data* datas, int left, int right)
{
    UINT first = left;
    UINT pivot = datas[first].Score;
    //
    left++;
    while (left <= right)
    {
        while (datas[left].Score <= pivot && left < right)
            left++;
        while (datas[right].Score > pivot && left <= right)
            right--;
        //
        if (left < right)
            Swap(&datas[left], &datas[right]);
        else
            break;
    }
    //
    Swap(&datas[first], &datas[right]);
    //
    return right;
}
void QuickSort(Data* datas, int left, int right)
{
    if (left < right)
    {
        int index = Partition(datas, left, right);
        // 
        QuickSort(datas, left, index - 1);
        QuickSort(datas, index + 1, right);
    }
}

• pivot 을 기준으로 균등형 분할, 병합하며 정렬
• O(n log n)
• 이미 정렬된 데이터에 대해 O(n^2)
  
• 구현
  • 분할-정복 pivot 을 정하여 pivot 보다 작은 데이터는 왼쪽. 큰 데이터는 오른쪽으로 불균등 분할한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할-정복 방법을 적용한다.
  • 결합 정렬된 부분 배열을 하나로 합친다.

문제를 해결하기 위한, 명확하며 순서화 된 명령

• 입력
• 출력
• 명확성
• 유한성
• 효과성

문제 해결 패러다임 : 탐욕

최적해를 구하는 데에 사용되는 근사적인 방법 일반적으로 계산이 빠름

여러 경우 중 하나를 결정해야 할 때마다, 그 순간에 최적으로 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

• 작동 실용성 조건
  • 탐욕스런 선택 앞의 단계의 선택이 이후 단계의 선택에 영향을 주지 않는다.
  • 최적 부분 구조 문제에 대한 최적해가 부분 문제에 대해서도 최적해이다.

문제 해결 패러다임 : 분할 - 정복

분할 가능한 문제를 독립적인 작은 문제들로 분할한 다음, 각각의 부분 문제를 해결정복하고 이를 최정족으로 결합하여 문제의 해를 구하는 방법 일반적으로 재귀또는 스택, 큐 자료 구조를 활용하여 구현된다.

• 특징
  • 병렬 프로그래밍 가능
  • 재귀로 인한 함수 호출 오버헤드, 스택 오버플로 주의

문제해결 패러다임 : 동적 계획법

복잡한 문제를 여러 개의 나누어 푸는 방법 각 문제가 서로 종속적

• 메모이제이션 이전에 계산한 값을 메모리에 저장하여 동일한 계산 반복 회피
• 타뷸레이션 필요 여부와 관계 없이 미리 계산해 두어 동일한 계산 반복 회피

문제해결 패러다임 : 백트래킹

해를 찾는 도중, 해가 아니어서 막힌다면 이전 단계로 되돌아가서 다시 해를 찾아가는 방법

자료 사이의 전후 관계가 1:1 이 아닌 구조

Tree

회로cycle가 없는 연결된 그래프

이진 트리

모든 노드의 차수자식노드 개수가 2 이하로만 있는 이루어진 트리

• 종류
  • 완전 이진 트리 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉차 있는 이진 트리
  • 정 이진 트리 모든 노드의 차수가 0 또는 2인 이진 트리
  • 포화 이진 트리 모든 내부의 차수가 0 또는 2인 이진트리

그림 출저 : https://seen-ma.tistory.com

+ 완전 이진 트리

배열 구현이 간편함.

• 루트 노드의 인덱스 = 0 레벨이 낮은 노드부터 왼쪽 노드부터 인덱스 부여
  부모 노드의 인덱스가 n 일 때, 1 ) 왼쪽 자식 노드의 인덱스 : 2n + 1 2 ) 오른쪽 자식 노드의 인덱스 : 2(n + 1)

이진 트리 구조 순회

• 전위 순회
  • 루트 -> 왼쪽 부분 트리 -> 오른쪽 부분 트리 순
  • 루트로 부터 값을 누적 시킬 때 주로 사용
  • 5 9 14 33 17 18 27 11 19 21
• 중위 순회
  • 왼쪽 부분 트리 -> 현재 노드 -> 오른쪽 부분 트리 순
  • 수식 트리 구조 , 상태 판단을 하는 경우 주로 사용
  • 33 14 17 9 18 27 5 11 19 21
• 후위 순회
  • 왼쪽 부분 하위 트리 -> 오른쪽 하위 트리 -> 현재 노드 순
  • 말단 노드 삭제 , 말단 노트로 부터 값을 누적하는 경우 주로 사용
  • 33 17 14 27 18 9 19 21 11 5

이진 탐색 트리

다음의 규칙을 만족하는 이진 트리

• 모든 노드는 비교할 수 있는 키 값을 가지며 , 값들은 전순서가 있다.
• 모든 노드의 왼쪽 자손 노드들은 부모 노드보다 작은 키를 가지는 노드만 존재한다.
• 모든 노드의 오른쪽 자손 노드들은 부모 노드보다 큰 키를 가지는 노드만 존재한다.
• 이진 탐색 트리의 부분 트리는 항상 이진 탐색 트리 구조이다.
  
• 구현
  • 노트 탐색·삽입 루트 노드부터 시작하여 자손 노드가 없을 때 까지 데이터 비교
  • 노드 제거
    • 자손 노드가 없을 경우 : 노드 삭제
    • 자손 노드가 하나만 있는 경우 현재 노드의 부모 노드와 자손 노드를 연결한 뒤 노드 삭제 즉, 하위 부분 트리를 한 레벨씩 올림.
    • 자손 노드가 두 개 있는 경우 우측 자손 트리에서 최솟값을 가지는 말단 노드를 찾아 해당 말단 노드의 데이터와 삭제할 노드의 데이터를 교체 이후 해당 말단 노드 삭제
      
• 시간 복잡도
  • 트리가 균형 상태일시 탐색·삽입·삭제 시간 O(log n)
  • 최악일 시 O(n)

이진 힙 트리

다음의 규칙을 만족하는 이진 트리

• 부모 노드의 값이 자식 노드의 값보다 항상 크다 max heap
• 부모 노드의 값이 자식 노드의 값보다 항상 작다 min heap
  
• 구현
  • 노드 탐색 루트 노드만 탐색 일반적인 트리 순회 · 노드 탐색은 고려하지 않음.
  • 노드 삽입 완전 이진 트리를 유지하도록 마지막 레벨의 가장 우측 노드 자리에 삽입한 뒤 재귀적으로 부모 노드와 비교하여 힙 속성을 만족하도록 노드간 데이터 교체
  • 노드 제거 마지막 레벨의 가장 우측 노드와 루트 노드의 데이터를 교체한 다음, 힙 속성을 만족할 때까지 재귀적으로 자식 노드와 데이터를 비교하여 교체
    
• 시간 복잡도 노드의 삽입/제거의 시간 복잡도는 O(log n)이다. 시간 복잡도가 트리의 높이에만 의존
  완전 이진 트리 구조를 항상 유지해야 한다. priority queue 를 구현 하는데 사용한다.

+ STL priority queue

우선 순위가 높·낮은 순으로 요소를 인출하는 큐 구조

• STL priority_queue<_Ty, _Container, _Pr>
  • Container = vector<_Ty> 기본
  • _Pr = less<_Ty> 우선 순위를 비교하기 위해 비교 연산자가 존재한다. < : max heap 구조가 나타난다. > : min heap 구조가 나타난다.

AVL Tree

대표적 자가 균형 이진 탐색 트리

• 모든 노드에서 왼쪽 자손 트리의 높이와 오른쪽 자손 트리의 높이 차이가 1이하인 트리구조
• 이상적인 상황, 최악의상황 모두 노트 탐색/삽입/제거의 시간 복잡도가 O(log n)
• 노드 삽입/제거 시에 부분 트리를 회전함으로써 균형 유지 각 노드 별 balance factor 계산

Red-Black Tree

다음 조건을 만족하는 대표적 자가 균형 이진 트리

• 모든 노드는 레드 아니면 블랙이다.
• 모든 NIL 리프 노드는 블랙이다.
• 레드 노드의 자식 노드는 언제나 블랙이다. 블랙 노드만이 레드 노드의 부모가 될 수 있다. 따라서 루트 노드는 반드시 블랙이다.
• 임의의 한 노드에서 널 리프 노드까지 도달하는 모든 경로에는 널 리프 노드를 제외하고 항상 같은 수의 블랙 노드가 있다.
  
• 균형을 유지하기 위한 규칙들을 만족하기 위해 노드/삽입 제거시 부분 트리를 회전 노드 삽입·삭제 case 에 따른 회전 규칙이 매우 다양하다.
• 구현이 매우 까다롭지만 일반적인 경우에서 높은 성능을 보인다.
• STL 의 set , map 클래스가 red-black tree 에 기반하여 구현 되어 있다
• 균형이 적절하게 잡히므로 다른 자가 균형 이진 트리에 비해 삽입·제거가 빠르다.
  
• 시간 복잡도
  • 균형 유지 O(1)
  • 노드 탑색·삽입·삭제 O(log n)

서로소 집합 구조

상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위한 구조

• union 연산 : 서로 다른 두개의 집합을 하나의 집합으로 병합하는 연산 항상 작은 트리를 큰 트리 루트에 붙이는 형태로 유니온 연산을 구현한다. 최적화
• Find 연산 : 하나의 원소가 어떤 집합에 속해 있는지 판단. O(1) 루트 노드를 찾을 때 까지 방문한 노드들의 부모 노드를 루트 노드로 갱신한다. 최적화, 경로 압축
  
• 구현

  template<typename T>
  class DisjointSet
  {
  public :
    struct Set
    {
        T Data;
        Set* Parent;
    };
    static void Union(Set* a, Set* b)
    {
        if (a == b) return;
        Set* pa = Find(a);
        Set* pb = Find(b);
        if (pa == pb) return;
        pb->Parent = a;
    }
    static void Find(Set* a)
    {
        if (a == a->Parent) return a;
        return a->Parent = Find(a->Parent); // 경로 압축
    }
  }

그래프

정점과 각 정점을 연결하는 변으로 구성되는 자료구조

• 각각의 변간선은 가중치를 가질 수 있다.
• 트리와는 다르게 시작 정점의 위치가 고정적이지 않을 수 있다.
• 변으로 연결된 정점들 사이에 순환이 가능하다.
• 행렬 또는 연결 리스트로 구현 가능하다.

자료 사이의 전후 관계가 1:1 인 자료구조

Array

• 연속적인 메모리 공간 사용
• 동일한 타입의 데이터
• 배열 전체에 대한 잦은 할당/해제 메모리 단편화
• 인덱스 접근이 가능
• 종류
  • 일반 배열
  • STL array<_Ty, _Size> 정적 배열
  • STL vector<_Ty, _Alloc> 동적 배열

List

• 연속적이지 않은 메모리 공간 사용
• 포인터를 통한 불연속적인 연결 행태
• 노드데이터 저장 단위 단위 메모리 할당/해제
• 데이터들 사이에 삽입/해제가 비교적 편리한 구조
• 방향에 따른 단·양방향 리스트로 나뉜다.
• 종류
  • STL list<_Ty,_Allloc> 양방향
  • 구현

    template <class T>
    class List
    {
    public :
    struct Node
    {
        T Data;
        Node* Next;
        // Node * prev; 양방향
    };
    private :
    Node* Head;
    // Node* Tail; 양방향
    //...
    };

Stack

• LIFO
• 종류
  • STL stack<_Ty, _Container>
  • 구현

    #include <vector>
    template<class T>
    class StackByArray
    {
    private :
    std::vector<T> Data;
    int Top = -1;
    };
    template<typename T>
    class StackByArray
    {
    public :
    struct Node
    {
        T Data;
        Node* Next;
    };
    private :
    Node* Top;
    };

Queue

• FIFO
  • 종류
• STL queue<_Ty,_Container>
• 구현

  #include <vector>
  template<class T>
  class QueueByArray
  {
  private:
  std::vector<T> Data;
  int Front;
  int Rear;
  };
  template<class T>
  class QueueByList
  {
  public :
  struct Node
  {
      T Data;
      Node* Next;
  };
  private :
  Node* Front;
  Node* Rear;
  };

환형 큐

기본적인 큐 구조의 단점메모리 낭비을 보완하기 위한 자료구조

• 크키capacity 고정
• 환형 큐를 구현할 때 Front == Rear 인 경우 full·empty 를 구별하기 위해 실제 큐의 최대 요소 개수 -1 을 capacity 로 설정하여 관리한다.

deque

양방향 삽입/인출이 가능한 큐 구조

문자들의 집합을 의미한다.

• C/C++ 에서는 특별히 문자열을 위한 타입을 기본적으로 제공하지 않으며 문자 배열로 표현한다.
• NULL 종료 문자열을 문자열 끝에 넣어 문자열의 범위를 판별할 수 있도록 한다. 문자열을 파악하기 위해 NULL 위치를 찾아야한다.
• 문자열을 쉽게 다룰 수 있는 자료구조 string 을 C++ 표준 라이브러리에서 제공한다.

strlen

• 문자 배열 문자열의 시작부터 NULL 을 찾을 때 까지 매번 검색한다
• string 문자열 정보를 저장하고 있어 길이 정보 반환.

c_str

문자열이 저장된 위치를 반환한다.

문자열 타입 반환

Func("Hello World'); 

매개 변수 타입에 따른 함수 호출 우선 순위 const char* > string > char* > void*

문자 전용 타입으로 ASCII 인코딩을 사용하여 문자를 비트 상태와 대응시킨다. 알파벳, 특수문자, 제어문자 등으로 모든 문자의 개수가 128개 이므로 7bit 만 사용한다. 이것은 맨 왼쪽 비트가 0 으로 설정되어 있는 것을 알 수 있다.

유니코드

세상 모든 문자들에게 코드를 부여한 것을 의미한다.

• 기원 알파벳을 특정한 ASCII 코드로서는 모든 문자를 나타낼 수 없었기 때문에 각각의 문자를 표현하기 위해 char 를 변형하여 맨 왼쪽 비트가 1일 경우 char 를 2개 묶어 한 문자로 표현하는 방법을 사용하였는데 이를 코드페이지라 한다. 코드페이지는 각 문화권에 따라 개별적으로 존재하며 같은 비트를 가지더라도 다르게 해석하는 경우가 있으며 이는 언어별 호환성에 상당한 제약을 주었다. 하여 모든 문자들을 단일 코드로 통합하는 유니코드가 탄생하게 되었다.

UTF - N

유니코들를 실제 컴퓨터의 타입으로 변형하는 것으로 N 비트의 배수로 한 문자를 표현하는 의미이다.

wchar_t

C++ 에서 UTF-16·18 제공하는 데이터 타입이다. wide character 형태를 표현하기 위해선 L 매크로를 사용한다.

'A' // = char 형
L'A' // = wchar_t 형
"ABC" // = char 형 배열
L"ABC" // = wchar_t 형 배열

• 렌더링할 지오 메트리 정점 정보 및 primitive topology... 데이터 입력
• 정점 변환 월드배치 , 카메라 뷰... 구현 투영
• 레스터 라이저 각 정점 사이 픽셀화
• 화면 공간으로의 매핑을 통한 렌더링 화면 제공

버퍼 종류

• 정점 버퍼 정점 데이터를 GPU 로 전달
• 인덱스 버퍼 정점을 primitive topology 에 근거하여 도형을 그릴 시 정점 오프셋을 나타내는 정수 데이터
• 상수 버퍼 셰이더 상수 데이터를 GPU 로 전달

Tessellation ( DX11 기반 )

• 덮개 셰이더 테셀레이션 매개변수를 받아 제어점 생성 다음 단게에 사용할 데이터 생성
• 테셀레이션 전달 받은 데이터 토대로 기존 지오메트리를 작은 삼각형으로 분할하기 위한 정점 생성
• 영역 셰이더 만들어진 정점 위치 계산

오른손·왼손 좌표계

• 외적이 정의되는 방향이 서로 반대 z축의 방향 반전 관계
• 회전의 양의 방향 반대 외적 방향 = 회전축의 방향

변환과 행렬 관계

• 변환 n 차원 벡터 공간에 속한 원소를 m 차원 벡터 공간에 속한 원소로 대응시키는 것
• 선형 변환 연립일차방정식 형태로 대응 관계를 표현할 수 있는 변환 행렬 표현 가능

3차원 공간의 평행이동

• 아핀 변환을 첨가 행렬 형태로 표현 아핀 변환 | 3 차원 공간 내에서 선형 변환을 통한 평행 이동 표현 불가 첨가 행렬 | 4 차원 공간 상에서의 선형 변환 표현 가능
• 위의 평행 이동 변환이 4차원 공간 위에서의 선형 변환중 전단 변환과 동일 정점과 행렬 표현시 4차원 공간 기준 표현

짐벌락

각 기저 축에 대한 회전이 종속적 오일러각 적용 될 때 특정 축 회전에 의한 나머지 두 축이 겹쳐져 회전축의 자유도를 상실하는 현상

단위 쿼터니온의 회전 변환

• Quatainon P(qPq*, 0) 실수부 | 0 허수부 | 로드리게스 공식에 기반한 특정 회전축에 2θ 회전된 위치를 나타내는 쿼터니온
  • (P , 0) 변환할 정점 위치의 쿼터니온 표현
  • q 임의의 단위 쿼터니온
  • q* 켤레 쿼터니온

오일러각·단위 쿼터니온 장·단점

• 오일러각
  • 직관적
  • 데이터 저장 개수 | 3
  • 임의의 축 회전 연산이 번거로움
  • 짐벌락 현상 발생
• 단위 쿼터니온
  • 연산 ↑ 삼각함수 연산x
  • 구면 선형 보간 가능
  • 데이터 저장 개수 | 4

구면 선형 보간

단위 쿼터니온 4차원 공간 상의 초구위에 표현했을 때 두 쿼터니온 사이를 구면을 따라 직선으로 보간하는 방법이며 서로 다른 2개의 회전 표현에 대한 선형 보간을 의미.

직교·원근 투영

• 직교투영
  • 투영선이 투영면과 직교하도록 투영
  • 거리에 관계 없이 투영 원근감x
• 원근 투영
  • 투영선이 하나 이상의 소실점을 수렴하도록 투영 원근감o

투영 공간 변환

• 클리핑 , 컬링과 같은 렌더링 처리 기술 가능
• 렌더링할 오브젝트 역변환 가능
  평면 투영시 z 축 상실 렌더링 처리 기술, 역변환 불가

• 메모리 상 연속적인 위치
• 순차적인 액세스가 매우 빠름 캐시 메모리 작동 측면
• 직관적
• 인덱스를 통한 빠른 접근
• 특정 위치 데이터 삽입 과정이 복잡함
• 빈번한 할당·해제로 인한 메모리 단편화 우려

연결 리스트 자료구조 특징

• 메모리 상 불 연속적인 위치
• 포인터를 통한 요소 접근 default
• 헤드 노드부터 순차적 접근을 통한 요소 접근
• 특정 위치 데이터 삽입 과장이 간단함

메모리 단편화

주기억 장치의 빈 공간이 여러 개의 조각으로 나뉘는 현상

• 사용가능한 공간 축소 ↓
• 읽기/쓰기 속도 ↓
• 내부 단편화

  의도하지 않는 메모리 할당으로 낭비되는 현상 필요한 메모리의 크기보다 큰 단위로 할당되는 경우

• 외부 단편화

  프로그램이 다양한 크기의 남은 영역을 할당·해제로 인해 빈 공간이 여러 작은 조각으로 나뉘는 현상

  • 사용 가능한 메모리 공간 총합 여유
  • 메모리 할당 알고리즘 약화 프로그램 성능 저하

push · emplace

• push

  • 복사 생성자 호출 default
  • 이동 생성자 호출 r-value
  • 오버 헤드 발생 이동·복사

• emplace

  • 내부에서 객체 생성
  • 버그 발생 우려 예기치 못한 타입 변환

  높이가 n 인 포화이진트리 노드 총 개수

  2 ^ (n+1) - 1 말단 노드 제외한 모든 노드 차수가 2

  이진 힙 트리

  힙 속성을 만족하며 최댓값·최솟값을 O(1) 시간복잡도로 탐색위한 완전 이진 트리 자료 구조

  • 노드 삽입·제거 → 부모
  • 자식 노드 사이의 키값의 재귀적인 비교
  • O(log n)

  힙 속성 | 부모 노드 키 값이 자식 노드 키 값보다 항상 크거나 작은 성질

  이진 탐색 트리의 O(n) 상황

  • 불균형 상태의 극단적인 경우 발생 단순 연결 리스트와 동일
  • 자가 균형 이진 탐색 트리를 통한 해결 AVL , Red-Black 트리

  불균형 상태 | 루트 노드 기준으로 부분 트리의 높이가 한 방향으로 크게 치우져져 있는 상태 자가 균형 이진트리| 노드 삽입·제거시 규칙에 따라 부분 트리의 회전을 통해 균형을 유지하는 자료구조

  서로 집합 자료구조의 union-find 연산 최적화

  • union by rank 항상 크기가 작은 집합을 큰 집합 하위 연결하는 형태로 유니온 연산을 구현
  • 경로 압축 루트 노트들 찾을 때 까지 방문 노드를 루트 노드로 갱신

  알고리즘 복잡도 표현

  • 시간 복잡도
    • 연산 소요 시간
    • 주로 사용 현대 컴퓨터의 메모리 여유성
    • 점근 표기법 사용 상한 (빅 오), 하한 (빅 오메가), 상한·하한의 종합적 (빅 세타)
    • 최장 시간 파악 중요 default
  • 공간 복잡도
    • 연산 사용 메모리

  가변 크기 컨테이너의 Capacity

  • 시간 복잡도 요소 추가·제거 < 실제 크기 증가 매 번 요소 추가시 컨테이너 크기 증가는 재할당으로 인한 오버헤드 초래
  • 해결 방법 현재 capacity 에 비례하는 크기로 적절하게 늘리는 방식 사용

슬랙

컨테이너가 저장할 수 있는 요소 최대 개수인 capacity 와 실제 컨테이너 저장 요소 개수인 size 의 차이

분할-정복, 동적계획법 차이

• 분할-정복
  • 주어진 문제를 독립적인 작은 문제 분할
  • 부분 문제 해결
  • 결합하여 문제의 해 도출
• 동적계획법 주어진 문제를 분할 시 이전 단계의 결과가 이후 단계에서 활용되어 문제를 해결

버블·선택·삽입 정렬의 실행 속도 차이

• 버블 정렬 pairwise 비교를 통해 정렬 순서가 마지 않을 시 요소 swap 가장 느림
• 선택 정렬 최소값을 찾는 과정 반복 필요 매 → 반복마다 남아있는 요소 재탐색 중간
• 삽입 정렬 이미 정렬되어 있는 데이터가 존재 가장 빠름

삽입 정렬 O(n)

이미 정렬된 상태일 경우 삽입할 위치를 찾는 시간 복잡도 O(1)

퀵 정렬 O(n^2)

정렬된 상태에서 단계별 pivot 이 항상 최솟(최댓)값이므로 발생 선택 정렬과 동일 일반적으로 단계별로 가장 앞(뒤) 요소를 pivot 으로 사용하기 때문

기수 정렬

주어진 숫자 형식의 데이터에 대해 보조 배열을 사용하여 각 자리수마다 데이터 보관·인출 과정을 통해 정렬

• 유용한 경우
  • 데이터가 정수형
  • 여분의 충분한 메모리를 활용 가능

멀티 플랫폼 빌드를 목표로 하는 게임엔진으로 빌드과정을 유연하게 하도록 하는 툴.

• Unreal Proejct C++ 소스 빌드과정 총괄
• 다양한 빌드구성
• 빌드 프로세스 자동화 커스텀 툴
• 추장저 소스코드 구조
• 플랫폼 호환성에 맞게 프로젝트 재생성
• 독립적인 빌드 및 스크립트 환경 제공 C# 사용

bulid.cs

• 빌드 옵션 관리
• PCH 사용
• 외부 모듈 사용

targect.cs

• 빌드 타입 정의
• 특정 모듈을 빌드에 포함
• 특정 타입의 빌드 결과물 생성 dll, exe

UHT ( Unreal Header Tool )

컴파일 전 모든 헤더 파일을 순회하며 리플렉션 시스템에 필요한 정보를 읽어 C++ 컴파일러가 읽기 가능한 코드를 재생성함.

• FileName.generated.h Pasring
• 매크로 정보 저장 generated.h, gen.cpp
• 실행 순서
  • 빌드 명령
  • UBT 실행
  • bulid.cs , target.cs 컴파일
  • UHT 실행
  • C++ 컴파일러 실행

모듈 ( Moudule )

관련된 데이터와 함수를 하나로 묶은 단위.

• 독립적 컴파일이 가능 분할 컴파일
• 재사용성↑
• 유지보수↑

언리얼 모듈

특정 기능들을 독립된 코드 단위로 캡슐화 한 것 모듈

실수 표현시 소수점 위치를 고정하지 않는 것 범위가 한정적인 고정 소수점에 비해 범위가 넓음.

• Bit State 표현
  2 진법

  부호부 / 정수부 / 소수부

  정규화

  부호부 음수 1 , 양수 0 지수부 바이어스 표현법 사용 가수부 왼쪽부터 채운 옮긴 뒤 0으로 채움

바이어스 표현법

지수의 음양 표현이 정수의 음양표현 의미와 다르기 때문에 사용 지수가 0 이라면 2^0 = 1 로 1이 기본값이 되는 현상을 피하기 위하여 사용한다.

지수부가 모두 0 인 경우

정수부를 0 으로 지수를 -126 으로 표현 모든 비트가 0 이라면 0

지수부가 모두 1인 경우

가수부가 모두 0 인경우 INF 가수부가 하나라도 1인 경우 NaN

실제 지수 범위 -126 ~ 127

부동 소수점 오차

구조상 가수부 크기가 일정하기 때문에 지수가 가수부의 크기보다 커진다면 오차가 발생한다.

문자열

문자들이 모여져 있는 집합

• C++ 표준 라이브러이에서 string 클래스 자료구조 제공.
• NULL 종료 문자열로 문자열 끝을 판별 할 수 있음.

참조자

Copy Pointer 를 의미한다.

• 참조 연산자로 초기화시 주소 연산자 생략
• 직접 접근시 간접 연산자 생략
• 포인터 영역 마련후 초기화 되는 변수 주소가 포인터 영역에 써지게 되는 방식 참조 객체의 메모리 공간 확부 및 주소 복사 포인터

타입 추론형

컴파일 타임에 초기화 된 값을 토대로 타입을 추론하여 적절한 타입으로 변경하는 자료형

• 선언 즉시 초기화
• 참조 타입 사용시 키워드 앞 참조 연산자 작성

전처리 지시문

• #define
• #include
• #pragma once
• #if , #ifdef, #ifndef

가상 메모리

• 메모리 영역이 프로세스에게 독립적으로 부여
• 타 프로세스 해당 메모리 영역 침범 불가
• 메모리 부여시 운영체제, 프로세스가 절반씩 사용

malloc & free , new & delete

• malloc
  • size 를 인자로 받음.
  • 할당한 주소 void * 반환
  • stdlib.h 필요
  • 할당 가능한 영역 없을시 nullptr 반환
• new
  • 요소 개수를 받음
  • 생성자 호출 가능
  • 인자로 받은 타입으로 할당한 주소 반환
  • 할당 가능한 영역 없을시 std::bad_alloc 예외 발생
• free
  • 주소를 인자로 받음
• delete
  • 변수명을 인자로 받으며 배열 해제시 [] 작성
  • 인자로 받은 타입 확인 후 소멸자 호출

동적할당 공간 메모리 해제

• malloc 과 new 요청 힙관리자가 할당받은 메모리 분배후 부여받은 주소 , size 를 할당 내역에 기록
  
• free , delete 요청 할당 내역에 기록해 놓은 주소와 size 토대로 검사후 메모리 회수

힙관리자 : 힙 영역 관리, 프로세스 시작시 OS 에서 가상 메모리를 할당 받음

delete[]

• 동적 배열 할당 요청 내부에서 malloc 호출 시 인덱스 요소 개수를 저장할 추가로 메모리를 할당 받음. 반환시 인덱스 0 번째 주소를 반환하기 위해 추가받은 메모리 크기를 더한 주소를 받음.
  
• 해제 힙 관리자의 할당 내역을 통하여 추가로 받은 메모리 크기를 뺀 후 인덱스 요소 개수 파악 요소 개수만큼 소멸자 호출

선언 · 정의

• 정의 메모리 공간 확보
• 선언 해당 메모리 공간이 있다는 것을 알림

암시적 생성자 , 소멸자

컴파일러가 필요할 시 생성자와 소멸자가 명시되지 않았을 때 제공하는 생성자 · 소멸자

• 명시되지 않은 모든 생성자 · 소멸자에 대하여 제공시
  • 불필요한 Code 영역 차지
  • 객체 생성 , 소멸시 생성자와 소멸자를 확인하는 오버헤드 발생

포인터

메모리의 주소를 가리키는 객체로 간접 접근을 통한 메모리 낭비와 지역성이 다른 메모리에 접근이 가능하다.

• 주소와 타입 정보를 가짐.
• 메모리 주소에 타입 정보를 기반으로 접근.
• 원천 타입이 아닐 경우 혼란 발생

구조체 · 클래스

구조체 public 와 클래스 private 는 객체 지향 프로그램의 도입과 기존 라이브러리의 호환성을 보존하기 위해 나누어져 있다.

메모리 배치 규칙

맴버 변수는 변수 타입의 크기 배수 일 때 CPU 의 메모리 접근 횟수가 최소화됨. 배치시 /Zp8 기준 변수의 타입 크기와 8중 더 작은 쪽이 최소배수.

클래스 암시적 정의 메소드

기본 생성자 , 기본 소멸자 , 복사생성자 , 복사 대입 연산자 , 이동생성자 , 이동 대입 연산자

복사생성자

멤버의 값을 복사하여 생성하는 생성자 인자는 const Type &
실행순서

• 명시적

  • 초기화 리스트
  • 선처리 영역의 부모 , 클래스 타입의 맴버 기본 생성자 호출
  • 코드블럭 실행

• 암시적

  • 부모 , 클래스 타입 타입의 맴버 복사 생성자 호출
  • 기본 맴버 타입일 경우 복사 실행

  암시적 복사 대입 연산자

  대입 연산자의 오버로딩

  • 인자 const Type 반환형 자기자신
  • 실행 순서
    • 부모의 복사 대입 연산자 호출
    • 맴버가 기본 타입일 경우 메모리 복사
    • 맴버중 const 지정자나 참조 타입이 있을 시 에러 발생

• Code Area 읽기 영역 (Text Area) 제어문 , 함수 , 상수
  
• Data Area 전역 · 정적 변수 , BSS 는 초기화되지 않는 전역변수
  
• Heap Area 사용자가 관리하는 동적할당 공간
  
• Stack Area 지역변수 , 매개변수 함수 종료시 쓰레드에 해당하는 변수 해제

컴파일 과정 순서

• 전처리 (.i) 외부에 선언된 소스코드 , 라이브러리 포함 주석제거 매크로 치환 적용
  
• 컴파일 (.s) 전처리된 소스코드파일 어셈블리어 변환 언어문법 검사 정적영역 메모리 할당
  
• 어셈블리 (.o) 어셈블리어 파일 -> 오브젝트 파일 변환
  
• 링킹 (.exe) 오브젝트 파일 · 프로그램에 사용되는 라이브러리 링크 => 하나의 실행파일 변환

인출 사이클 레지스터

• PC 메모리에서 가져올 명령어 주소 저장 특별한 경우 제외 순차적 주소 값 증가

  
  

• MAR PC 에서 주소 값을 받아 메모리 접근 제어장치의 제어신호화 함께 메모리 접근

  
  - MBR MAR 에서 접근한 메모리 명령어 · 데이터 저장
  - IR MBR 에서 저장된 명령어 · 데이터 해석

  인터럽트

  CPU 가 진행하고 있던 작업을 중단시키는 상황

  • 동기 인터럽트 CPU 가 직접 작업 중단
    
  • 비동기 인터럽트 입출력 장치에서 인터럽트 요청신호 호출 ↓ FLag Register 의 IF 활성화 여부에 따라 인터럽트 결정 ↓ 현재 작업 스택에 백업후 인터럽트 백터 확인 ↓ 해당 장치의 인터럽트 서비스 루틴 실행 ↓ 백업한 작업 재개

  명령어 파이프라이닝

  명령어가 처리되는 과정을 순차적으로 처리하는 기법

  • 데이터 헤저드 데이터가 의존적일 때 둘중 하나의 명령어가 처리되지 못하는 상황
  • 컨트롤 헤저드 분기로 인한 PC 의 갑작스러운 변환 쓸모 없는 명령어 발생
  • 스트럭쳐 헤저드 서로 다른 명령어가 같은 자원 접근

  비순차적 명령어

  명렁어들이 순차적으로 실행되지 않는 기법

  • 순서가 바뀌어도 진행에 영향을 주지 않는 명령어 우선 처리 명령어 처리 딜레이 로스가 발생하지 않도록 함

  CISC · RISC

  • CISC 가변길이 명령어 복잡하고 다양한 기능 제공 메모리 관리 효율적 명령어의 크기 · 실행 시간이 일정하지 않음. 파이프라이닝 불리
    
  • RISC 명령어의 종류 축소 · 규격화된 명령어 제공 작성되는 명령어 증가 한 클럭 내외 실행 파이프라이닝 유리

  RAM 의 종류

  • DRAM 일정시간 이후 데이터 소멸을 막기 위한 재활성화 소비전력 · 비용 ↓ 집적도 ↑ 대용량 설계 유리 주기억 장치 사용
    
  • SRAM 데이터 유지 속도 ↑ 집적도 ↓ 소비전력 · 비용 ↑ 캐시메모리 사용

캐시 메모리

CPU 에서 사용될 것으로 예측되는 데이터 미리 확보후 CPU 에서 제공하는 메모리 공간

• 코어 내에서 개별 메모리 할당 L1 · L2 캐시
• 코어 외에서 각 코어 캐시 메모리 공유 L3 캐시
• 한번 접근한 곳에 접근 할 가능성 시간지역성
• 접근한 메모리와 인정한 공간에 접근할 가능성 공간지역성

컴파일 언어 · 인터프리터 언어

• 컴파일 언어 소스 코드 전체 검사 -> 저급 언어 변환 -> 실행 파일 생성
  
• 인터프리터 언어 코드를 한줄 씩 저급 언어 변환후 실행 컴파일 시간 · 실행 파일 생성 x 실행 때 마다 인터프리터 과정 반복 수행

std::vector<int> vec;
const std::vector::iterator iter = vec.begin();
// iter 는 T * const 처럼 동작한다.
*iter = 10;
++iter; // Error
>>
std::vector::const_iterator cIter = vec.begin();
// cIter 는 const T * 처럼 동작한다.
*cIter = 10; // Error
++cIter;

Iterator 는 Pointer 를 본 뜬 것이기 때문에 기본적인 동작 원리가 T* 와 흡사하여 const 로 선안한다는 것은 Pointer 를 상수로 선언하는 것과 같다. Iterator 가 자신이 카리키는 대상이 아닌 것을 가리키는 경우가 허용되지 않지만, 가리키는 대상 자체를 변경이 가능하다. 변경 불가능한 Object 를 가리키는 Iterator 가 필요하다면 const_iterator 를 사용하자.

Floating Point 에 대해 알아보기전 이해를 돕기 위하여 Fixed Point 에 대해서 알아보도록 하자.
Fixed Point 란 소수점의 위치가 고정인 것을 의미하는데 123.456 이라는 수를 표현할 경우 정수 부분과 소수부분을 나누어 표현한다. 이때 한정된 비트에 정수와 소수를 분할 배치할 경우 나타낼 수 있는 범위가 매우 한정적인데 소수점의 위치가 고정이 아니라면 어떻게 될까 ? 123456 이라는 유효숫자와 3이라는 소수점 위치를 통해서 훨씬 많은 범위의 수를 표현할 수 있게 된다. 이렇게 나온 방식이 바로 Floating Point 이다.

Fixed Point | 고정 소수점 Floating Point | 부동 소수점

Binary system of Real numbers

정수와 같은 경우 2의 보수법을 통하여 2진법으로 BitState 가 될 수 있는데 소수는 어떻게 2진법으로 표현하는 걸까 ? Floating Point 를 제대로 이해하기 위해서는 실수를 2진법으로 표현하는 방법을 알고 있어야 한다.
예시를 들어 -9.6875 를 2진법으로 나타낸다 하였을 때 부호 , 정수 , 소수로 나누어 생각한다.

부호	-	정수	9 < 1001(2) >	소수	6875

-1001.1011(2) 의 구조

위와 같이 부호는 음수이며 정수 9를 2진수로 1001 로 쉽게 변화할 수 있는데 소수부분을 어떻게 해결할까 ?
정수의 반대로 생각하여 구하면 쉬워진다. 정수와 같은 경우 다음과 같이 2진법을 사용할 수 있다. 9 / 2 = 4 ... 1 4 / 2 = 2 ... 0 2 / 2 = 1 ... 0 1 / 2 = 0 ... 1 이처럼 나머지를 구하여 1001 이라는 표현으로 2진수로 구하지 않았는가 ?

이와 같이 소수는 반대로 2를 곱하여 정수부분을 취한다. 0.6875 * 2 = 1.375 0.375 ... 1 0.375 * 2 = 0.75 ... 0 0.75 * 2 = 1.5 0.5 ... 1 0.5 * 2 = 1.0 ... 1 이 처럼 정수부분을 모두 취한 소수부분의 2진수는 1011 이 나오게 되며 -9.6875 의 2진수 표현은 -1001.1011(2) 로 나오게 된다.
위와 같은 경우에는 최종결과가 0.0이 나와 멈출 수 있지만 보통 대부분의 실수는 무한히 순환하면서 반복되어 적당한 개수의 유효숫자만을 취하게 된다.

Binary System | 2진법 Real Number | 실수

Floating Point Structure

이제 앞서 예를 들었던 -1001.1011(2) 을 이용하여 부동 소수점의 구조를 알아보도록 하자.
부동소수점으로 저장하기 위해선 정규화 과정을 거쳐야 하는데 지수를 이용하여 실수를 표현한다. -1001.1011 은 -1.0011011 * 2^3 이 되는데 여기에서 정규화란 정수부를 1로 맞추어 놓고 적절하게 소수점 위치를 조정하는 것이다. 이 때 정규화를 거친 소수부의 유효 숫자를 가수부 , 지수를 지수부로 나누어 부동 소수점을 표시한다.

부호부	-	지수부	3	가수부	0011011

-1.0011011 * 2^3 의 구조

위와 같이 보호부 지수부 가수부로 나누어 Bit 로 변환하게 되는데 이때 해당 부분들이 얼마 만큼의 Bit 가 사용하는 지 알아보자.

자료형	부호부	지수부	가수부	총 Bit
float	1 Bit	8Bit	23Bit	32 Bit
double	1 Bit	11Bit	52Bit	64 Bit

이제 위의 표를 가지고 BitState 로 변환하여 보자 부호부는 간단한데 양수면 0 , 음수면 1이다.

가수부 같은 경우엔 변환된 가수부를 왼쪽 부터 그대로 채우게 된다.

지수부와 같은 경우 8 bit 로 -127 ~ 128 까지의 256 단계를 나타내는데 이때 오해할 수 있는 것이 2의 보수를 취하여 표현하여 저장한다라고 생각 할 수 있지만 그렇지 않다. 지수부 8 bit 가 모두 0 으로 채워진 [ 0000 , 0000 ] 은 -127 을 나타내고 1 증가한 [0000, 0001] 은 - 126 을 나타낸다. 이렇게 하여 모두 [ 1111 , 1111 ] 은 128 을 나타나게 된다. 이러한 방식을 바이어스 표현법이라 한다.

이렇게 하여 -9.6875 를 BitState 로 저장하게 된다면 부호부 : 1 지수부 : 1000,0010 ( 참고 : 1000,0000 부터가 1이다. ) 가수부 : 0011011000...0 으로 표현하여 저장하게 된다.

Bias

위에서 어째서 불필요한 바이어스 표현법을 사용할까 ? 라는 의구심이 생길수가 있다. Bias 와 같은 경우 순수한 0 과 INF 를 표현하기 위해 사용한다.

실상 우리가 아는 컴퓨터의 0 의 표현법은 모든 메모리의 bit 가 0 으로 채워져 있을 때를 0 이라 가정한다. 실수의 모든 bit 가 0이라 채워져 있을 때를 가정하여 2의 보수를 취해 계산을 하게 된다면 + 1.00000...0 * 2^0 = 1 이 되어버린다. 이처럼 모든 bit 를 0 으로 채워버리면 기본값이 1이 되어버리는 경우가 발생한다.

바이어스 표현법을 사용하여 표현하게 된다면 1.0000..0 2 ^ -127 이 되며 이것은 1 / 2^127 이라는 아주 작은 수를 표현하게 된다. 이 또한 0 이 아닌데 만일 이 값을 0으로 지정하게 된다하면 이보다 작은 양수를 표현할 수 없게 되어 버린다. 이때 특별한 규정을 두었는데 지수부가 모두 0으로 채워진 경우에 유효숫자의 정수부가 1 이 아닌 0이 되도록 하였으며 그에 맞추어 지수를 -127 이 아닌 -126 으로 고정하였다.

게임 내 캐릭터 또는 개체의 골격을 계층 구조화 시킨 시스템이다. 특정 모델을 애니메이션 하는데 사용되는 뼈의 배치와 이동을 정의 하는 에셋이다.

Skeletal Mesh

Skeleton Asset 을 메시에 바인딩한 Asset 으로 캐릭터나 오브젝트의 시각적 표현을 제공한다.

KeyFrameAnimation

특정 프레임에서 간격마다 Key 를 잡아 각 사이의 키에 대한 이동 회전 배율을 저장하고 키 사이의 Frame 을 보간하여 부드러운 전환을 생성하여 Animation 을 재생하는 기법

마지막으로 Game Math 글의 모든 Image 출저는 '이득우의 게임 수학' 임을 밝힙니다.

° Cartesian coordinate system

직선의 Number Set 을 수직으로 배치해 평면을 표기하는 방식

Cartesian coordinate system

Cartesian coordinate system 의 한 Element 는 순서쌍으로 표현하며 Coordinate 라 하며 ( x , y ) 로 표기한다.

Cartesian coordinate system | 데카르트 좌표계 Coordinate | 좌표

° Vector

두 개 이상의 실수를 Cartesian Product 로 묶어 형성된 Set 을 Axiom Set Theory 의 관점에서 규정한 것을 Vector Space 라 하며 이러한 Vector Space 의 Element 를 Vector 라 한다. 또한 Vector 의 Element 를 Scalar 라고 한다. 즉 x , y 가 Scalar 인 것 이다.

vector 표기법

vector space 의 8 가지 Axiom

° Norm

Vector 의 크기를 말한다. Norm 은 원점으로 부터의 최단 거리를 의미하는데 피타고라스 정리를 사용하여 거리를 측정한다.

피타고라스 정리와 이를 이용한 Norm 의 크기 측정 방법

° Unit Vector

크기가 1인 Vector 를 의미한다. 벡터의 크기를 측정하는 기준이 되며 Hat을 씌워 표시한다.

Normalize

특정 vector 를 Norm 으로 나눈다면 Unit Vector 를 얻을 수 있는데 이렇게 크기를 1인 Vector 를 만드는 연산을 Normalize 라 한다.

Unit Vector | 단위 벡터 Hat | (^) 모자 기호 Normalize | 정규화

특정 값에 따라 Animation 을 블렌딩시켜주는 기능이다.

그림과 같이 특정 축에 따라 애니메이션을 설정하고 Skeletal Mesh 의 Key Frame Animation 이 특정 키 사이의 보간을 이용하는 것이기 때문에 값의 위치에 따라 보간 비율이 달라지며 각축 애니메이션들이 서로 블렌딩되어 Animation 이 출력된다.

Unreal Documentation

Blend Space 에서 사용할 기준 값 같은 경우 위의 그림과 같이 게임 플레이의 코드 상등에서 값을 받아 가져온다.

1차원을 사용하였을 때 Blend Space 1D 를 사용할 수 있다.

Detail

Input Interpolation

애니메이션 속도 구동을 위한 축을 지정할 수 있는 기능이라고 하는데 정확히 어떠한 기능을 하고 있는 지는 모르겠으므로 추후 업데이트할 예정이다.

Axis Settings

• Name 에디터 그리드에 사용할 축 이름
• Minimun & Maximum Value 최소 최대 축값
• Number of Grid Divisions 그리드 분할 수로 Aninmation Data 에서 보간에 사용할 지점수
• Interpolation Time 보간 시간으로 지정한다면 해당 시간동안 보간을 유지하여 더 부드럽게 움직이는 효과를 줄 수 있음.
• Interfolation Type 보간에 대한 유형 지정.
  Sample Interpolation

  

• Target Weight Interpolation 초당 타깃 웨이트 보간 속도로 해당 보간 속도를 더 빨리 줄 수 있는 기능.
• Per Bone Blend 특정 본에 타깃 웨이트 보간을 설정하여 설정된 본마다 다른 속도로 블렌드 인 될 수 있는 기능.
  Animation Notifies

  

  Blend Space 에서 Notifie 의 실행 여부를 결정하는 기능 All Animations | 모든 노티파이 실행 Heigest Weighted Animation | 특정 가중치가 가장 높은 Notifie 만을 실행 None | 실행 여부 없음

  Notifies | 특정 이벤트를 알리는 것인데 추후에 알아볼 예정
  Meta Data

  

  Metadata Animation Asset 할당 기능이다. Metadata 는 추후 자세히 정리할 예정이다.

  Thumbnail

  

  Content Browser 에서 미리 나오는 에셋의 미리보기 형식 ( ? ) 을 비춰주는 카메라의 각도를 변화할 수 있는 옵션 같다.

ACharacter Class 로 Blueprint 를 만들게 되며 해당과 같이 Component 들이 추가되어 있다. 이 장에서는 ACharacter 를 구성하는 Component 를 알아보도록 하자.

CapsuleComponent

Character 충돌체 영역을 담당하며 RootComponent 로 설정이 되어 있어 모든 USceneComponet 의 기준이 되는 Component 입니다.
CapsuleComponent 의 Detail Panel 살펴보도록 하자.

Shape

• Capsule Half Halt Height 캡슐의 절반 높이를 설정하며 높이는 Radius 보다 작을 수 없다.
• Capsule Radius 캡슐의 반지름을 설정한다.
• Shape Color 캡슐이 그려지는 색상을 설정한다.

Arrow Component

단순한 화살표가 Rendering 되는 Component 로 Character 가 바라보는 방향을 표시하는 Component 이다.

Skeletal Mesh Component

Character 의 Mesh 를 결정하는 Component 로 StaticMesh 가 아닌 Skeletal Mesh 를 설정한다. Skeletal Mesh 가 무엇인지에 대해서는 나중에 자세하게 다룰 예정이다.

Character Movement Component

Character 의 물리적인 움직임을 담당하는 Component 로 ACharacter 의 핵심 구성 요소이며 AActorComponent 의 파생클래스이다.
General Settings

일반 적인 설정 기능을 담당한다.

• Gravity Scale 중력이 곱해지는 정도를 설정한다.
• Max Acceleration 최대 가속도를 설정하며 속도의 변화율을 결정한다.

  
  

• Breaking Friction Factor
• Breaking Friction
• Use Separate Beraing Fiction 이 세가지는 제동 거리를 만들기 위한 마찰력과 관련된 기능같다. 나중에 추후에 업데이트 할 예정이다.

  
  

• Crouched Half Height 앉거나 웅크릴 시의 Capusle 의 절반 높이를 설정한다.
• Default Land Movement Mode 땅에 있을 시 기본 모드를 설정한다.
• Default Land Movement Mode 물에 있을 시 기본 모드를 설정한다.
  Walking

  

• Max Step Height Pawn 이 계단을 올라 갈 수 있는 높이를 설정합니다.
• Walkable Floor Angle 경사진 곳을 걸을 때 Pawn 이 최대로 걸을 수 있는 각도를 설정합니다.
• Walkable Floor Z 업데이트 예정
• Ground Friction 업데이트 예정
• Max Walk Speed 걸을 때 최대 속력입니다.
• Max Walk Speed Crouched 앉거나 웅크릴 시의 최대 속력입니다.
• Min Analog Walk Speed 아날로그 스틱을 최소로 기울일 때 붙을 가속도에 관하여 설정하는 기능
• Breaking Deceleration Walking 걷기 상태에서 가속을 적용하지 않을 시 일어나는 감속을 설정하는 기능
• Sweep While Nav Walking 보행 도중 Sweep Test 여부
• Can Walk Off Ledges 절벽을 넘어 설 수 있는지에 대한 여부 True 시 절벽을 걸어다니며 False 시 절벽이라면 밖으로 걸아나가지 못하도록 설정하는 기능
• Can Walk Off Ledges when Crouching 크런치 상태에서 절벽을 넘어 설 수 있는지에 대한 여부
• Maintain Horizontal Ground Velocity 경사로 지면에서 Movement 의 속력이 가로 지면을 기준으로 이동하므로 경사로가 높을 수록 그만큼 보정되어 빠르게 이동하게 만들어주는 기능
• Ignore Base Rotation True 라면 현재 캐릭터의 월드 회전을 계속 유지하고 False 라면 움직이는 Base 와 더불어 같이 회전한다.
  Jumping / Falling

  

• Jump Z Velocity 점프의 초기 속도로 점프할 때의 속력이다. 높으면 높을 수록 더 높이 점프한다.
• Air Control 공중에서 캐릭터의 움직임을 얼마나 제어 가능한지에 대해서 조절하는 기능이다.