본문 바로가기

문제 노트

 (157)
전깃줄 - 2( BOJ 2568 ) 문제 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 파악하기 최소한의 전깃줄을 잘라 서로 겹치는 전깃줄이 없게 만드는 문제입니다. 보통 이런 문제는 가장 긴 증가하는 부분 수열(이하 LIS)을 사용하며, 이 문제 역시 대표적인 LIS 문제입니다. 서로 겹치지 않는다는 건 항상 현재 가로등 번호보다 다음 가로등의 번호가 더 커야 한다는 걸 의미하며, 결국 주어진 수열 중 LIS의 길이를 찾는 문제와 동치가 됩니다. 그럼 어떻게 이 ..
세 수의 합( BOJ 2295 ) 문제 : https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 파악하기 N개의 숫자로 이루어진 집합 U에서 3개의 숫자를 적절하게 선택해서 집합 U에 있는 값 중 만들 수 있는 가장 큰 값을 만드는 문제입니다. N의 개수가 최대 1,000개이기 때문에 O(n3)알고리즘으로는 시간초과가 나오게 됩니다. 그렇다면 어떤 알고리즘을 사용해서 시간 복잡도를 줄일 수 있을까요? 여기서는 3개의 숫자의 합을 ..
1의 개수 세기( BOJ 9527 ) 문제 : https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 문제 파악하기 주어진 자연수 A, B 사이의 모든 숫자를 이진수로 표현했을 때, 사용되는 모든 1의 개수를 세는 프로그램입니다. 이렇게 특정 구간 내에 조건을 만족하는 값의 개수를 세는 문제에서는 주로 누적합을 구하는 알고리즘을 활용해서 문제를 해결하며, 이번 문제 역시 비슷한 방식을 사용하면 문제를 해결할 수 있습니다. 여기서 말하는 누적합을 구하는 알고리즘이란..
공통 부분 수열 확장( BOJ 21762 ) 문제 : https://www.acmicpc.net/problem/21762 21762번: 공통 부분 수열 확장 어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab는 $X$ = ababca의 부분수열이지만, $Y$ = cbabba의 부분수열은 아니다. 두 개의 수열이 주 www.acmicpc.net 문제 파악하기 주어진 문자열 X와 Y의 공통 부분 수열을 확장할 수 있는지 확인하는 문제입니다. W는 X와 Y의 공통 부분 문자열이며 W를 확장시킬 수 있다면 1을, 확장시킬 수 없으면 0을 출력하는 결정 문제입니다. 단순 반복문을 사용하는 알고리즘을 사용하면 정답을 구할 수 있지만, 1초 안에 해결할 수는 없습니다. 그렇기 때문에 문제를 해결하기..
레이스( BOJ 1508 ) 문제 : https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net 문제 파악하기 M명의 심판을 배치하는 여러 가지 경우 중, 가장 가까운 심판 사이의 거리가 최대인 경우를 구하는 문제입니다. 만약 모든 경우의 수를 조사한다면, 최악의 경우 1,000,000개 자리 중 50명의 심판을 배치하는 모든 가짓수를 조사해야 합니다. 터무니없이 많기 때문에 문제를 조금 바꿀 필요가 있습니다. 문제를 최적화 문제에서 결정문제로 바꿔봅시다. ..
그래프 균형 맞추기( BOJ 22344 ) 문제 : https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 문제 파악하기 그래프 내 간선의 가중치가 주어질 때, 그래프의 균형을 맞출 수 있는 여러 가지 방법 중 모든 정점 가중치 값의 절댓값 합이 가장 작은 경우를 구하는 문제입니다. 그래프의 균형은 두 정점을 연결하는 간선의 가중치와 두 정점의 가중치의 합이 같은 경우를 의미합니다. 문제 예시 그림과 같이 모든 간선의 가중치 값이 연결된 정점의 합과 일치하는 경우를 의미하며, 균..
개구리 점프( BOJ 17619 ) 문제 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 문제 파악하기 개구리가 점프를 해서 원하는 통나무까지 이동할 수 있는지 확인하는 문제입니다. 통나무들은 항상 가로방향으로 연못에 떠 있으며, 개구리는 항상 수직적인 방향으로 점프할 수 있습니다. 그렇기에 개구리는 항상 통나무의 값이 조금이라도 겹친다면 무조건 점프할 수 있습니다. 따라서, 우리는 모든 통나무에 대해서 서로 겹쳐있는지 확인하고, 겹..
헬기 착륙장( BOJ 22348 ) 문제 : https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 2개의 페인트통을 사용해서 헬기 착륙장을 그릴 수 있는 경우의 수를 구하는 문제입니다. 헬기 착륙장은 반지름이 서로 다른 원으로 구성되어 있으며, 반지름이 1부터 R까지 1씩 차이나게 그릴 수 있습니다. 하나의 헬기 착륙장은 항상 하나의 색으로만 만들 수 있으며, 각각의 페인트통이 최대 50,000개 있기 때문에 그릴 수 있는 헬기착륙장의 최대 크기는 대략 450입니다. 따라서, 우리..

티스토리툴바