미니베리

1) 문제수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.예시A = {10, 20, 10, 30, 20, 50} 가능한 증가 부분 수열 중 하나10 → 20 → 30 → 50 따라서 정답은 4이다.여기서 중요한 점은 "연속된 수열이 아니라 부분 수열"이라는 점이다.즉 중간 값을 건너뛰어도 된다.2) 처음 접근 (실패했던 아이디어)처음에는 다음과 같이 2차원 DP를 생각할 수도 있다.dp[i][j] = i까지 고려했을 때 j를 선택한 경우 하지만 이렇게 설계하면상태 수가 불필요하게 많아지고문제 해결에 필요하지 않은 정보까지 저장하게 된다.LIS 문제에서는 사실 마지막 원소만 알면 충분하다.그래서 1차원 DP로 해결하는 것이 정석적인 방법이다.3) 핵심 아이디어DP 배열을 다음과..

백준 10844번 쉬운 계단 수1. 문제https://www.acmicpc.net/problem/10844 어떤 수의 인접한 자리의 차이가 항상 1이면 이를 계단 수라고 한다.문제는 다음과 같다.길이가 N인 계단 수의 개수를 구하시오.단 0으로 시작하는 수는 계단 수가 아니다.2. 처음 떠올릴 수 있는 방법 (완전 탐색)처음에는 이런 방식이 떠오를 수 있다.1자리 숫자 만들기→ 뒤에 숫자를 붙이기→ 인접한 자리 차이가 1인지 확인 예를 들어1 → 10, 122 → 21, 233 → 32, 34 이런 식으로 계속 숫자를 만들어 나가는 방식이다.하지만 이 방식은 문제가 있다.길이가 최대 100이기 때문에 가능한 경우의 수가 거의 10^100수준이 된다.즉 완전탐색은 불가능하다.3. 핵심 아이디어 (DP)숫자..