[크래프톤 정글] 12일차 : 가장 긴 증가하는 부분 수열 (DP)

오늘은 백준에서 가장 긴 증가하는 부분 수열을 풀었다.

블로그: DP(Dynamic Programming)이란?

이 문제는 이분탐색을 주제로 주어진 문제이다. 이분탐색으로 어떻게 풀지 계속 고민해봤지만, 아이디어가 계속 떠오르지가 않았다. 우선 문제를 풀어 놓고 생각해보자는 생각에 우선 떠오르는 아이디어로 풀었다.

dp list 를 만들고, 길이 N만큼 1로 숫자를 채워 놓는다.

이후 for문을 2번 중첩으로 사용하여, 시간복잡도는 O(N^2)으로 작동한다.
첫번째 for문에서는 비교대상 i를 고정시켜 두고,
두번째 for문에서는 j를 증가시키면서, 비교대상 i의 최대 높은 위치를 DP에 저장 시켜놓는 방식으로 구현했다.

GitHub: 가장 긴 증가하는 부분 수열 구현 (코드보기)

이게 왜 DP 라고 하는 것인지 조금 더 공부를 해서 정리해봐야 할 것 같다. 정리된 내용은 앞써 안내된 블로그에 링크를 걸어 놓겠다.

🎯 TO DO

• 가장 긴 증가하는 부분 수열 문제가 이분탐색으로 풀 수 있다고 해서, 이분탐색으로 어떻게 풀 수 있을지 고민해보기