Notice
Recent Posts
Recent Comments
Link
목록14002번 (1)
궤도
[백준] 14002번 : 가장 긴 증가하는 부분 수열 4
문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 단순히 수열의 길이만 구하던 위 문제에서 응용된 문제이다. 처음에는 그냥 length가 늘어날 때마다 dp 배열을 그대로 복사하면 되는거 아닌가? 했다가 반례를 만났다. 10 3 7 4 1 8 이 경우 11053에서 작성한 내 코드 기준 dp를 그대로 복사해오면 1 4 8이란 결과가 나온다. 딱봐도 말도 안된다는 것을 알 수 있다. 그래서 배열의 ..
💻 현생/⛓ 알고리즘
2021. 4. 21. 15:14