mojo's Blog

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 이 문제에서 뇌절을 한 이유를 적어보려고 한다. 1. cell 을 채우는 과정에서 r, c가 달라지는 경우를 고려하지 못함 => 먼저 r을 채우고 c를 채우는 과정에서 cell을 채울 경우와 채우지 못할 영역을 표시해야 한다. cell을 채울 경우 r에서 cell을 채우지 못할 영역을 표시한 곳을 채운다면 이경우는 r, c가 달라지는 경우이다. 따라서 바로 0을 출력하면 끝이다. cell을 채우지 못할 영역을 표시할 경우 r에서 cell을 채운 곳이라면 이 또한 r, c가 달라지는 경우이다. 따라서 바로 0을 출력하면 끝이다. 2. 모든 cell 을 채웠을 때 r, c에 영..

이전에 배웠던거에 이어서... The Priority Boost Rule 5 : After some time period S, move all the jobs in the system to the topmost queue. Example ) A long-running job(A) with two short-running interactive job(B, C) 여기서 interactive job이란? => CPU를 짧게 사용하고 I/O를 하는 process를 의미함 왼쪽 예제를 보면 long job A를 실행하고 time slice를 초과하면서 Q0까지 이동하다가 short job B, C가 RR Scheduling 을 계속해서 하는 모습이다. (언제 끝날지 모름) 그렇다면 RR을 계속하는 과정에서 job..

문제 링크 => 15989번: 1, 2, 3 더하기 4 (acmicpc.net) 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 합을 나타낼 때 수를 1개 이상 사용한다는 것을 못봐서 약간의 뇌절을 했던 문제이다. 그럼 규칙성을 발견해보도록 한다. dp_1[x] => x = 1 + ( ) (( ) 안에 1, 2, 3 으로 구성)로 나타낼 때, ( ) 가 나타낼 수 있는 갯수 dp_23[x] => x = 2 + ( ) (..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com sorting 을 이용한 binary search 문제이다. 문제에 대해 간략하게 설명하자면 다음과 같다. 영웅들 n명과 드래곤 1명이 주어지며 힘, 수비력은 다음과 같이 주어진다. 영웅 => 드래곤에 맞서 싸울 영웅 1명과 드래곤의 공격을 받아쳐낼 (n - 1)명의 영웅들이 존재한다. 이때, 영웅의 각각 가지고 있는 힘을 ai 라고 한다. (1 해당 영웅을 한명 보내고 나머지 영웅들을 드래곤의 공격을 받아쳐내야 한다. 드래곤의 공격(y)이 나머지 영웅들의 힘(total)보다 클 경우 (y - total)만큼 힘을 키우면 된다. 반면에 같거나 작을경우 힘을 키우지 않아도 된..

Multi-Level Feedback Queue(MLFQ) A Scheduler that learns from the past to predict the future. 목표는 2가지이다. 1. Optimize turnaround time -> Run shorter jobs first 2. Minimize response time without a priority knowledge of job length. MLFQ has a number of distinct queues. - Each queues is assigned a different priority level. A job that is ready to run is on a single queue. - A job on a higher queue is..

문제 링크 => 15486번: 퇴사 2 (acmicpc.net) 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net Dynamic Programming 문제이다. 이 문제는 1일 2일 ... N일 접근을 해서 O(N) 만에 해결하도록 해야 한다. 문제에 주어진 Input을 기반으로 설명하고자 한다. 이때 dp[x] 는 x일 일때의 최대 이익을 의미한다. x T[x] P[x] dp[x] 1 3 10 0 2 5 20 0 3 1 10 0 4 1 20 0 5 2 15 0 6 4 40 0 7 ..