24.10.02 UE5, 알고리즘

UE5

언리얼 엔진의 기본타입

• bool
  • boolean 값(bool 크기 추정 금지). BOOL은 컴파일되지 않는다.
• TCHAR
  • character(TCHAR 크기 추정 금지)
• uint8
  • unsigned byte(1 바이트)
• int8
  • signed byte(1 바이트)
• uint16
  • unsigned “short”(2 바이트)
• int16
  • signed “short”(2 바이트)
• uint32
  • unsigned int(4 바이트)
• int32
  • signed int(4 바이트)
• uint64
  • unsigned “quad word”(8 바이트)
• int64
  • signed “quad word”(8 바이트)
• float
  • single precision floating point(4 바이트)
• double
  • double precision floating point(8 바이트)
• PTRINT
  • 포인터를 가질 수 있는 integer(PTRINT 크기 추정 금지)
• C++의 int와 unsigned int 유형은 플랫폼에 따라 크기가 변할 수 있지만 너비가 적어도 32비트임이 보장되므로 정수 너비가 중요치 않은 경우라면 코드에서 사용해도 괜찮다.
• 명시적으로 크기가 정해진 유형은 여전히 시리얼라이즈 또는 리플리케이트된 포맷으로 사용해야 한다.

알고리즘

기본 정렬 알고리즘

1. 선택 정렬(Selection Sort)

• 선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택정렬과 최대 선택 정렬로 구분 할 수 있다.
• 최소 선택 정렬은 오름차순으로, 최대 선택 정렬은 내림차순으로 정렬된다.
• 기본 로직
  1. 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
  2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
  3. 다음 인덱스에서 위 과정을 반복한다.
• 이 정렬 알고리즘은 n-1개, n-2개 … , 1개씩 비교를 반복한다.
• 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.
• 공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
• C++ 코드
• void SelectSort(vector<int> v) { for(int i = 0; i<v.size()-1; ++i) { int tmp = i; for(int j = i+1; j<v.size(); ++j) { if(v[tmp] >= v[j]) { tmp = j; } } } }

2. 삽입 정렬(Insertion Sort)

• 삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.
• 기본 로직
  1. 삽입 정렬은 두 번째 인덱스에서 부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
  2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
  3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.
  4. 만약 삽입 변수가 더 크면, 비교 인덱스 +1 에 삽입변수를 저장한다.
• 이 정렬 알고리즘 또한 최악의 경우 시간복잡도는 O(n^2)이지만, 이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않아 시간 복잡도는 O(n)이다.
• 공간 복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
• C++ 코드
• void InsertionSort(vector<int> v) { for(int i = 1; i<v.size(); ++i) { int key = v[i]; int j = i-1 while(j>=0 && key<v[j]) { swap(v[j], v[j+1]); --j; } v[j+1] = key; } }

3. 버블 정렬(Bubble Sort)

• 버블 정렬은 매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다.
• 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.
• 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해 주면 된다.
• 기본 로직
  1. 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
  2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
  3. 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열 값을 비교한다.
  4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼 반복한다.
• 선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.
• 공간복잡도는 O(n)이다.
• C++ 코드
• void bubbleSort(vector<int> v) { for(int i = 0; i<v.size()-1; ++i) { for(int j = 1; j<v.size()-i; ++j) { if(v[j-1]>v[j]) { swap(v[j-1], v[j]); } } } }

---

참조

https://hsp1116.tistory.com/33

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1