본문 바로가기

분류 전체보기

 (191)
문자열 장식( BOJ 1294 ) 문제 : https://www.acmicpc.net/problem/1294 1294번: 문자열 장식 첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다. www.acmicpc.net 문제 파악하기 N개의 문자를 적절하게 분해해서 사전순으로 가장 앞에 있는 하나의 문자를 만드는 문제입니다. 모든 문자의 순서를 맞춰야 하기 때문에 앞에서부터 하나씩 가져와야합니다. 문제를 처음 보면 사전순으로 가장 빠른 문자를 마냥 선택하면 될듯 하지만 aaa / aab 와 같이 동일한 문자가 반복될 때, 어떤 문자에서 a를 가져오는지에 따라 결괏값이 달라지기에 좀 더 세밀한 조건이 필요합니다. 문..
Escaping( BOJ 20041 ) 문제 : https://www.acmicpc.net/problem/20041 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 문제 파악하기 N명의 경찰이 1명의 도둑을 잡을 수 있는지 여부를 파악하는 문제입니다. 정답이 Yes / No로 나오는 대표적인 결정 문제라고 할 수 있습니다. 경찰과 도둑은 항상 상하좌우 인접한 격자 점으로 이동하며, 번갈아 가며 한 칸씩 움직일 수 있기 때문에 경찰이 먼저 도달하거나 도둑과 함께 동시에 도달하는 위치에서는 항상 경찰이 도둑을 잡을 수 ..
보석( BOJ 2492 ) 문제 : https://www.acmicpc.net/problem/2492 2492번: 보석 첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다(1 ≤ N, M ≤ 1,000,000). T는 금강석의 개수를 나타내고, K는 정사각형의 크 www.acmicpc.net 문제 파악하기 가장 많은 금광석을 포함하고 있는 K*K 크기의 정사각형 위치를 구하는 문제입니다. 지도의 크기인 N과 M의 범위는 크지만 묻혀있는 금광석의 개수는 최대 100개이기 때문에 탐색할 범위만 잘 설정하면 충분히 완전탐색으로도 해결할 수 있습니다. 그럼 탐색할 범위는 어떻게 구할 수 있을까요? 탐색할 범위를 구하기 앞서, 탐색할 영역이 정사각형이라는 점..
나무 막대( BOJ 7344 ) 문제 : https://www.acmicpc.net/problem/7344 7344번: 나무 막대 목공소에 n개의 나무 막대가 있고, 각 막대의 길이와 무게가 주어져 있습니다. 이 막대들은 기계를 이용해 하나 하나 가공 처리 과정을 거치게 됩니다. 이때, 각 막대를 처리할 수 있도록 기계를 www.acmicpc.net 문제 파악하기 N개의 나무 막대를 가공하기 위해 필요한 세팅 횟수를 구하는 문제입니다. 나무 막대는 길이(l)와 무게(w)를 가지고 있으며, 이전에 가공했던 나무 막대보다 길이와 무게 모두 크거나 같다면 세팅할 필요가 없습니다. 따라서, 한번 세팅하면 더 이상 세팅할 필요가 없는 나무 막대들을 찾는 알고리즘이 필요합니다. 알고리즘을 통해 세팅이 필요없는 나무 막대들을 골랐다면, 해당 나무 ..
다리( BOJ 9006 ) 문제 : https://www.acmicpc.net/problem/9006 문제 파악하기 왼쪽 집에서 오른쪽 집으로 가는 모든 거리의 합을 최소화하기 위해 다리를 놓아야 할 곳을 찾는 문제입니다. 다리의 길이는 항상 2이기 때문에 다리 길이에 대해서는 신경쓸 필요가 없으며, 어느 위치에 다리를 놓을 것인지만 생각하면 됩니다. 다만, N의 최대 범위가 106이며, 입력되는 집의 위치가 -107 ~ 107이기 때문에 단순히 모든 경우를 탐색하는 방법으로는 절대 해결할 수 없습니다. 대신, 중복되는 계산을 효과적으로 줄여서 정답을 찾을 수 있습니다. 문제 해결하기 만약 우리가 h 위치에 다리를 놓았다고 가정하면, 우리가 최솟값을 구해야할 수식 f(h)는 다음과 같습니다. 참고로 수식에서 배열 a과 b는 각각 ..
동전 문제( BOJ 1398 ) 문제 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 문제 파악하기 주어진 초콜릿의 가격을 만들 수 있는 동전의 최소 개수를 구하는 문제입니다. 모든 동전이 우리나라 동전 체계처럼 약수 관계를 가지고 있다면 간단하게 사용할 수 있는 가장 큰 동전부터 사용하는 그리디 기법을 사용할 수 있습니다. 하지만 문제에 제시된 동전들은 약수 관계를 가지고 있지 않습니다. 이 경우에는 가치가 큰 동전부터 사용하는 것이 최적이 아닙니다. 예를 들어 초콜릿의 가격이 30원이라고 하면, 단순히 그리디 기법을 ..
게리맨더링( BOJ 17471 ) 문제 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 파악하기 입력된 그래프를 2개의 구역으로 나눠 인구수의 차이를 최소로 하는 경우를 찾는 문제입니다. 마을의 개수(N)이 작기 때문에 모든 경우의 수를 탐색해도 충분한 문제입니다. 각각의 마을을 0번 혹은 1번 선거구로 설정한 다음, 깊이 우선 탐색과 비트마스킹을 활용하면 문제를 풀 수 있습니다. 문제 해결하기 우선, N개의 마을을 0번 혹은 1번 선거구로 나눌 수 있는 모든 경우의 수를 만들어봅시다. 재..
창업( BOJ 16890 ) 문제 : https://www.acmicpc.net/problem/16890 16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주 www.acmicpc.net 문제 파악하기 N개의 문자로 이루어진 문자열 2개에서 값을 하나씩 순서대로 가져와서 새로운 문자열을 만드는 문제입니다. 다만, 첫 번째 문자열에서 가져온 문자로는 항상 사전 순으로 앞서게 만들어야 하며, 두 번째 문자열에서 가져온 문자로는 항상 사전 순으로 뒤에 오게 만들어야 합니다. 모든 경우의 수를 찾는 방법을 가장 먼저 떠올릴 수 있지만 N의 값이 최대 300,000개이기 ..

티스토리툴바