본문 바로가기

문제 노트/정올

 (47)
창고 다각형( BOJ 2304 ) 문제 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 파악하기 주어진 막대 기둥을 둘러싸는 가장 작은 창고 다각형의 크기를 구하는 문제입니다. 주어진 입력의 범위가 크지 않기 때문에 어렵지 않게 해결할 수 있는 문제입니다. 이 문제에서 가장 중요한 점은 가장 높은 막대의 위치입니다. 가장 높은 막대의 위치를 기준으로 나눠서 생각해보면 쉽게 해결할 수 있습니다. 문제 해결하기 지붕을 오목하게 만들지 않으면서 창고 다각형의..
산만한 고양이( BOJ 14866 ) 문제 : https://www.acmicpc.net/problem/14866 14866번: 산만한 고양이 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 방의 수를 나타내는 정수 N(2 ≤ N ≤ 300,000)과 복도의 수를 나타내는 정수 M(1 ≤M ≤ 300,000)이 주어진다. 다음 M개의 각 줄에는 하나의 복도로 www.acmicpc.net 문제 파악하기 그래프의 사이클을 없애기 위해 제거해야 하는 정점을 찾는 문제입니다. 사이클을 이루는 정점마다 하나씩 제거해서 확인할 수 있지만, 정올 4번 문제답게 입력되는 정점의 개수가 300,000개로 어마어마합니다. 그렇기에 각각의 정점을 제거하는 O(n2) 알고리즘으로는 시간이 부족하며, 좀 더 효율적인 알고리즘이 필요합니다. 여기서 우리가 사용..
동전 뒤집기( BOJ 1285 ) 문제 : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 파악하기 2006년 정보올림피아드 고등문제의 small 버전 문제입니다. N*N개의 동전을 뒤집어서 동전의 뒷면(T)이 최소로 보이게 만들었을 때, N*N개의 동전 중 뒷면(T)의 개수를 구하는 문제입니다. 동전은 행 또는 열을 선택한 다음, 선택한 행/열의 모든 동전(N개)를 뒤집을 수 있습니다. N의 범위가 크지 않지만, 나올 수 있는 경우의 수는 어마어마하기 때문에 단순히 ..
오목( BOJ 2615 ) 문제 : https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 문제 파악하기 바둑판의 모습이 주어질 때, 흑/백의 승패여부를 판단하는 문제입니다. 종목이 오목이기에 가로, 세로, 대각선 방향으로 연결된 같은 색의 돌이 딱 5개여야하며, 만약 6개 이상 돌이 연결되어 있다면 인정되지 않습니다. 바둑판은 19*19로 이루어졌기에 2차원 배열을 사용하여 바둑판의 모습을 충분히 저장할 수 있으며, 5목인지 판단하면 되기에 놓여진 모든 바둑돌을 하나씩 검사해..
보석( 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 2478 ) 문제 : https://www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net 문제 파악하기 주어진 수열을 만들기 위해 필요한 k-왼쪽밀기와 (p, q)-구간뒤집기 작업을 구하는 문제입니다. 모든 자물쇠는 [ k-왼쪽밀기 > (p, q)-구간뒤집기 > k-왼쪽밀기 ] 순서로 작업이 이루어지기 때문에, 우리는 반대로 [ k-오른쪽밀기 > (p, q)-구간뒤집기 > k-오른쪽밀기 ] 순서로 작업을 하여 정렬된 수열의 상태(1, 2, 3, ... , n)를 만들면..
전깃줄 - 2( BOJ 2568 ) 문제 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 파악하기 최소한의 전깃줄을 잘라 서로 겹치는 전깃줄이 없게 만드는 문제입니다. 보통 이런 문제는 가장 긴 증가하는 부분 수열(이하 LIS)을 사용하며, 이 문제 역시 대표적인 LIS 문제입니다. 서로 겹치지 않는다는 건 항상 현재 가로등 번호보다 다음 가로등의 번호가 더 커야 한다는 걸 의미하며, 결국 주어진 수열 중 LIS의 길이를 찾는 문제와 동치가 됩니다. 그럼 어떻게 이 ..
공통 부분 수열 확장( 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초 안에 해결할 수는 없습니다. 그렇기 때문에 문제를 해결하기..

티스토리툴바