sium   6달 전

코드는 문제에서 원하는 결과를 출력하는데, 값이 조금만 커져도 시간 초과가 뜨네요.

재귀함수를 이용하여 조합순열을 구한 뒤에 비교하여 맞는지 틀린지 출력하도록 했는데,


시간을 줄이는 방법이 있나요?


아니면 처음에 접근 방법이 틀린건가요??ㅠㅠ

flflds0811   6달 전

코드를 자세히 보지 않았지만

해당 문제는 LIS(longest inceasing subsequence) 문제로

해당 문제를 푸는 알고리즘을 공부하신 후에 풀어보시는 것이 좋습니다.

기본적으로 다이나믹 프로그래밍을 사용하는 O(N^2)방식과

다이나믹 프로그래밍과 세그먼트트리를 이용하는 O(NlogN) 방식,

lower_bound를 이용하는 O(NlogN)방식이 있습니다.

해당 알고리즘을 찾아 공부하신 후 문제를 풀어보세요

sium   6달 전

감사합니다. LIS라고 처음 들어봐서 잠시 봤는데, 많은 도움이 될거 같네요

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