본문 바로가기

분류 전체보기

 (84)
백준 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..
이분탐색 기본적이면서도 너무나도 강력한 이분탐색에 대한 정리를 하고자 한다. 이분탐색이란 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 것을 말한다. 시간복잡도를 따질 때 log N이 붙는 경우가 많은데, 이 로그의 밑은 보통 2를 쓴다. log가 붙었다는 것은 이분탐색 등이 사용되었다는 것을 의미하는 경우가 많다. 4라는 숫자에 밑이 2인 로그를 씌우면 2가 된다. 2의 11승인 2048에 로그를 씌우면 11이 되어버린다. 이것이 의미하는 것은 2048개의 원소를 완전탐색하기 위해서 2048번 일일이 확인하지 않아도, 단 11번 만에 전 범위를 볼 수 있다는 뜻이다. 2048개 숫자를 일종의 이진트리로 재구성하였을 때 그 깊이가 11이라는 의미도 된다. 2048 대 11은 드라마틱하게..
백준 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 가 될 것 같지만, ..

티스토리툴바