기록공간

깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것이다. 이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없는 경우 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색한다. 그림을 통해 한번 살펴보자. 위 그림의 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정하자. 우선, 정점 1에서 깊이 우선 탐색을 한다고 하자. 먼저, 정점 1에서 연결된 간선들을 통해 연결된 정점을 확인하면 2, 3..

동전 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)는 운영체제가 제공하는 핵심 개념 중 하나로 실행 중인 프로그램이다. 프로그램 자체는 생명이 없는 존재와 같다. 프로그램은 디스크 상에 존재하며 실행을 위한 명령어와 정적 데이터의 묶음일 뿐이다. 이것들을 읽고 실행하여 프로그램에 생명을 불어넣는 것이 운영체제이다. 프로..