본문 바로가기

전체 글

 (191)
스타트링크 타워( BOJ 1089 ) 문제: https://www.acmicpc.net/problem/1089 1089번: 스타트링크 타워 스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다. 숫자 www.acmicpc.net 문제 파악하기 엘리베이터의 전구를 파악해서 나올 수 있는 모든 숫자의 평균을 구하는 문제입니다. 10-5까지의 오차를 허용하기 때문에 맨 마지막에 평균을 구해주면 실수 값을 처리하는데 크게 문제가 없는 문제입니다. 이 문제에서 조금 까다로운 부분은 엘리베이터의 층을 표현하는 부분입니다. 층과 층 사이는 '.'으로 구분되어 있으며, 숫자들은 0부터 9까지 서로 다른 모습을 ..
자물쇠( 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)를 만들면..
수 지우기( BOJ 1467 ) 문제 : https://www.acmicpc.net/problem/1467 1467번: 수 지우기 첫째 줄에 세준이가 가지고 있는 N자리의 수가 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에 세준이가 지울 숫자들이 공백 없이 주어진다. 지울 숫자의 개수는 N보다 작으며, 항상 www.acmicpc.net 문제 파악하기 세준이가 가지고 있는 숫자 중 제시된 지울 숫자들을 지워서 만들 수 있는 가장 큰 숫자를 구하는 문제입니다. 문제 자체는 이해하기 어렵지 않지만 문제를 해결할 전략을 세우는데 생각이 필요한 문제입니다. 문제를 해결하기 위해 우리가 초점을 맞춰야 할 핵심요소는 바로 큰 수의 조건입니다. 큰 수가 되기 위해서는 큰 숫자가 왼쪽에 있어야 합니다. 이 점에 주목하면 문제를 해결..
아우으 우아으이야!!( BOJ 15922 ) 문제 : https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 문제 파악하기 N개의 선분을 수직선 위에 그렸을 때, 그어진 모든 선분의 길이의 합을 구하는 문제입니다. 입력에 따라 선분들이 겹치는지 확인할 필요가 있습니다. 다행히 선분의 개수가 100,000개이기 때문에 충분히 정렬을 사용할 수 있습니다. 문제 해결하기 모든 선분을 왼쪽 좌표 기준으로 정렬하면 가장 왼쪽에 위치한 선분부터 탐색을 시작할 수 있습니다. 가장 왼쪽의 선분의 왼쪽과 오른쪽을 각각 (l, r)으로 설정할 수 있으며, 다음 선분..
전깃줄 - 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초 안에 해결할 수는 없습니다. 그렇기 때문에 문제를 해결하기..

티스토리툴바