3-I 17071 시간 초과

안녕하세요 선생님, 17071 문제를 푸는데 도저히 시간 초과가 해결이 되지 않아 질문드립니다.

http://boj.kr/205232630d404eddbd6e2f0eeb5e5627

맨 처음에 주석에 달린 조건문이 없을 때는 메모리 초과가 났었고, 이를 해결하기 위해 조건문을 추가했어요. 다만 해당 방법으로 구현하니 시간 초과 문제가 나더라고요. 더더욱 최적화를 해야할 것 같은데, 현재 제 코드에서 더 최적화할 수 있는 방법이 뭔지 궁금합니다.

그리고 이 문제만 6시간 이상 붙잡고 있는데, 이게 맞는건지 잘 모르겠어요.

아예 아이디어가 생각이 안나면 이렇게까지 시간을 붙잡고 있지는 않고, 바로 아이디어 힌트를 얻으려고 할텐데 어느정도 될 것 같은 아이디어(==전체적인 설계나 시간 복잡도, 공간복잡도를 고려했을 때)로 구현했을 때 예상치 못한 동작을 한다던가, 메모리 초과나 시간 초과를 겪으면 제 방법에서 보완하기 위해 고민하다보면 시간이 너무 많이 지나있더라고요.

물론 선생님의 해설은 훌륭해서 잘 이해가고, 해당 방법으로 풀면 풀린다는 것도 잘 알아요.

하지만 그건 제가 푼 게 아니라 선생님이 푼건데, 그저 이해하고 따라하기만 하면 낯선 아이디어를 떠올려야할 때 스스로 생각하는 힘이 부족한 느낌이 들더라고요. 그래서 계속 어떻게든 제 방법의 문제점을 찾아내고 해결하려고 붙잡게 되네요. 방법의 시작 자체가 잘못된 걸수도 있는데, 그렇다면 무엇이 잘못되었는지 파악하려고 하고요. (물론 잘 안돼요. 시간만 버리는 것 같습니다.)

실력도 별로 느는 것 같지 않아요. 연습 시간은 너무 많이 걸리고요. 코드도 너무 못 짜는 것 같아요.

제 방식이나 생각이 잘못된건가요?

안녕하세요, 인프런 AI 인턴입니다.

K케이님께서 겪고 계신 문제는 많은 개발자들이 코딩 테스트나 알고리즘 문제를 풀면서 직면하는 어려움입니다. 특히 시간 초과 문제는 코드의 효율성과 관련이 깊고, 복잡한 문제에서는 최적화를 더 필요로 할 수 있습니다.

문제 해결 방향 및 최적화:
- 시간 초과: 반복문이나 재귀 호출이 과도하게 많이 발생하는 부분을 찾아서 개선이 가능할지 살펴봐야 합니다.
- 조건문 최적화: 불필요한 조건문이나 이미 확인한 조건을 다시 검사하는 것은 없는지 확인해 보세요.
- 효율적인 데이터 구조: 큐, 스택, 힙 등의 자료 구조와 최적화된 알고리즘을 활용함으로써 시간 복잡도를 줄일 수 있습니다. 예를 들어 BFS 또는 DFS를 활용할 때, 방문 처리를 효율적으로 하여 불필요한 탐색을 줄이는 것이 중요합니다.
코딩 문제 접근법:
- 문제 해결 아이디어를 잡기 어려운 경우 강의에서 배운 내용을 기반으로 다른 사람들의 풀이를 참고해 작은 힌트라도 얻는 것이 좋습니다.
- 최적화 단계에서, 작성한 코드의 복잡한 요소들을 하나씩 뜯어보고 더 나은 방법이 없는지 고민해보세요.
- 디버깅과 테스트: 시간 초과나 메모리 초과 문제는 보통 특정한 입력에서 발생하므로, 다양한 케이스에서 테스트를 반복하며 문제가 되는 부분을 찾아 수정합니다.
코딩 연습과 성장 방법:
- 너무 많은 시간을 한 문제에 소비하게 되면 지치게 되고 학습 효율성이 떨어질 수 있습니다. 일정 시간을 정해두고 그것을 초과하면 새로운 방법을 배우거나 힌트를 참고해보는 것도 좋은 방법입니다.
- 문제 해결에 있어서 본인의 방법과 강사의 방법을 비교해보며 장단점을 분석해보세요.
- 꾸준한 연습과 피드백을 통해 점차적으로 실력을 쌓을 수 있으며, 이는 자연스레 새로운 아이디어를 떠올리는 힘을 길러줄 것입니다.

기존 답변은 다음 링크에서 시간을 줄이기 위한 최적화 전략에 대한 설명을 확인할 수 있습니다:

“3 - k 시간초과 문제”에서는 다소 복잡한 문제 상황에서 효율적인 코딩을 통해 시간 초과를 방지하는 여러 방법을 설명하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변