한 발짜국

DP 4번째 [백준 11722번] https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int N, MAX = 1; cin >> N; vector DP(N), A(N); for (int i = 0; i < N; ..

DP 3번째 [백준 1463번] https://www.acmicpc.net/problem/1463 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int DP[1000001]; void minCount(int N) { for (int i = 2; i N; minCount(N); } 이전 문제를 풀어봐서 그런지 생각보다 수월하게 풀렸다. 전에 DP문제 풀어보려고 했을 때 첫 문제가 이 문제였는데 모르겠어서 좌절했던 문제인데 풀리니까 완전 뿌듯하다!!! 아주 살짝 DP 감을 잡은듯..? 원래는 위의 DP 배열을 지역변수로, 이름은 count로 선언했었는데 배열 크기가 때문에 에러가 발생해서 전역으로 내보냈다. 전역으로 선언한 이후..

DP 두번째! DP 초보자로서 https://zzonglove.tistory.com/13 동적계획법 (Dynamic Programming) 는 어떻게 풀까? 이 포스팅은 Nitish Kumar 의 기사를 참고하여 만들었습니다. [출처] 동적계획법 (Dynamic Programming), DP 는 다항(Polynomial)한 시간안에 특정 문제를 풀기위한 기술입니다. DP 를 이용한 솔루션은 지수형태 zzonglove.tistory.com 이 게시글의 동적계획법 푸는 순서을 한 번 따라해보려했다. [백준 2579번] https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각..