1. 문제https://www.acmicpc.net/problem/1562 1562번: 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 2. 풀이DP적 접근비슷한 문제로 [백준 18044] 쉬운 쉬운 계단수가 있습니다. 이 문제를 먼저 이해해야 합니다. 이 문제는 기본적으로 [18044 쉬운 계단수]와 동일하게 최적 부분구조와 반복되는 부분문제를 가집니다. 하지만 쉬운 계단 수와는 다르게 "0부터 9까지 숫자가 모두 포함되어야 한다"는 조건이 추가되었습니다. 기존의 두 가지 정보를 이용한 DP 테이블로는 원하는 답을 얻을 수 없습니다. 따라서 부분문제를 해결할 때 "현재 구성된 계단수의 숫자의 조합"이라는 정보도 추가되어야..

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 DP적 접근 문제를 읽고 세번째까지는 구조도를 그려봤습니다. 구조를 보면 결국 완전탐색을 통해 모든 경우의 수를 찾는 문제입니다. 그런데 다음 자리로 늘어나는 과정에서 완전탐색의 시간복잡도는 O(2ⁿ)이 됩니다. 따라서 DP나 그리디를 써야 하는데 아까 그린 구조도를 살펴보면 두 가지 특징을 가집니다. 반복되는 부분문제(Overlapping Subproblems) 다음 자리로 늘어나는 과정에서 같은 부분문제들이 반복됩니다. 최적 부분구조(Optimal Substructur) 위의 부분문제들..

두 가지 방법으로 접근할 수 있다. 1. LIS를 두번한 다음 비교하기 2. 반복문을 돌며 기준점을 잡고 증가하는 부분 수열과 감소하는 부분 수열을 구한 뒤 최댓값 구하기

https://jeonyeohun.tistory.com/86 [알고리즘 정리] 배낭 문제(Knapsack Problem) Knapsack Problem Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 jeonyeohun.tistory.com 예제로는 [백준 12865번] 평범한 배낭을 참고한다. 이 문제는 NP-hard문제이다. optimazation problem 모든 경로를 탐색하여 최적해를 찾는 문제!! DP를 이용해야겠지?? 경로: 해당 무게로 만들 수 있는 조합 값: V가치 1. top - down 방식 2. bottom - up 방식 tabulat..

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..

1. 구간합이란? 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 개념 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다. 자연수 n에 대하여 수열 A(n)의 1 ~ n까지의 합을 S(n)이라고 할 때 두 자연수 a ~ b까지의 합은 S(b) - S(a-1)이다. [증명] a > a >> b; for (int i = 1; i > A[i]; //S(b), S(a) 구하기 for(int i=1; i Ai; S[i] = S[i-1] + Ai; } cin >> a >> b; cout