이번에는 진짜 너무 어려웠다. 정답비율이 40%문제인데 다들 대단한거 같다. 물론 문제 자체가 기본적인 LIS유형중 한개로 쉽게 풀리지만 알지 못하는 상태에서 생각해 내기 굉장히 어려운거 같다. 따라서 나도 LIS를 공부하고 기본 코드로 풀이를 할 수 있었다.
우선 문제를 보자
문제는 간단하다. 수열이 주어지고 여기서 "최장 증가 부분 수열"을 구하면 된다.
내가 풀이를 쓰는 것보다 더 좋은 풀이가 있어서 고수님의 글을 참고하면 좋을것 같다.
https://chanhuiseok.github.io/posts/algo-49/
결론적으로 LIS의 풀이 방법은 2가지가 있다.
1. DP를 활용하여 메모이제이션 기법을 활용한다. 단, 시간복잡도가 O(N^2) 이다.
2. 이분탐색을 활용하여 배열을 작은 수로 갱신해준다. 시간 복잡도는 O(N log N) 이다.
아마 LIS를 응용하게 되면 난도가 높아지므로 이분탐색을 통해 LIS를 구하는 방법을 잘 기억해 놓아야 할 거 같다.
'알고리즘' 카테고리의 다른 글
[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP ) (0) | 2021.08.28 |
---|---|
[python3] 백준 1238 풀이 ( 파티, 다익스트라 ) (0) | 2021.08.28 |
#5 알고리즘 공부 8/24 리뷰 (0) | 2021.08.24 |
[python3] 백준 2110 풀이 ( 공유기 설치, 이분탐색 ) (0) | 2021.08.24 |
[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 ) (0) | 2021.08.22 |