요새 푸는 문제마다 시간이 발목을 잡네요.

이 문제를 O(n2)으로 풀었는데 채점시 45%에서 시간초과가 뜨네요...

혹시 더 빠른 방법으로 접근 가능한가요?

이 문제는 LIS와 다른 것 같은데, 참고할만한 알고리즘 또한 알려주시면 감사하겠습니다.

시간초과 너무나 어렵네요ㅜㅜ

kesakiyo   10달 전

참고할만한 알고리즘은 없는것 같습니다.

수가 감소하거나 증가하는 순간 새로운 순서가 시작된다고 생각하시면

O(N)에 해결할 수 있습니다.

kesakiyo 님의 답변 감사드립니다.

O(n)에 해결하고자 짠 코드는 다음과 같습니다.

여기서 문제는 다음과 같은 테스트케이스 에서 발생합니다.

9

4 1 3 3 2 2 9 2 3

즉, 1 3 3 에서 증가로 인식하고(status=1) 증가가 끝나는 2부터 다시 세고있는데

정답은 3 3 2 2일 때 4입니다.

3이 증가하는 수열의 일부인 지, 아니면 감소하는 수열의 시작점 인지 어떻게 찾을 수 있을까요?

kesakiyo   10달 전

두가지 해결방법이 있겠네요.

1. 감소하는 수열과 증가하는 수열을 따로따로 세면서 나아간다.

2. 증가하는 수열을 세는 함수를 만들고 증가하는 수열을 센다. 그리고 기존의 수열을 뒤집어서 한번 더 센다.

kesakiyo님 답변에 감사드립니다.

Baekjoon Online Judge은 이렇게 도움을 받을 수 있어서 좋은것 같습니다.

초보자 입장에서 한 가지 추가질문드립니다. 이런 부분은 문제에 대한 많은 경험을 통해 쌓아지는 것인가요? 아니면 학습을 통해서 배우신건가요?

혹시 공부를 따로 하신다면 그냥 문제를 많이 푸는것이 좋을까요? 아니면 책 또는 강의를 듣는 것이 좋을까요?

간단하게 라도 조언주시면 정말 감사하겠습니다:)

kesakiyo   10달 전

음 이건 정말 경우에 따라 다르기 때문에 대답을 드리기가 상당히 애매하네요.


하지만 경험상 단순히 문제를 많이 푸는 것보다는 배경 지식을 쌓은 뒤 문제를 풀어 나가는 쪽이 훨씬 더 효율적인 것 같습니다.

그러기 위해서는 배울 수 있는 사람이 필요할 텐데 온라인 상으로는 의사소통을 해 나가기가 상당히 제약이 많습니다.

그렇기 때문에 고려대에서 알고리즘 공부를 하는 알콜이나 알프스와 같은 동아리에 문을 두드려 보는것도 괜찮지 않을까 생각해 봅니다.

지금까지는 혼자서 하려했는데

역시 함께하는게 좋을것 같군요! 조언 감사드립니다.

flflds0811   10달 전

kesakiyo님의 명답변에 knee를 탁치고 갑니다.

appa님의 좋은 링크 감사드립니다. 참고하여 공부해보겠습니다^^

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