컴공에서 살아남기

동적할당 컴파일 시에 메모리를 할당하는 정적할당과 달리, 런타임 중에 메모리를 할당하는 것을 말합니다. C++에서는 new 연산자를 사용하여 동적할당하고, 사용이 끝난 이후엔 반드시 메모리를 해제해 줘야 합니다. 그렇지 않을 경우 메모리 누수가 발생하여 성능 저하나 예기치 못한 오류가 발생할 수 있습니다. new/delete와 malloc/free 차이 new와 delete는 호출 시 생성자와 소멸자를 각각 호출합니다. 또한 new는 메모리를 할당할 때 자료형 단위로 할당합니다. malloc과 free는 호출 시 생성자와 소멸자를 호출하지 않습니다. 또한 malloc은 메모리를 할당할 때 바이트 단위로 할당합니다. 바인딩 프로그램 실행 시 변수나 함수들은 그 내용을 저장할 메모리를 할당해야 하는데, 그 ..

해시 테이블 해시테이블은 효율적으로 빠른 탐색을 하기 위한 자료구조로, key-value 쌍의 데이터를 입력받습니다. 해시 Function h에 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 키는 무조건 존재해야 하며, 중복되는 키가 있어서는 안됩니다. 해시 테이블을 구성하고 있는 key-value 데이터를 저장할 수 있는 공간을 slot 또는 bucket이라고 합니다. > 해싱함수 더보기 해싱 함수 h(k) 어떤 키 k에 대한 테이블 주소를 계산하기 위한 방법으로 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다. 해싱 함수 h를 이용하여 key-value를 index : h에 저장하는데, 이것을 "키 k..

스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자. ..

배열 (Array) Array는 연관된 데이터를 메모리상에 연속적이고 순차적으로 저장하며, 미리 할당된 크기만큼 저장되는 자료구조입니다. Array의 장점은 조회(lookup)와 추가(append)가 빠르다는 것입니다. 따라서 조회를 자주 해야하는 작업에서는 Array를 사용합니다. Array의 단점은 고정된 저장 공간을 사용한다는 특성 상, 선언 시에 배열의 크기를 미리 정해야 한다는 것입니다. 이로인해 메모리 낭비나 추가적인 오버헤드가 발생할 수 있습니다. 시간복잡도 접근(access), 추가(append), 마지막 원소 삭제(delete) : O(1) 삽입(insertion), 삭제(deletion), 검색(search) : O(n) 미리 예상한 것보다 더 많은 수의 데이터를 저장하느라 배열 크기를..

큐(queue) 큐는 선입선출의 자료구조로 인큐와 디큐의 시간복잡도가 O(1) 입니다. 주로 순서를 보장해주는 경우에 사용되며 큐를 통해 Cache, 프로세스 관리, 너비우선탐색 등을 구현할 수 있습니다. 이러한 큐는 배열이나 링크드 리스트로 구현할 수 있습니다. > Array-Base / List-Base 더보기 Array-Base 배열을 이용해 큐를 구현하면, 인큐와 디큐 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 원형 큐 형식으로 구현합니다. 또한 인큐가 계속 발생하면 고정된 배열 크기를 넘어가게 되어서 동적 배열과 같은 방법으로 배열의 size를 확장시켜야 합니다. 전반적으로 리스트를 이용하는 것보다 배열을 이요하는 것이 퍼포먼스가 더 좋지만, 최악의 케이스에는 r..

객체지향의 주요 특성은 캡슐화, 정보은닉, 상속성, 추상화, 다형성이 있습니다. (+ 코드의 재활용) 캡슐화 캡슐화는 클래스 안에 서로 연관있는 속성과 기능들을 하나의 캡슐로 만들어 묶는 것을 말합니다. 프로그램 구현에 필요한 자료와 함수를 묶어서 외부와 단절시키고, 그 묶음을 사용하는 데 필요한 인터페이스만 외부에 공개하는 것입니다. 캡슐화를 사용하면 속성과 기능들을 컴포넌트로 재사용하기 용이하고, 인터페이스가 단순해지며, 관련있는 컴포넌트 간에 응집도가 높아진다는 장점이 있습니다. 정보은닉 캡슐화를 하게 되면 자연스럽게 클래스의 내부 속성이나 메서드를 외부에 노출하지 않게 되어 정보가 은폐되는데 이것을 정보 은닉이라고 합니다. 정보 은닉은 프로그램이 데이터에 직접 접근하지 못하게 막아줄 뿐만 아니라,..

순서 렌더링 파이프라인은 IA(Input Assembly)인 "입력 조립" 단계부터 시작하여, 버텍스 쉐이더, 헐 쉐이더, 테셀레이션 쉐이더, 도메인 쉐이더, 지오메트리 쉐이더를 거치고, (스트림 출력 단계 SO) , 래스터라이저, 픽셀 쉐이더, Output Merge인 출력병합 단계로 마무리 됩니다. 단계별 간단한 설명 1. 입력 조립 - 입력 조립 단계는 GPU가 렌더링 할 데이터에 대한 정점 버퍼들을 CPU에게 받아서 기본 도형인 프리미티브 토폴로지를 설정하는 단계입니다. - 정점버퍼에는 위치, 노말, Color, UV 정보가 직렬화된 배열 형태로 담겨져있고, 이를 통해 조립된 프리미티브가 정점 쉐이더의 입력이 됩니다. 2. Vertex Shader (정점 쉐이더) - 버텍스 쉐이더 단계는 정점 데..

Draw Call(드로우 콜)이란? DP Call (Draw Primitive Call)? CPU가 GPU에게 오브젝트를 화면에 그리라고 명령하는 것을 말합니다. 드로우콜의 명령 과정 1. 데이터는 HDD나 SSD같은 데이터 저장 장치에 저장되고 CPU에도 CPU 메모리가 있고, GPU에도 GPU 메모리가 존재한다. (모바일에서는 물리적으로 나눠지지 않고 논리적으로 나눠 사용한다) 2. 어떠한 Mesh를 그리기 위해선 GPU 메모리에 Mesh 관련 정보가 있어야 하는데, 먼저 저장장치에 있는 데이터를 복사하여 CPU 메모리에 데이터를 올리게 된다. 3. GPU는 CPU 메모리에 접근할 수 없기 때문에 GPU 메모리에 CPU 메모리 데이터를 다시 복사하게 된다. 4. GPU는 그려야 하는 Mesh의 상태 ..

설명 인스턴싱이란 동일한 객체를 한 화면에 여러 개 렌더링 시킬 경우 한번의 DP Call로 처리하는 방식을 말합니다. 예를 들어 수많은 나무, 풀, 파티클 같은 객체들에 적용할 수 있습니다. 정의 동일한 객체(모델)을 한 화면에 여러 개 렌더할 때 batch 최적화를 통한 최적의 성능을 발휘할 수 있게 하는 기법 Batch란 모든 DrawIndexedPrimitive 함수를 콜 하는 것을 말합니다. 즉, HAL 함수를 최대한 적게 부르는 것이 Batch의 최적화라고 할 수 있습니다. 모델 정보를 담고 있는 하나의 정점 버퍼와 인스턴스 버퍼라는 각 복사본의 변경점들만 담은 두번째 버퍼를 사용하여 인스턴싱을 구현할 수 있고, 정점 버퍼는 그래픽 카드에 계속 캐싱되어 있고 인스턴스 버퍼의 내용대로 바뀌어 그..

오클루전 컬링 (Occulusion) 오클루전 컬링은 다른 오브젝트에 의해 숨겨진 오브젝트를 걸러내는 컬링 기법입니다. 카메라 앞에 위치하여 다른 오브젝트를 가리는 오브젝트를 오클루더(Occluder)라고 하고, 오클루더에 의해 가려지는 오브젝트들을 오클루디(Occludee)라고 합니다. (오클루더는 스태틱 오브젝트) 오클루전 컬링 시 주의할 점으론, 야외 씬 같이 다른 오브젝트에 가려지는 경우가 많지 않은 경우에는, 오브젝트를 가리며 얻는 이득보다, 오클루전 컬링 연산 비용이 더 클 수 있다는 점 입니다. (언리얼의 프로젝트 셋팅에서 렌더링에 들어가면 오클루전 컬링을 켜고 끌 수 있는 설정값이 있다.) 언리얼에서의 렌더링 컬링 언리얼에는 Distance, View Frustum, Precomputed ..

프러스텀 컬링, 절두체 컬링 (Frustum Culling) 절두체 컬링은 3차원의 월드 상에서 실제로 카메라의 시야 범위에 포함되는 것들만 렌더링하고, 나머지 것들은 렌더링 하지 않는 기법을 말하며, 3D 렌더링 기법 중 속도 증가 기법으로 중요하게 사용됩니다. 카메라 시야의 상,하,좌,우 방향으로 시야에 수직하는 평면과 먼곳의 시야 범위를 나타내는 평면까지 총 6개의 평면(절두체)을 통해 오브젝트가 절두체에 포함되는지를 평면 방정식으로 계산하여 구할 수 있습니다. 평면의 방향을 나타내는 법선 벡터 a, b, c 가 있을 때 평면과 원점의 거리를 나타내는 값 d가 존재하면 평면 방정식: ax + by + cz + d = 0 이러한 평면의 방정식을 만족하는 (x, y, z) 좌표값은 모두 평면 위에 있으..

벽 부수고 이동하기 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다...