본문 바로가기

문제 노트

 (157)
이진 트리( BOJ 31966 ) 문제 : https://www.acmicpc.net/problem/31966 문제 파악하기이진 트리의 모습이 순차적으로 주어질 때, 모든 말단 노드의 순서쌍 (a, b)에 대한 f(a, b) 값의 합인 S(T)를 구하는 문제입니다. f(a, b)는 말단노드 a에서 b까지 모두 덮는데 필요한 노드 최솟값을 의미하며, 문제를 해결하기 위해서는 트리의 왼쪽 서브트리와 오른쪽 서브트리를 입력받을 때마다 f(a, b)의 합을 모두 구해서 출력하면 됩니다. 다만, 트리의 입력이 서브트리의 형태로 주어지기 때문에 개수가 입력 값이 증가할수록 노드의 개수가 기하급수적으로 증가하게 됩니다. 따라서, 이 문제를 해결하기 위해서는 트리의 모습을 모두 구하는 것이 아닌, 미리 구해놓은 값을 활용하는 동적 프로그래밍 기법이 필..
두 배( BOJ 31963 ) 문제 : https://www.acmicpc.net/problem/31963 문제 파악하기 주어진 수열을 오름차순으로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 2배 하는 연산 1가지이며, 최대 250,000개의 숫자로 구성된 수열이 제시됩니다. 문제 자체는 이해하기 어렵지 않지만 은근 생각할 사항이 많은 문제입니다. 맨 왼쪽 부터 오른쪽 방향으로 숫자들을 하나씩 오름차순으로 맞추는 기본 베이스는 유추하기 쉽습니다. 다만, 여기서 어떻게 해야 시간 초과에 걸리지 않으면서 모든 숫자들을 바꿀 수 있을지는 생각을 필요로 합니다. 여기서 중요한 키워드는 기록하기 입니다. 문제 해결하기이 문제를 효율적으로 해결하기 위해서는 사용할 수 있는 유일한 연산인 2배 연산에 초점을..
개미( BOJ 2136 ) 문제 : https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 문제 파악하기 길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그..
유클리드 게임( BOJ 4342 ) 문제 : https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 문제 파악하기 주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하..
옥토끼는 통신교육을 풀어라( BOJ 17838 ) 문제 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 문제 파악하기 옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다. ..
게리멘더링( BOJ 28433 ) 문제 : https://www.acmicpc.net/problem/28433 28433번: 게리맨더링 길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과 www.acmicpc.net 문제 파악하기 합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요? 문제 해결하기 문제를 관찰..
하늘에서 떨어지는 1, 2, ... , R-L+1개의 별( BOJ 17353 ) 문제 : https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 문제 파악하기 주어진 N개의 수열을 대상으로 [ L, R ] 구간에 1, 2, ... , R-L+1의 값을 더하는 쿼리와 X 위치의 값을 구하는 쿼리를 수행하는 문제입니다. 수열의 범위가 최대 100,000개이며 쿼리의 수가 최대 100,000개이기 때문에 효율적인 자료구조가 필요합니다. 또한, 수행할 쿼리 역시 모든 구간에 동일한 값을 더하는 작업..
아이템 획득( BOJ 28216 ) 문제 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 문제 파악하기 자동차가 Q번 이동하면서 획득한 상자의 아이템 개수를 구하는 문제입니다. 자동차는 (1, 1) 위치에서 시작하며, 이동하면서 만나는 상자에서 항상 아이템을 얻을 수 있습니다. 상자와 이동하는 횟수 모두 최대 200,000번이기에 전탐색으로는 문제를 해결할 수 없습니다. 하지만 x와 y의 값이 최대 200,000이라는 범위 안이기 때문에 x와 y축을 기준으로 적절하게 상..

티스토리툴바