모든 경험을 소중하게

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14002번 문제 '가장 긴 증가하는 부분 수열 4' 이다. 이 문제는 LIS 로 알려진 유명한 문제이다. 이 문제를 풀기 위해 이용한 알고리즘은 DP 이다. 물론, 2중 for 문을 이용해서 전체를 계속 순회해도 문제를 풀 수 있다. 특히 이 문제에서는 크기가 1000 이므로, O(n^2) 이다. 따라서 충분히 시간 내에 풀 수 있다. 하지만 DP 를 이용한다면, O(n) 으로 계산 할 수 있다. DP 문제는 다들 많이 풀어보는 유형이라 방법은 알고 있겠지만, 모르는 분들에게 도움이 되고자 설명한다. dp 배열을 수열 길이만큼 잡은 후, 0 으로 초기화 해준다. 여기서 C 언어를 사용하고 있다면, 전역변수로 선언하면 0..