본문 바로가기

문제 노트/정올

 (49)
이진 트리( 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 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축을 기준으로 적절하게 상..
주유소( BOJ 28219 ) 문제 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇 www.acmicpc.net 문제 파악하기 N개의 마을에 필요한 주유소의 최소 개수를 구하는 문제입니다. N개의 마을은 (N-1)개의 도로로 연결되어 있으며, 길이가 K인 두 마을 사이의 경로에는 꼭 1개 이상의 주유소가 있어야 합니다. 문제 설명에서 (N-1)개의 도로로 연결되어 있으며, 모든 마을 사이의 경로는 유일하게 존재한다는 점을 통해 N개의 마을은 트리 형태로 연결되어 ..
레벨 업( BOJ 25405 ) 문제 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 문제 파악하기 N개의 캐릭터를 조건에 맞게 레벨업 시켰을 때의 결과를 출력하는 문제입니다. 캐릭터는 K개의 캐릭터를 동시에 1씩 레벨업 할 수 있으며, 총 M번 레벨업시킬 수 있습니다. N과 M의 범위에 따라 해결할 수 있는 방식과 난이도가 달라지는 문제로, 전체 문제를 해결하기 위해서는 레벨이 올라가는 특징을 적절하게 캐치해야 합니다. 문제 해결하기 그렇다면 문제를..
점( BOJ 2541 ) 문제 : https://www.acmicpc.net/problem/2541 2541번: 점 첫째 줄에는 처음에 S에 속하는 점 (a, b)의 좌표인 두 자연수 a와 b가 하나의 공백을 두고 순서대로 주어진다. 그리고 그 다음 다섯 줄에는 각 줄마다 한 개의 점 (p, q)의 두 자연수 p와 q가 하나의 www.acmicpc.net 문제 파악하기 시작점 (a, b)에서 3가지 규칙을 사용하여 집합 S에 점을 추가할 때, 주어진 (x, y)가 집합 S에 포함될 수 있는지 여부를 확인하는 문제입니다. 입력되는 점의 범위는 1 ~ 100,000이기 때문에 단순히 모든 경우의 수를 파악할 수는 없습니다. 대신 규칙을 계속 적용할 때 나타나는 특징을 살펴보면 문제를 해결할 수 있습니다. 문제 해결하기 규칙 3가지를..
트리와 쿼리( BOJ 25402 ) 문제 : https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 문제 파악하기 집합 S에 포함된 정점들이 몇 개씩 연결되었는지 판단하는 문제입니다. 문제에서 요구하는 연결 강도는 결국 연결된 정점 중 2개의 정점을 고를 수 있는 경우의 수를 의미하며, 만약 t개의 정점이 연결되어 있다면 연결 강도는 t*(t-1)/2 로 계산됩니다. 따라서, 문제를 해결하기 위해서는 몇 개의 정점들이 현재 연결되어 있는지 확인해야 합니다. 다만, 모든 경우를 ..
커다란 도시( BOJ 25380 ) 문제 : https://www.acmicpc.net/problem/25380 25380번: 커다란 도시 KOI시는 너무나 커다라서, 이동하려면 시간이 오래 걸린다. 그래서 KOI시는 도시를 관통하는 아주 긴 도로를 건설하였다. 도로는 남북 방향 또는 동서 방향으로 무한히 뻗어 나간다. 남북 방향의 www.acmicpc.net 문제 파악하기 K명의 경찰이 서로를 만나기 위해 필요한 이동거리의 합의 최솟값을 구하는 문제입니다. 경찰들은 주어진 길을 통해서만 움직일 수 있기에 모든 경로가 최단 경로(맨해튼 경로)가 아닐 수 있습니다. 그렇다고 한 명씩 확인하기에는 최대 200,000명의 경찰 사이의 경로를 확인해야 하기에 제한시간 이내에는 불가능합니다. 이렇게 복잡한 문제는 단계를 나눠서 생각하면 알고리즘을 ..

티스토리툴바