allgoodlife   3달 전

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

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

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

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

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

kesakiyo   3달 전

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

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

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

allgoodlife   3달 전

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   3달 전

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

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

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

allgoodlife   3달 전

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

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

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

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

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

kesakiyo   3달 전

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


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

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

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

allgoodlife   3달 전

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

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

flflds0811   3달 전

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

allgoodlife   3달 전

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

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