Algorithm/Dynamic Programming

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이과정 ①문제 들여다보기 이 문항은 앞전에 푼 11053문제에서 아주 살짝 업그레이드 된 버전의 문제이다. https://stopmin.tistory.com/46 [백준] 11053번 가장 긴 증가하는 부분수열 (Python) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이과정 ①문제 바라보기 N으로 전체 수열의 길이를 받고, 다음줄에 array가 입력된다. array에서 몇 개의 수를 지움으로써 만들 수 있는 가장 긴 증가하는 수열의 길이를 인쇄하는 문제다. ②아이디어 열기 이 문제는 동적계획법으로 해결이 된다. 이중 for문을 활용하여서 해결되는 문제였다. 현재 해당하는 위치의 숫..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이과정 ①문제 바라보기 DP문제임은 자명하다. 계단 오르기 문제랑 굉장히 유사하게 느껴졌다. 더보기 이것이 계단오르기다. https://stopmin.tistory.com/42 [백준] 2579번 계단오르기 (Python) https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-h..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이과정 ①문제 바라보기 DP문제인데 규칙을 발견해야한다고 생각했다. 0과 9의 경우 특별한 Case이기에 따로 분류해서 처리해야 한다. ②아이디어 펼치기 아래는 수형도이다. N == 1일 경우, 0은 불가능하고 나머지 1~9는 모두 가짓수가 1개가 된다. N == 2일 때 부터 규칙이 발견이 되는데 편의상 N이 3~4일 때로 예시를 들었다. dp[4][0]으로 가기 위한 방법의 개수는 dp[3][1] 온전히 갖게 된다. dp[4][9]으로 가기 위한 방법의 개수는 dp[3][8] 온전히 갖게 된다. 나머지 경..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 과정 ①문제 바라보기 처음에 이 문제가 Greedy 문제인 줄 알았다. 그러나 알고보니 DP문제! 뭔가 greedy로 풀릴 것 같기도하다. 이 문제도 메모이제이션 기법으로 풀릴 것이다. 문제에서 내가 할 수 있는 조치는 다음과 같다. X가 3으로 나누어 떨어지면 3으로 나눈다. X가 2로 나누어 떨어지면 2로 나눈다. 1을 뺀다. ②아이디어 펼치기 자명한 사실이 있다. N을 만드는 데 x번의 단계가 필요하다면 그냥 -1만 가능하다고 할 때, N+1은 x+1단계가 필요하다. 이 문제를 풀기 위해서는 dp 테..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이과정 ①문제 들여다보기 dp 문제임은 자명하고, dp테이블을 만들어서 for문을 통해서 답을 도출하는 것임에 분명하다. 계단을 타는 조건은 세 가지인데 한 번에 한 계단 또는 두 계단씩 오를 수 있음 연속된 세 계단은 오를 수 없음 마지막 도착 계단은 무조건 밟아야함 ②아이디어 펼치기 1번 조건은 for문으로 해결할 수 있다. 3번 조건은 계단순서를 reverse해서 미리 한 칸을 밟아놓은 상태로 시작하면..