25.11.12일자 - TIL

수정을 통해 내용을 추가할 때는 재 저장을 습관화 하자.

코딩 테스트 3-3

다양한 정렬의 동작 방식을 이해하고/ 성능(시간 복잡도)을 비교 분석할 수 있다.
사용자가 정의한 순서대로 데이터를 나열하는 것을 의미한다. -오름차순/내림차순 둘 다 가능하고 임의로 정한 조건이 될 수도 있다.
좌표 정렬이 흔히 나온다.(2차원 값을 X우선 정렬하고 Y오름차순 정렬하라 등)
원하는 값을 빨리 찾을 수 있기 때문.
정렬이 전제 조건인 알고리즘이 존재하기 때문.


삽입 정렬
앞 또는 뒤의 값을 비교해서 순서를 바꾸는 식으로 완성하는 정렬 방법.
의사 코드
 for j=2 tp A.length
  key = A[j]
  // A[j]를 정렬된 부분 배열 A(1, , , j-1)에 삽입한다.
  i = j-1
  while i>0 and A[i] > key
    A[i+1] = A[i]
    i=i+1
  A[i+1] = key


시간 복잡도는 O(N^2)이다. 이는 오름차순을 내림차순으로 바꿀 때 가장 큰 값을 가지고 이미 정렬에 가까운 상태라면 O(N)이 소요될 수 있다.(갭이 크다)

// 최악의 경우: 삽입 정렬의 시간 복잡도를 확인하기 위한 역순 배열 정렬
#include <iostream>
using namespace std;

int main() {
    int arr[] = {9, 7, 5, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int count = 0; // 비교 횟수 측정

    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            count++; // 비교 발생
            arr[j + 1] = arr[j];
            j--;
        }
        if (j >= 0) count++; // 마지막 비교 실패도 포함
        arr[j + 1] = key;
    }

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "\n비교 횟수: " << count << endl;

    // 출력결과
    // 1 3 5 7 9
    // 비교 횟수: 10
}



병합 정렬
divide&conquer
최소 단위로 나눈 후 합치면서 재 정렬을 시행하는 방법.

의사코드
 MERGE_SORT(A, p, r)
if  p < r
  q = (p + r) / 2
  MERGE_SORT(A, p, q)
  MERGE_SORT(A, q,+1, r)
  MERGE(A, p, q, r) // 이미 정렬된 A[p, , ,q]와 A[q+1, , ,r]을 병합해서 하나의 배열로 만듬

세부 동작
분할 2. 정복 3. 결합
#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int size = right - left + 1; // 임시 배열의 크기
    int* temp = new int[size];   // C-style 동적 배열 할당

    int i = left;    // 첫 번째 부분 배열(arr[left...mid])의 시작 인덱스
    int j = mid + 1; // 두 번째 부분 배열(arr[mid+1...right])의 시작 인덱스
    int k = 0;       // 임시 배열(temp)의 시작 인덱스

    // 두 부분 배열을 비교하며 임시 배열에 정렬하여 저장
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 첫 번째 부분 배열에 남은 요소가 있다면 임시 배열에 복사
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 두 번째 부분 배열에 남은 요소가 있다면 임시 배열에 복사
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 임시 배열(temp)에 정렬된 요소들을 원래 배열(arr)의 해당 위치에 복사
    for (int idx = 0; idx < size; ++idx) {
        arr[left + idx] = temp[idx];
    }

    delete[] temp;
}

// mergeSort 함수는 변경할 필요 없음
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // (left + right) / 2 는 큰 값에서 오버플로우를 일으킬 수 있음
        int mid = left + (right - left) / 2;

        // 왼쪽 부분 배열 정렬
        mergeSort(arr, left, mid);
        // 오른쪽 부분 배열 정렬
        mergeSort(arr, mid + 1, right);

        // 정렬된 두 부분 배열 병합
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {9, 3, 1, 5, 13, 12};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "원본 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // 출력 결과
    // 원본 배열: 9 3 1 5 13 12
    // 정렬된 배열: 1 3 5 9 12 13

    return 0;
}


계수 정렬
데이터 값 자체를 인덱스로 사용하는 데이터에 의존적인 정렬 방식.
각 값의 빈도 수를 세어 그 정보를 기반으로 정렬을 수행한다.

의사 코드
//A는 입력 배열이고, k는 입력 배열의 최대값
COUNTING-SORT(A, k)
   count <- 크기가  k+1인 0으로 채워진 배열
   output <- 입력배열과 같은 크기의 배열
   for i = 0 to A.length - 1
    count[A[i]] <- count[A[i]] + 1
   idx <- 0
   for i = 0 to k-1
     while (count[i]--) {
             arr[idx++] = i;
      }

빈도 수를 얻고 이를 이용해서 내용을 빈도수에 따라 역으로 산출해 내는 방법.

세부 동작
카운트 배열 생성
 입력 배열의 최대값k를 기준으로 크기가 (k+1)인 count배열을 생성하고 모든 원소를 0으로 초기화 한다.
빈도수 계산
 입력 배열을 순회하면서, 각 원소의 값을 인덱스로 사용하여 배열의 해당 위치에 해당 값의 빈도수를 누적한다.

시간 복잡도
N은 입력 배열의 크기이고 K는 입력 배열의 최대 값 이라고 한다면
count배열을 초기화 하는데 O(K)
빈도수를 세는데 O(N)
정렬된 배열을 생성하는데 O(N)
따라서 시간 복잡도는 O(N+K)가 된다.

계수 정렬의 한계
음수 값이 존재하는 경우 해당 값을 인덱스로 사용할 수 없기 때문에 사용할 수 없다.
원소 값의 범위가 넓거나 듬성등성 있는 경우 - 중간 값을 모두 포함하는 큰 크기의 배열을 생성해야 하므로 비효율적이다.


힙 정렬
힙 이라는 자료구조를 사용한 정렬 방법

조건을 만족하는 이진 트리이다.
보통 최대합과 최소합으로 구분된다.

최대힙 구축하기 - max_heapify() 정의   build_heap
특정 원소를 기준으로 최대 힙의 성질을 만족하도록 재구성하는 함수 max_heapify(int idx)
조건을 만족하지 못하면 부모 노드와 값을 바꾸고 재귀하여 다시 시행한다.

// 최대 힙(Max Heap)을 이용하여 정수 배열을 오름차순 정렬하는 힙 정렬 예제
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;         // 루트를 가장 큰 값으로 시작
    int left = 2 * i + 1;    // 왼쪽 자식
    int right = 2 * i + 2;   // 오른쪽 자식

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 재귀적으로 하위 트리 정리
    }
}

void heapSort(int arr[], int n) {
    // 배열을 힙 구조로 만들기 (Build Heap)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 힙에서 하나씩 요소를 추출
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);        // 루트와 마지막 요소 교환
        heapify(arr, i, 0);          // 줄어든 힙에 대해 다시 heapify
    }
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // 출력결과
    // 1 3 4 5 10
}

힙 구축은 N 부터 해도 동작은 하나 N/2부터 시작하는 것이 좋다.(자식 노드의 왼쪽은 2*N 오른쪽은 2*N+1이기 때문)
힙 정렬의 최종 목적은 배열을 오름차순 또는 내림차순으로 정렬하는 것.
루트 노드(가장 큰 값을 가지는 노드)

시간 복잡도
힙은 높이가 최대 log N 인 이진 트리가 되고 재구성하는데 O(log N)의 시간이 걸리므로 시간 복잡도는 O(N logN)이므로
삽입 또는 삭제 연산의 시간 복잡도는 O(log N)이 들어간다.

우선순위 표를 사용할 때 주로 사용된다.

// 최대 힙(Max Heap)을 이용하여 정수 배열을 오름차순 정렬하는 힙 정렬 예제
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;         // 루트를 가장 큰 값으로 시작
    int left = 2 * i + 1;    // 왼쪽 자식
    int right = 2 * i + 2;   // 오른쪽 자식

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 재귀적으로 하위 트리 정리
    }
}

void heapSort(int arr[], int n) {
    // 배열을 힙 구조로 만들기 (Build Heap)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 힙에서 하나씩 요소를 추출
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);        // 루트와 마지막 요소 교환
        heapify(arr, i, 0);          // 줄어든 힙에 대해 다시 heapify
    }
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // 출력결과
    // 1 3 4 5 10
}

1~10,000 일때 O(N^2)인 함수를 사용하면 실패다.  만약 1~10,000,000 일 경우에는 O(log N)을 사용해도 실패한다.
'와 "의 의미

STL - sort

string - 문자열

==============================
언리얼 2-3
숙제는 실습 복기에서 확인!
숙제에 대한 해설은 13:33까지

콜리전(collision) 충돌,부딪침
엔진 내부에서 콜리전을 어떻게 관리하는지 실습으로 콜리전 채널과 프리셋을 바꿔가며 이벤트를 발생시켜보는 방법, 스태틱 메시의 기본 콜리전 형태 편집, 캐릭터 콜리전의 주의사항 까지 알아본다.

콜리전 채널
오브젝트 채널(Object Channels)과 트레이스 채널(Trace Channels)을 기반으로 동작한다.
각 채널은 오버렙(Overlap), 블록(Block), 무시(Ignore)중 하나로 설정돼, 서로 마주쳤을 때 어떻게 반응할지를 결정한다.
편집- 프로젝트 편집 -엔진- 콜리전 이 있다.

제공되는 콜리전 채널을 이용해본다.
디테일 - 스테틱 매쉬-피직스 에서 간단하게 이용할 수 있다.
콜리전이 없으면 충돌 상호작용이 안된다.
콜리전 - 자동 컨벡스 콜리전

=============================================
언리얼 실습 1-9 + (1-8 다시 만들기)

카메라가 스프링 암에 상속 되어있으나 스프링 암의 카메라 세팅에서 폰 제어 회전 사용을 체크 하였을 때 스프링 암의 회전 값이 0으로 고정되는 현상이 있었고 이를 바로 하단의 피치 상속을 해제함으로써 해결되었다.(튜터님과 해결한 부분)

원래 세팅했던 각도와 카메라의 위치

스프링의 회전값이 초기화되어(변경을 해도 적용되지 않음) 수평으로 이동된 모습

이동 애니메이션을 추가하기위해 Bland Space 셋팅, 캐릭터에 적용되게 하기 위한 블루프린트를 셋팅하고 적용되는모습.