본문 바로가기

dp8

[BOJ 1806] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 위 문제를 전체 탐색을 하면 O(N^2)으로 N이 100000이어서 시간초과가 난다. 투 포인터 알고리즘을 이용하여 풀 수 있다. 배열에 .. 2020. 4. 17.
[BOJ 13398] 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위 문제는 연속합을 구하는 문제를 조금 바꾸어서 풀 수 있다. dp배열을 한 개를 제거했을 때, 제거하지 않았을 때로 나누어서 문제를 풀면 된다. dp[i][0] = 한 개를 제거하지 않고 i번째까지의 가장 큰 연속합 dp[i][1] = 한 개를 제거하고 i번째까지의 가장 큰 연속합 이렇게 나누어서 풀면된다. 제거하지 않고 구하는 건 max(0, dp[i - 1][0]) + a[i] (a[i]는 i번.. 2020. 4. 17.
[BOJ 14002] 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net [BOJ 11053] 가장 긴 증가하는 부분 수열 과 똑같이 길이를 구한 뒤에 dp의 맨 끝부터 탐색을 하면서 가능한 최대 길이랑 같은지 다른지를 확인하면 된다. 같은 값이 나올 때마다 최대 길이를 1씩 줄여서 dp[i]에서 가능한 최대 길이를 구하면 된다. #include #include #de.. 2020. 4. 7.
[BOJ 12738] 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [BOJ 12015] 가장 긴 증가하는 부분 수열 2 과 풀이는 똑같다. 같은 코드로 통과가 된다. #include #include #include using namespace std; int n; int main() { scanf("%d", &n); vector dp; for (int i = 1; i dp.back()) dp.push_back(t); else { v.. 2020. 4. 7.
가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7.
[BOJ 11053] 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 굳이 연속적인 배열이 아니여도 상관없다. 주어진 수열을 순회하면서, 각 순회마다 현재위치에서 첫번째 위치까지 돌면서 각 위치의 값보다 현재 위치의 값이 크면 현재 위치까지의 가장 긴 증가수열은 각 위치의 길이 + 1이다. 이를 통해서 구하면 된다.. 2020. 4. 7.
[BOJ 1932] 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 문제에서는 삼각형이 예각 삼각형처럼 보이지만, 입력을 보면 직각삼각형 형태이다. 이를 통해서 보면 i번째 줄에는 (i + 1)개의 입력.. 2020. 1. 13.
[BOJ 9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 1, 2, 3의 경우만 생각하여 풀면 된다. 4는 3 + [1], 2 + [2], 1 + [3] ([n]은 n을 만들 수 있는.. 2020. 1. 2.

티스토리툴바