https://www.acmicpc.net/problem/2143 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 누적 합(Cumulative Sum) - 이분 탐색(Binary Search) 우선 두 배열의 크기가 모두 1000이기 때문에, O(N^2)의 이중for문을 통해 가능한 모든 부분배열의 합의 경우의 수를 Asumcase, Bsumcase에 저장하였다. 그 이후, O(logN)의 lower_bound, upper_bou..
알고리즘 문제풀이
https://www.acmicpc.net/problem/2467 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 투 포인터(Two Pointer) - 이분 탐색(Binary Search) 간단한 투 포인터 문제로 보인다. 과정은 이러하다. (1) 용액 배열의 양 끝을 초깃값으로 잡은 뒤, 서로 다가오면서(투포인터) 두 개의 합이 0에 가장 가까울 경우 저장해준다. (2) 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net - 이분 탐색(Binary Search) - 다이나믹 프로그래밍(Dynamic Programming) - 너무나도 중요한 문제이다. 가장 긴 증가하는 부분수열을 구하는 풀이법은 크게 두 가지가 있다. 첫 번째는 길이가 N인 수열을 돌면서, "현재의 숫자 앞에서 자신보다 작은 수이면서 가장 큰 부분수열을 가진 값 + 1" 을 구하는 시간복잡도 O(N^2)인 풀이법이 있다. 두 번째는 "현재의 숫자 ..
https://www.acmicpc.net/problem/1253 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net - 이분 탐색 (Binary Search) - 투 포인터 (Two Pointer) 투 포인터를 이용하여, 서로 다른 두 수를 지목했고, 이들의 합을 구했다. 시간복잡도의 경우, - N개의 숫자를 모두 순회해야 하므로 O(N) - 각각의 숫자들이 서로 다른 두 수의 합으로 구할 수 있는지를 구하는 것은 투 포인터로 구현했으므로 O(N) 따라서 O(..
https://www.acmicpc.net/problem/2110 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net - 이분 탐색(Binary Search) 이 문제를 풀기 전에 파악해야 하는 점은, 문제의 조건(가장 인접한 두 공유기 사이의 최대 거리)을 구하는 데에 있어서, "첫 번째 공유기"는 무조건 포함한다는 것이다. 또한, 우리가 Focus해야 하는 부분은 "간격"이다. (공유기의 위치가 아니다.) 예제를 예로 들어 보자. [1, 2, 4, 8, 9] 에서, 공유기 2개만 사용한다고 가정했을 때, 공유..
https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net - 이분 탐색(Binary Search) - 깊이 우선 탐색(Depth First Search) 1. 30개의 물건이 있고, 이를 선택하는 경우의 수를 모두 더하는 최대 경우의 수는 이다. 따라서 O(2^N)의 시간복잡도를 가지므로 제한시간 1초인 문제에서 시간초과가 발생한다! 결국 이것을 줄일 수 있는 방법은 1. 물건들을 절반으로 분리한다.(part1 집합과 part2 집합으로 분리) 2. 각..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net - 다이나믹 프로그래밍(Dynamic Programming) 예제 입력 1을 참고하여, x축은 전봇대 A에서 나가는 전깃줄, y축은 전봇대 B의 전깃줄을 표시해 봤다. 백준 사이트의 예제 입력을 보면서 이 그림을 보면 된다. 자, 이렇게 정리하면 B전봇대 기준에서의 수열은 [8, 2, 9, 1, 4, 6, 7, 10] 이다. 여기서 곰곰이 생각해 봤다. 문제에서 "없애야 하는 전깃줄의 최소 개수" 의 의..
https://www.acmicpc.net/problem/2056 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net - 그래프 이론(Graph Theory) - 위상 정렬 (Topological Sort) - 다이나믹 프로그래밍(Dynamic Programming) 1. 위상 정렬 문제다. 아래는 예제 입력 1에 관한 내용을 그림으로 표현하였다. 2. 위상정렬은 간선(edge), 진입차수(Indegree)에 관한 배열과 큐(queue)를 이용하여 구현한다. 3. 하지만 이 문제는 ..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net - 그래프 이론(Graph Theory) - 다익스트라(Dijkstra) 1. 각 마을에서 파티장소까지 가고, 파티장소에서 다시 자신의 마을로 돌아오는 최단경로를 모든 vertex에 따라 구해야 한다. 그림은 다음과 같다. (4번 마을에 사는 사람에 대한 예시도 적었다.) 2. 결국 중요한 점은, 기존의 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것..
https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net - 우선순위 큐(Priority Queue) - 그리디 알고리즘(Greedy Algorithm) 1. 처음에는 파스칼의 삼각형을 떠올려, 중간에 있는 값들을 최솟값으로 지정하고, 가장자리로 갈수록 오름차순의 나열을 떠올렸다. 하지만 이 과정을 한다고 해도, 덧셈 과정에서 for문을 필연적으로 두 번 사용해야 하기에 O(N^2)의 시간복잡도를 가져 시간초과가 날 것이라는 예상을 했다. 그 해결책..
