알고리즘/백준(30)
-
[백준] [C++] 1208번 부분수열의 합2 (조합, 중간에서 만나기)
1. 문제 1208번: 부분수열의 합 2 (acmicpc.net) 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 2. 풀이1 이 문제는 입력의 크기 때문에 메모이제이션과 완전탐색으로는 해결하지 못한다. 따라서 주어진 수열을 절반으로 쪼개 각각의 모든 조합의 합을 구한뒤 두개의 합이 S인 조합의 개수를 구해야한다. 각각 따로 조합의 합을 map의 key로, value에 가짓수를 담고 마지막에 right[ s - left[]] 와 left[] 를 곱하면 합이 s인 전체의 ..
2021.06.30 -
[백준] [C++] 1202번 보석 도둑 (greedy, priority queue)
1. 문제 1202번: 보석 도둑 (acmicpc.net) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 2. 풀이 이 문제는 탐욕법으로 해결할 수 있다. 가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다. 하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다. 따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다. map을 사용하면 빠르게 원소를 제외할 수 있고, 최소 원소 또한 찾..
2021.06.30 -
[백준] [C++]12852번 1로 만들기 (dp, tracking)
1. 문제 12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 2. 풀이 3가지 함수를 사용하여 1로 만드는 것 전형적인 dp문제로 모든 경우의 수를 따져 함수를 사용할때마다 1씩 더하면서 기저조건인 1이 나올경우 0을 리턴, 0이나올경우 max값을 리턴하도록 함수를 짜면 문제없이 잘 동작할것이다. 이 문제는 또 과정을 추적해야한다. 과정을 추적하는 단순한 방법은 함수의 번호를 최적값과 같이 저장하는 것 이다. 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..
2021.06.29 -
[백준] [C++] 2261번 가장 가까운 두 점 (sweeping)
1. 문제 2261번: 가장 가까운 두 점 (acmicpc.net) 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 아래 문제 풀이를 보고 작성하였다. *[C/C++] 백준 2261번 - 가장 가까운 두 점 (라인 스위핑) :: 코딩 공부 일지 (tistory.com) 2. 풀이 set과 mindist의 정의가 다음과 같을때 큰 틀은 다음과 같다. set: 고려될 수 있는 점집합 mindist: 현재까지 가장 짧은 두점 거리 1) x축 기준으로 정렬 2) 첫 두점을 기준으로 m..
2021.06.29 -
[백준] [C++] 11444번 피보니치 수 6 (분할정복)
1. 문제 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 이 문제는 엄청나게 큰 n번째 피보나치 수를 구하는 문제이며 피보나치 수의 성질을 잘 알고 있어야 풀 수 있는 문제이다. 피보나치 수의 점화식은 다음과 같다 f_n = f_n-1 + f_n-2, (f0 = 0, f1 = 1) 이 식을 다음과 같이 열벡터로나타낼 수 있다. C_n은 원소의 합이 f_n이 되는 열벡터이다. C_n = { {f_n-2}, {f_n-1}} 그리고 이 식을 풀어쓰면 다음과 같은 식이 나오게 된다. C_n = { {f_n-2}, {f_n-2 +..
2021.06.29 -
[백준] [C++] 6549번 히스토그램에서 가장 큰 직사각형(sweeping, 분할 정복, stack)
1. 문제 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 2. 분할정복 직사각형이 있는 경우의 수는 한 부분문제에서 총 3가지의 경우 로 나눌 수 있다. 1. 왼쪽~ 중간 쪽에 최대인 직사각형이 있는 경우 2. 중간~오른쪽 쪽에 최대인 직사각형이 있는 경우 3. 중간을 포함하여 위의 두 영역에 걸쳐 있는 경우 직관적으로 한 문제당 왼쪽, 오른쪽 두개의 부분문제로 나뉘어지고, 중간을 ..
2021.06.28