park94128   1년 전

쉬운버전은 DP 문제임을 어느정도 짐작하고 풀었더니 맞았고, 실제로도 분류상 DP라서 문제없이 통과했습니다. 그런데 이 문제를 처음 봤을땐 입력 범위를 보고 DP하듯 풀면 반드시 시간초과 생기겠다 싶었고 어떻게 푸는지 고민하다가 분류를 보고 이분 탐색인 것을 확인했습니다.

이게 이분 탐색 문제라는 것을 예상 못해서 한 번 뇌절 왔는데 이분 탐색으로 어떻게 푸는지 생각을 계속 해봐도 방법이 떠오르지 않았고 결국 힌트를 찾아본 후에야 이해했습니다.

문제를 봤을때 어떤 알고리즘인지 파악하는 것, 그리고 알고리즘을 알아냈다면 어떻게 풀어야 할지 짐작이라도 바로 할려면 결국 문제를 많이 풀어보는것 말고는 답이 없겠죠?

not_strober   1년 전

LIS, 또는 LIS의 길이를 이분 탐색으로 O(N log N)에 구하는 방법은 웰노운입니다. 문제를 많이 풀어보면서 다양한 유형을 접하시는 것이 좋다고 생각합니다. 

댓글을 작성하려면 로그인해야 합니다.