기록공간

동전 0 문제와 유형이 비슷한 문제이다. 그리디 알고리즘 문제이다. 입력 받은 가격을 1000엔과 빼서 나머지 거스름 돈 값을 구한다. 그리고 500엔부터 차례대로 거스름돈 보다 가치가 적거나 같은 경우 그 가치에 맞는 동전 개수를 구한 후 최종 값에 더해주고, 거스름돈에서 구한 만큼의 가치를 빼주면 된다. 이 작업을 동전 가치가 1엔이 될때까지 혹은 거스름돈이 0엔이 될때까지 반복해주면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int maxMoney = 1000; int coinArr[6] = { 500, 100, 50, 10, 5, 1 }; int change = 0; int changeCoinCount = 0; int price = 0..

우선, 로프들을 오름차순으로 정렬한 후, 그리디 알고리즘을 이용하여 풀면된다. O(n^2)를 사용하면 시간초과가 나므로 이점을 유의해서 풀어야한다. 정렬 후에 할일은 다음과 같다. 배열 가장 처음에 위치하는 가장 길이가 짧은 로프는 모든 로프의 길이보다 작거나 같으므로 개수는 배열의 크기와 같다. 분기를 타며 길이가 길어질수록 로프의 개수를 하나씩 줄여나가면서 들 수 있는 중량을 구해주면된다. 이전에 저장된 들 수 있는 중량보다 현재 계산한 중량이 더 크다면 그 값으로 덮어쓴다. 코드는 다음과 같다. #include #include using namespace std; bool cmp(int a, int b) { return a > inpu..

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 알고리즘이다. 하지만 그리디 알고리즘을 적용할 수 있는 예는 많지 않다. 코딩이 쉽고, 구현이 쉬운건 사실이지만, 그리디 알고리즘으로 구한게 항상 최적을 보장하는 경우는 거의 없기 때문이다. 만약에 사탕을 당장 받으면 1개만 받지만, 1분을 기다리면 2개를 받을 수 있다고 하자. 이런 경우 그리디 알고리즘을 사용하면 사탕을 1개 받는 것을 선택한다. 그래서 보통 '근사치 추정'을 위해 그리디 알고리즘을 사용한다. 적용 가능한 예 Prim Algorithm, Kruskal ..

회의 시간에 대한 문제는 그리디 알고리즘의 대표적인 문제라고 한다. 회의 시간이 끝나는 시간을 기준으로 정렬 한 후, 현재 기준에서 가능한 회의 가장 회의가 빨리 끝나는 것을 고르면 된다. 끝나는 시간이 같은 경우가 있을 수 있는데 (6, 8) (8, 8) 이러한 경우이다. 이런 경우를 고려하여 정렬을 해줘야 한다. 만약 끝나는 시간이 같다면 시작시간을 기준으로 정렬해주면 된다. 회의 시간 정렬이 끝나면, 맨 처음 시작 시간을 기준으로 차례대로 카운트 해나가면 원하는 값을 구할 수 있다. 코드는 다음과 같다. 벡터를 이용하여 회의 시간을 담아 정렬을 하였다. #include #include #include using namespace std; struct Time { int begin; int end; ..

동전의 가치가 가장 높은 것 부터 순차적으로 내려가면서 K보다 가치가 작았을때 그 가치만큼의 동전의 개수를 구해 (나눠주고) 최종값에 더해주고 나머지 값이 있으면 아직 동전을 충분히 채우지 못했으므로 반복해주면 된다. 4200원 동전의 가치 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 [1] 50000 -> 10000 -> ... -> 1000(알맞는값) 4200 / 1000 = 4개 4200 - (1000 * 4) = 200원 [2] 1000 -> 500 -> 100(알맞는값) 200 / 100 = 2개 200 - (200 * 2) = 0원(분기 종료) [최종] 4개 + 2개 = 6개 #include using namespace std; int main() {..

정렬을 할 줄 안다면 정말 쉬운 문제이다. 시간의 합이 최소가 되기 위해서는 각 사람이 돈을 인출하는데 필요한 시간을 오름차순으로 정렬하면 된다. 정렬 전 [3 1 4 3 2] 3 3 + 1 = 4 3 + 1 + 4 = 8 3 + 1 + 4 + 3 = 11 3 + 1 + 4 + 3 + 2 = 13 3 + 4 + 8 + 11 + 13 = 39 정렬 후 [1 2 3 3 4] 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 3 = 9 1 + 2 + 3 + 3 + 4 + 13 1 + 3 + 6 + 9 + 13 = 32 #include #include using namespace std; int main() { int personCount = 0; int* personTime = nullptr..

CPU 가상화 앞서 우리는 CPU의 가상화에 대해서 살펴보았다. 운영체제는 여러 개의 CPU가 존재한다는 환상을 제공하고 이는 프로세스 하나를 실행하고, 멈추고, 다른 프로세스를 실행하는 반복 과정인 시분할(Time Sharing)을 통해 이루어진다. 하지만 프로세스가 많아지면 CPU를 공유해야 할 대상도 많아지기 때문에 속도가 느려진다. 프로세스 앞에서 계속해서 프로세스라는 단어가 나왔는데, 도대체 무슨 뜻일까? 프로세스(Process)는 운영체제가 제공하는 핵심 개념 중 하나로 실행 중인 프로그램이다. 프로그램 자체는 생명이 없는 존재와 같다. 프로그램은 디스크 상에 존재하며 실행을 위한 명령어와 정적 데이터의 묶음일 뿐이다. 이것들을 읽고 실행하여 프로그램에 생명을 불어넣는 것이 운영체제이다. 프로..

DXGI(DirectX Graphics Infrastructure)는 Direct3D와 함께 쓰이는 API로 DirectX 그래픽 런타임에 독립적인 저수준(Low-Level)의 작업을 관리한다. 또한 DirectX 그래픽을 위한 기본적이고 공통적인 프레임워크를 제공한다. DXGI는 유연성을 위해 새로운 그래픽 라이브러리가 나오더라도 변하지 않을 수 있도록 구성되어 있다. 예를 들어 2차원 랜더링 API에도 3차원 렌더링 API처럼 스왑 체인과 페이지 전환이 필요하다. 이 때문에, 스왑 체인을 대표하는 인터페이스인 IDXGISwapChain은 실제로 DXGI API의 일부이다. DXGI는 그 밖에도 여러가지 공통적인 그래픽 기능성을 처리한다. 이를테면 화면 모드 전환, 디스플레이 어탭터나 모니터, 지원되는..