전체 글

문제 풀이 구현, 시뮬레이션, 너비 우선 탐색, 그래프 탐색 문제이다. 터질 뿌요들을 탐색할 때, BFS를 이용한다. 상하좌우로 같은 색상의 뿌요들을 탐색했을 때, BFS 탐색의 횟수가 4이상이라면 터질 뿌요들이다. 이 것을 queue explode의 형태로 저장한다. explode 큐를 꺼내면서 뿌요를 터트린다. 터진 뿌요에 해당하는 필드는 '.'으로 값이 변한다. 밑에 빈 공간이 있는 뿌요들은 아래로 떨어져야 한다. 아랫줄부터 검사하면서 현재 검사하는 타일의 값이 '.'일 경우, 해당 타일 바로 위에 있는 뿌요 타일과 값을 바꾼다. 다시 explode 큐를 채우기 위해 BFS로 터질 뿌요들을 탐색하고, explode가 모두 비워질 때까지 반복한다. 코드 #include #include #include..

40: 다중 상속은 심사숙고해서 사용하자 다중 상속(multiple inheritance: MI)하면 바로 머리에 들어와야 하는 사실 중 하나는, 둘 이상의 기본 클래스로부터 똑같은 이름(이를테면 함수, typedef 등)을 물려받을 가능성이 생겨 버린다. 모호성이 생긴다는 것이다. class BorrowableItem { public: void checkOut(); }; class ElectronicGadget { private: bool checkOut() const; }; class MP3Player : public BorrowableItem, public ElectronicGadget {}; MP3Player mp; mp.checkOut(); // 모호성 발생! 위의 checkOut 함수는 C++..

문제 풀이 구현, 시뮬레이션 문제이다. 파이어볼을 표현할 구조체를 하나 만든다. (fireball) 문제의 방을 vector room[51][51]의 형태로 만들어서 (x, y)의 방의 파이어볼의 데이터를 알 수 있도록 하였다. 각각의 방을 조사하며 파이어볼을 이동시킨다. 이동 시, 속도가 방의 크기보다 클 수 있기 때문에 mod연산을 사용하며 범위를 초과했다면 범위에 맞게 조절해준다. 이동 후의 방에 파이어볼이 합쳐졌다면, (x, y)에서의 vector를 이용해서 합친다. 코드 #include #include using namespace std; typedef struct { int mass; int speed; int direction; }fireball; // 이동 방향 8가지 int dx[8] =..

4.4 시간 측정과 애니메이션 애니메이션을 정확히 수행하려면 시간을 측정해야 한다. 애니메이션의 인접한 두 프레임 사이에 흐른 시간의 양을 측정할 수 있어야 한다. 4.4.1 성능 타이머 정밀한 시간 측정을 위해, Windows가 제공하는 성능 타이머를 사용한다. 성능 타이머의 시간 측정 단위는 '지나간 클럭 틱 들의 개수'이다. 성능 타이머로부터 틱 수 단위의 현재 시간을 얻을 때에는 다음과 같이 QueryPerformanceCounter 함수를 사용한다. __int64 currTime; QueryPerformanceCounter((LARGE_INTEGER*)&currTime); 초 단위 시간을 얻으려면, 우선 QueryPerformanceFrequency 함수를 이용해서 성능 타이머의 주파수(초당 틱..

39: private 상속은 심사숙고해서 구사하자 class Person {}; class Student : private Person {}; void eat(const Person& p); Person p; Student s; eat(p); eat(s); // 에러! Student는 Person의 일종이 아니다. Person의 파생 클래스 Student를 public이 아닌 private으로 상속하였다. private 상속은 분명이 is-a를 뜻하지 않는다. 우선 private 상속을 쓰면 어떻게 되는지 알아보자. 클래스 사이의 상속 관계가 private이면 컴파일러는 일반적으로 파생 클래스 객체를 기본 클래스 객체로 변환하지 않는다. 그리고 기본 클래스로부터 물려받은 멤버는 파생 클래스에서 모조리 p..

문제 풀이 누적 합과 이분 탐색을 사용한다. 피자 조각의 최대 개수는 1000개 이므로 O(N * N)으로 해도 시간초과가 발생하지 않는다. A와 B에서 얻을 수 있는 모든 피자 조각을 계산한다. 피자 조각은 끝과 처음이 연결될 수 있으므로 유의해서 더해야 한다. A에서 얻을 수 있는 피자 조각을 기준으로 P와의 차이만큼의 B의 피자 조각의 수를 이분 탐색으로 구한다. 코드 #include #include #include using namespace std; vector A; vector A_parts; vector B; vector B_parts; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int P; int m,..

4.3 Direct3D의 초기화 Direct3D 초기화 과정은 길지만, 응용 프로그램 실행 시 한 번만 해주면 된다. 책에서 말하는 초기화 과정은 다음과 같다. D3D12CreateDevice 함수를 이용해서 ID3D12Device를 생성한다. ID3D12Fence 객체를 생성하고 서술자들의 크기를 얻는다. 4X MSAA* 품질 수준 지원 여부를 점검한다. 명령 대기열과 명령 목록 할당자, 그리고 주 명령 목록을 생성한다. 교환 사슬을 서술하고 생성한다. 응용 프로그램에 필요한 서술자 힙들을 생성한다. 후면 버퍼의 크기를 설정하고, 후면 버퍼에 대한 렌더 대상 뷰를 생성한다. 깊이 스텐실 버퍼를 생성하고, 그와 연관된 깊이 스텐실 뷰를 생성한다. 뷰포트와 가위 판정용 사각형들을 설정한다.

CPU와 GPU는 병렬로 작동하지만, 종종 동기화가 필요하다. 동기화는 한 처리 장치가 작업을 마칠 때 까지 다른 처리 장치가 놀고 있어야 함을 의미하며, 성능에 바람직 하지 않다. 동기화는 병렬성을 망친다. 4.2.1 명령 대기열과 명령 목록 GPU에는 명령 대기열 (command queue)가 있다. CPU는 그리기 명령들이 담긴 명령 목록(command list)을 Direct3D API를 통해서 그 대기열을 제출한다. 하지만 그 명령들을 즉시 GPU가 실행하는 것은 아니다. 처리할 준비가 되어야 비로소 실행되기 시작한다. 즉, 명령들은 대기열에 남아 있는다. 명령 대기열이 비면 GPU는 할 일이 없어 놀게 된다. 반대로 대기열이 꽉 차면, 대기열에 자리가 생길 때까지 CPU가 논다. 고성능 응용 ..

38: "has-a(...는...를 가짐)" 혹은 "is-implemented-in-terms-of(...는...를 써서 구현됨)"를 모형화할 때는 객체 합성을 사용하자 합성(composition)이란, 어떤 타입의 객체들이 그와 다른 타입의 객체들을 포함하고 있을 경우에 성립하는 그 타입들 사이의 관계를 일컫는다. 포함된 객체들을 모아서 이들을 포함한 다른 객체를 합성한다는 뜻인데, 이를 테면 다음과 같은 경우다. class Address{}; class PhoneNumber{}; class Person { public: private: std::string name; // 이 클래스를 이루는 객체들 Address address; PhoneNumber voiceNumber; PhoneNumber fax..

문제 풀이 이분 탐색을 사용한다. 모두 탑승하는데 소모되는 최소 시간을 이분 탐색한다. 최소 시간은 0, 최대 시간은 (N X 최장 운행 시간)으로 설정했다. mid값을 이용해서 해당 시간 동안 몇 명이 탑승할 수 있는 확인한다. 여기서 주의할 점이 0초 때, 이미 기구에 탑승하고 있기 때문에 현재 탑승한 아이의 수를 미리 N으로 세팅해줘야 한다. 이분 탐색으로 얻은 최소시간은, 마지막 아이가 놀이기구에 탑승한 시점의 시간이다. (최소시간 - 1)분 때, 총 몇 명이 탈 수 있는지 확인한다. (최소시간 % 탑승시간 == 0)이라면 해당 놀이기구에는 최소시간 시점에 탑승할 수 있는 놀이기구이다. 인덱스가 작은 순으로 해당 검사를 하면서 총 탑승한 아이의 수가 N과 같을 때의 인덱스를 출력한다. 코드 #in..