인프런 커뮤니티 질문&답변
작성한 질문수
2-S 질문있습니다.
작성
·
85
·
수정됨
0
안녕하세요 큰돌님 강의 잘 보고 있습니다.
혼자 문제를 풀때 dfs와 dp를 섞어서 다음과 같이 풀었습니다.
http://boj.kr/1502bc54c9eb4d5ea406fd47713ab8e5
dp를 섞어 각 노드당 한번씩만 방문하게 하여 입력, 로직 수행, 출력 모두 합쳐도 최대 O(2n+m)이라는 생각이 드는데 시간 초과가 나옵니다. 혹시 제가 놓치고 있는 부분이 있을까요?
사이클을 고려하지 못해서 틀렸었네요! 감사합니다!
추가로 궁금한점이 있는데 큰돌님께서는 강의에서 시간복잡도가 보통 O(10,000,000) 까지는 괜찮다고 하셨던것이 기억납니다.
이때 만약 그래프가 1->2->3-> ... -> 10000 이렇게 되어 있는 상황에서 특정 노드마다 그래프 탐색을 수행하면 시간복잡도가 약 O(50,000,000)이 됩니다.
이는 시간 복잡도가 O(1000만)을 넘어감에도 불구하고 하나의 재귀 함수당 로직이 많지 않아서 괜찮은건가요? 아니면 일반적으로 시간복잡도가 O(1억) ≒ 1초 이고 C++은 다른 언어에 비해 실행속도가 빠르므로 시간초과가 나지 않는걸까요?