분류 전체보기

[실4] 2003 - 수들의 합2

#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m, s = 0, e = 0; cin >> n >> m; int* arr = new int[n]; for (int i = 0; i > arr[i]; int sum = 0, res = 0; while (e m) sum -= arr[s++]; else { res++; sum += arr[e++]; } } cout

투 포인터 알고리즘(Two Pointers Algorithm)

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘이다. 절대 답이 되지 않는 경우는 계산하지 않아 시간을 단축시켜준다. Q. 배열에서 부분 배열의 합이 M이 되는 경우의 수를 구하여라! A1. 가장 쉽고 단순한 방법으로는 이중 for문을 이용해서 모든 경우의 수를 구할 수 있다. 시간 복잡도 O(N^2) A2. 투 포인터 알고리즘을 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 주로 적용되는 문제 유형 - 연속된 수들의 합 - 부분 배열의 합 풀이 방법 1. 포인터 2개가 같은 방향으로 진행해 나아가는 것 2. 포인터 2개가 양끝에서 반대로 진행하는 것 대표 문제 풀이 1 - 백준 [2003] 수들의 합 2 www.acm..

C++ 프림(Prim) 알고리즘으로 MST 찾기

1. 프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘이다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것이다. 하늘색으로 표시한 경로가 최소신장트리이다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적이다. 2. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요하다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한다. (보통 Min Heap을 이용해서 구현한다.) 가장 먼저, 그래프에서 아무 노드나 선택하므로 가장 번호가 ..

[골4] 1197 - 최소 스패닝 트리

#include #include #include using namespace std; class Edge { public: int node[2]; int dist; Edge(int a, int b, int dist) { node[0] = a; node[1] = b; this->dist = dist; } bool operator> vertex >> edge; for (int i = 0; i > from >> to >> cost; v.push_back(Edge(from, to, cost)); } sort(v.begin(), v.end..

[Unity] 그래픽스 최적화 - 드로우콜과 배칭

01. Draw Call 드로우콜은 수많은 병목 중 하나의 원인일 뿐,, 반드시 병목이 드로우콜에서 일어난다고 단정지어서는 안됨. 드로우콜이 강조되는 이유는 대부분 병목의 원인이 드로우콜에 있기 때문. 드로우 콜이란? CPU가 GPU에게 이거 그려! 하고 명령을 호출하는 것. 더 자세하게 ? 한 프레임의 렌더링은 매 오브젝트를 순차적으로 그려주면서 오브젝트를 다 그리면 화면에 보여지게 되는 것. 오브젝트를 화면에 렌더링하기 전에 우선 해당 오브젝트가 렌더링 대상에 포함되는지 체크한다. 현재 프레임 상에서 해당 오브젝트가 카메라의 시야 밖에 있다면 안 그려도 되는 것이므로 렌더링 대상에서 제외한다. 이런 검사 과정을 Culling이라고 한다. 컬링을 거친 오브젝트가 렌더링되려면 CPU로부터 GPU에게 정보..

[Unity] 그래픽스 최적화 - 병목

01. 병목의 이해 성능 최적화란? 적은 자원을 사용하더라도 연산 효율이 높아지도록 최적의 성능을 이끌어 내는 것. 최적화를 위해 할 수 있는 노력들은... Mesh의 Vertex 줄이기 텍스처 크기 줄이기 가벼운 Shader 사용 Draw Call 줄이기 게임 로직 최적화 물리 연산 줄이기 등등이 있는데 그 전에 선행되어야 할 것이 병목을 탐지하는 것. Bottleneck, 병목 전체 프로세스가 갑자기 느려지거나 막혀서 정지하는 원인이나 그 장소. 병목현상이 발생했다 ! == 전체 성능이나 용량이 어떤 하나의 구성요소 때문에 제한 받는 일이 생겼다 ! 특정 로직 수행이 오래걸리면 그 친구 때문에 전체 성능이 떨어지게 되는 것. 따라서 최적화를 하려면 병목 현상이 누구 때문에 일어나는지 찾아야 함. 프로..

[Unity] 그래픽스 최적화 - 렌더링 파이프라인

01. GPU의 의미 그래픽 처리를 위한 시스템은 GPU를 중심으로 구성된 칩셋에서 이뤄짐. CPU가 렌더링 명령을 내리면 GPU가 수행. GPU 메모리, VRAM Video Random Access Memory. CPU가 메모리에서 데이터를 읽어오듯 GPU도 그래픽 카드에 GPU 메모리가 있다! 그것이 VRAM. 텍스처, 메시 데이터 등 렌더링에 필요한 데이터들, 렌더링 결과를 저장하는 버퍼들이 포함됨. 렌더링할 때 여기에 저장된 데이터를 참고해서 그래픽 처리. 02. 게임 루프 유저가 게임을 실행하면 로딩(초기화, 리소스 생성) -> 게임 중(매 프레임 렌더링) -> 게임 종료(리소스 해제) 위와 같은 일련의 과정이 게임 루프. 만약 10프레임이라면, 1초동안 10개의 장면, 한 장면당 0.1초를 쓰..

[Unreal] 스레드와 단일 스레드로 실행시키기 (-norenderthread)

언리얼은 두 개의 메인 스레드로 돌고 있는데, 하나는 우리가 아는 게임 스레드이고 나머지 하나는 한 틱 뒤에서 이 게임스레드를 뒤쫓고 있는 렌더 스레드이다. 게임 스레드가 월드의 변경점을 렌더 스레드에 반영시키기 위해서는 ENQUEUE_RENDER_THREAD라는 매크로를 통해 람다 함수로 이를 렌더 큐에 쌓아두는 방식으로 접근한다. void BeginInitResource(FRenderResource* Resource) { ENQUEUE_RENDER_COMMAND(InitCommand)( [Resource](FRHICommandListImmediate& RHICmdList) { Resource->InitResource(); }); } RenderResource.cpp에 정의되어있는 BeginInitRe..

[실1] 2468 - 안전 영역

#include using namespace std; using IntPair = pair; #define MAX 100+1 #define y first #define x second IntPair dir[] { {1, 0}, // 상 {-1, 0}, // 하 {0, -1}, // 좌 {0, 1} // 우 }; int board[MAX][MAX]; bool vis[MAX][MAX]; int n, ans; void Reset() { for (int i = 0; i n) continue; if (!vis[ny][nx] && board[ny][nx] > rain) DFS(ny, nx, rain); } } void Input() { ios_base::sync_with_stdio(false); cin.tie(NU..

[C++] STL 연관 컨테이너(associative container), set, multiset

set 세트set 컨테이너는 요소가 그 값에 따라 정렬되는 형태이다 즉, key라 불리는 원소(value)의 집합이다. 또한 이 원소들에 중복을 허용하지 않는다는 것이 특징이다.#include#includeusing namespace std;int main(){ set is; is.insert(55); is.insert(7); is.insert(23); is.insert(61); is.insert(7); is.insert(9); is.insert(58); set::iterator it; for(it = is.begin(); it != is.end(); it++) { cout 그냥 제멋대로 insert를 해도 알아서 정렬이 된다.​실제 트리구조는 항상 균형 이진 트리로 구성된다.이 ..