mojo's Blog

문제 링크 => 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 끝지점까지 문제에서 주어진 조건에 맞게 이동할 수 있는 경우 최소로 점프한 횟수를 반환하고 이동할 수 없는 경우 -1 를 반환한다. i 번째에 점프할 수 있는 횟수를 A[i] 라고 할 때, 0 A[i]; cout

문제 링크 => 5904번: Moo 게임 (acmicpc.net) 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 재귀를 이용한 분할 정복문제이다. 이 문제는 다음과 같이 Moo 수열을 만들 수 있다. S(0) = moo S(1) = moo mooo moo S(2) = moo mooo moo moooo moo mooo moo ... S(k) = S(k - 1) moo ... o S(k - 1) (o의 개수는 (k + 2) 개) 이런식으로 Moo 수열을 구할 수 있다. 근데 ..

Scheduling Metrics 시작에 앞서 4가지 가정이 있다고 하자. 1. Each job runs for the same amount of time. ex) process p1, p2, p3, p4 가 동일하게 10초씩 돈다고 가정 2. All jobs arrive at the same time. ex ) CPU 입장에서 동시에 실행해서 도착한 상황이라고 가정 3. All jobs only use the CPU (they perform no I/O) 4. The run-time of each job is known. Performance metric : Turnaround time => The time at which the job completes minus the time at which th..

문제 링크 => 2737번: 연속 합 (acmicpc.net) 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 알고리즘이 수학으로 분류되었지만 binary search 를 이용하여 해결했다. 문제는 굉장히 간단하다. 숫자 N 에 대하여 2개 이상의 연속하는 수의 합이 나올 수 있는 모든 경우의 수를 구하는 문제이다. 간단하게 생각해본다. 임의의 수 (x > 0) 에 대하여 다음과 같은 작업을 계속 해준다. (1) 연속하는 수 2개 ) x + (x + 1) = N 를 만족하는 x 가 있으면 경우의 수를 counting 한다. (2) 연속하는 수 3개 ) x..

문제 링크 => Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces codeforces.com 어제 밤에 ICPC 학회분들과 virtual 을 돌려서 푼 문제인데 뇌절을 계속해서 풀지 못한 문제이다. 이러한 용의 머리의 길이 x 가 주어질 때 n 개의 Query가 주어진다. Query 는 머리의 길이를 d 만큼 잘라낼 수 있는 d 값과 자른 후에 h 만큼 다시 생겨나는 h 값이 주어진다. 이 때 용의 머리를 완전하게 잘라낼 수 있는 경우 최소로 자른 횟수를 출력하고 그렇지 못한 경우 -1..

문제 링크 => 코딩테스트 연습 - 구명보트 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 이 문제에서 핵심은 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다. 그리고 구명 보트는 무게 제한이 있다. 예를 들어서 x kg, y kg 의 합 (x + y) kg 에 대하여 (x + y) limit 인 경우 => 1를 counting 하고 back 에 존재하는 값만 pop (가장 작은 값은 pop 하지 않음) 4. 1번으로 돌..