rainyCode rainyCode

백준 1932번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 이 문제는 규칙이 눈에 보여서 어떻게 코드로 잘 정리하냐가 관건인 문제 같다. 문제 링크 알고리즘 최댓값의 경로를 파악해야 하는데 dfs 같이 모든 경로를 탐색해 버리면 n이 최대 500개라 해보진 않았지만 분명 시간 초과가 날 것 같아, 위에서 부터 한번에 돌면서 최댓값을 찾는 dp를 이용해야된 다. dp 이중배열을 선언해 dp[i][j]라 하면, 위에서 부터 i번째 층에 왼쪽부터 j번째 값의 최댓값을 저장한다고 하자. 지금부터 dp배열의 값들을 구해볼 것이다. 우선 삼..