오늘 학습 키워드

• 언리얼 git 관리

• 힙(heap) 자료구조

• 배열 회전

1. 언리얼 git 관리

• 언리얼 프로젝트 역시 git으로 관리할 수 있다

• 대용량의 경우 LFS를 사용하기

1. 프로젝트가 있는 폴더에서 git init하여 초기화하기

2. 아래의 사진처럼 필수 폴더/파일만 냄기고 나머지 제거
   (Content/StarterContent)의 경우 용량이 아주 크므로 제거 추천
   

3. 이 폴더들만 git으로 관리

4. 다시 프로젝트파일들 복구하려면 프로젝트 우클릭 후 generate visual studio project files 클릭하여 다시 복구
   

2. 힙(heap) 자료구조

• 부모 노드가 자식노드보다 큰(작은) 이진 트리구조

관련 동작

1. 삽입동작

2. 제거동작

• 부모노드가 자식노드보다 크기(작기)만 하면 되므로, node의 순회 및 탐색, 출력 등의 동작들은 힙 구조에 필요가 없음

삽입동작

• 맨 마지막 노드에 추가한 후 아래에서 위로 부모 노드와 비교하며 heap 구조를 완성시킴
  

제거 동작

• 최대(최소)값인 root를 반환하며 제거

• 제거 해도 heap구조는 유지

• 이는 root의 key와 마지막 node의 key값을 바꾸고, 위에서 아래로 자식노드와 비교하며 heap 구조를 완성

구현

• complete or nearly complete한 이진트리구조이므로 배열로 구현 가능

• 편의상 배열의 0번은 비움

• root node의 index는 1번

• 왼쪽 자식의 index는 2i

• 오른쪽 자식의 index는 2i + 1

• 부모의 index는 i / 2
  

• 처음 heap을 만드는과정은, root만 존재하는 heap에 나머지 node들을 추가하는 것처럼 만들면 된다

사용처

• Priority queues

• Sorting

• Selection algorithms
  정렬되지 않은 배열에서 k번째로 큰(작은)값 찾기.
  전부를 정렬시키고 찾는것보다 효율적.
  힙 구조를 만들고, (k-1)번 root삭제했을 때의 root가 k번째로 큰(작은) 값

C++에서의 사용법

1. priority_queue

2. make_heap

priority_queue

• priority_queue내부적으로 힙으로 구현되어 있어, 이를 통해 사용 가능

• 사용이 매우 간편하고, push(), pop(), top() 같은 직관적인 메서드 제공

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 최대힙 (기본값)
    priority_queue<int> maxHeap;
    
    // 최소힙 (greater<int> 사용)
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    // 데이터 삽입
    maxHeap.push(5);	// 5
    maxHeap.push(2);	// 5 2 
    maxHeap.push(8);	// 5 2 8 -> 8 2 5
    maxHeap.push(1);	// 8 2 5 1
    // 힙 구조로 8 2 5 1 로 되어있음
    
    // 최대값부터 출력
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";  // 8 5 2 1
        maxHeap.pop();
    }
}

make_heap

• 기존 벡터를 힙으로 변환

• 벡터의 모든 원소에 직접 접근 가능하고, 힙 구조를 세밀하게 제어할 수 있음

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // 벡터를 최대힙으로 변환
    make_heap(v.begin(), v.end());	// 9 5 8 1 2 3
    
    // 새 원소 추가
    v.push_back(10);
    push_heap(v.begin(), v.end());	// 10 9 8 1 2 3 5
    
    // 최대값 제거
    pop_heap(v.begin(), v.end());
    cout << "최대값: " << v.back() << endl;  // 10
    v.pop_back();					// 9 5 8 1 2 3
}

priority_queue를 사용하는 경우:

• 단순히 우선순위 큐가 필요할 때
• 최대값/최소값만 필요하고 중간 원소는 볼 필요 없을 때
• 코드를 간결하게 작성하고 싶을 때

make_heap을 사용하는 경우:

• 힙의 모든 원소에 접근해야 할 때
• 기존 벡터를 힙으로 변환해야 할 때
• 힙 구조를 직접 조작하고 싶을 때
• 메모리나 성능 최적화가 중요할 때

3. 배열 회전

• 반시계 방향으로 90도 회전

• 기존 좌표가 (Y, X)이고 배열의 크기가 N이라면 회전 후에는 ((N - 1) - X, Y)

• 180, 270도는 위의 과정을 2,3 번 반복해주면 됨

다음 학습

• C++ 코딩테스트