본문 바로가기

Problem Solving

 (67)
백준 2075 N번째 큰 수 www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 정렬 또는 우선순위 큐를 통해 해결할 수 있다. 문제의 메모리 제한을 눈여겨 보자. 12MB로 평소와 다르다. int형 정수 1개는 4byte를 갖는다고 한다. 1천개면 4kb이고, 1백만개면 4MB이니 12메가 바이트는 겨우 3백만개의 정수만 담을 수 있는 것이다. 문제의 조건에서 N이 1500이므로 1500 x 1500 = 2,250,000 (225만)개의 정수가 필요하므로 다 담을 수 있을 것 같지만,..
백준 1654 랜선 자르기 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제 또한 이분탐색의 기본적인 문제이다. 문제에서 보면 랜선의 길이는 최대 2^31-1까지 될 수 있다고 했는데 이는 int 범위 내에서 가장 큰 값이다. 이처럼 이분탐색 문제는 어마어마한 범위를 주는 경우가 많다. 어차피 몇 번만 탐색하면 전 범위를 다 볼 수 있기 때문이다. 이분탐색 문제를 몇 개 풀고 나면 이분탐색의 기본 포맷이 잡힐 것이다. 아래와 같다. 먼저 문제의 상한..
백준 2110 공유기 설치 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 이 문제 해결에 앞서 이분탐색에 대해 기본 개념을 익히고자 한다면, 다음의 포스팅을 한번 살펴보기 바란다. 이분탐색 : t-anb.tistory.com/18 이분탐색 기본적이면서도 너무나도 강력한 이분탐색에 대한 정리를 하고자 한다. 이분탐색이란 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 것을 말한다. 시간복잡도를 따질 t-a..
백준 5214 환승 www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 신선한 발상, 새로운 시각이 필요한 문제이다. 그 아이디어가 떠오르면 다음은 일반적인 다익스트라 또는 BFS문제가 된다. 하지만 아이디어가 떠오르지 않으면 풀기 어려울 수 있다. 가끔 퀴즈문제들을 해결하는 기발한 아이디어를 보면, 문제상에는 존재하지 않는 무언가를 더 그려 넣어서, (또는 집어넣어서) 해결하는 경우들이 있다. 또는 뭔가 문제상에서 정확하게 제한을 두진 않았지만, 우리가..
백준 1989 부분배열 고르기 2 www.acmicpc.net/problem/1989 1989번: 부분배열 고르기 2 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 �� www.acmicpc.net 이 문제는 앞서 포스팅하였던 부분배열 고르기에서 최대 점수를 받는 실제 부분 배열의 앞 뒤 인덱스까지 출력해야 하는 문제이다. 부분 배열 고르기 문제에서 모노톤 스택을 잘 이해하였다면 최대 점수 갱신 시에 인덱스만 계속 기록해주면 된다. 이전 포스팅에서 언급한 바와 같이, 스택의 순기능을 활용하여 O(n^2)의 시간복잡도를 O(n..
백준 1725 히스토그램, 2104 부분배열 고르기 www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 � www.acmicpc.net www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 �� www.acmicpc.net 대단..
백준 15663 N과 M (9) www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 너무나 필수적인 N과 M시리즈의 9번째 문제이다. 개인적으로는 9번부터 더욱 필수다. 이 문제는 재귀와 백트래킹으로 해결하였다. 다만 문제를 읽고 주의할 점은, 똑같은 수가 여러 번 주어지면 모두 갖고는 있되, 각 경우의 수가 완전히 일치하는 경우는 배제한다는 점이다. 문제에서 주어진 예제를 보면, 3 1 4 4 2 가 있다. 이 경우, 하나를 뽑을 수 있는데 4가 2개 있어서 2 4 4 가 될 것 같지만, ..
백준 1992 쿼드트리 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 분할 정복의 기초라고 볼 수 있는 문제다. 분할 정복이란 어떤 일정한 규칙 또는 반복된 연산이 적용되는 정점 또는 상황 들을 여러 개로 나누어(분할) 빠르게 처리하고 다시 합쳐주는 (정복) 풀이 방식이라고 할 수 있다. 여기서 중요한 부분은 바로 '합치기가 가능한가?'이다. 이전 포스팅(행렬 곱셈 순서)에서도 보았듯이, 나누고 합치기를 할 때 적용되는 어떠한 규칙 등이 있어야 한다. 이 문제에서는 ..

티스토리툴바