질문드립니다.
86
작성한 질문수 2
2-S 백준1325 효율적인 해킹 문제에서
시간복잡도가 10억인데,
시간복잡도가 10억이어도 괜찮나요?
답변 2
0
안녕하세요 ㅎㅎ
10억이면 거의 안되지만 될 때도 있습니다.
개념 교안내의 다음 부분 참고부탁드립니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 코딩하는사람님께서 궁금해하시는 백준 1325 효율적인 해킹 문제의 시간복잡도에 대한 질문에 대해 답변드리겠습니다.
백준 1325 효율적인 해킹 문제를 해결하려면, DFS나 BFS를 사용하여 각 노드에서 도달 가능한 모든 노드를 방문해야 하는데, 이 과정에서 시간복잡도가 O(N * M) 형태가 됩니다. 여기서 N은 정점의 수, M은 간선의 수를 의미합니다. 최대 시간복잡도는 문제에서 입력 범위 상 한계까지 접근할 수 있기 때문에 이론상 10억에 이를 수 있습니다.
하지만 실제 온라인 저지 환경에서는 입력 데이터의 특성과 최적화된 알고리즘에 따라 10억의 복잡도를 가진 알고리즘도 동작할 수 있습니다. 이는 테스트 케이스에 따라 최적화된 연산과 초기화 과정이 발생함으로써 가능해집니다. 보통은 1억 이내의 연산을 기준으로 생각하지만, 일부 문제는 이렇게 높은 복잡도에서도 성공할 수 있도록 설정된 경우라고 할 수 있습니다.
이 문제는 강의에서 사용한 알고리즘 외에도 SCC(Strongly Connected Components)를 활용한 해법으로 접근할 수 있으며, 이 방법이 시간복잡도를 줄이는 데 도움이 되기도 합니다.
유사한 질문이 있는 게시물들을 소개드리니 참고 부탁드립니다:
- 2-S (1325번 - 효율적인 해킹) 문제 질문 드립니다.: 해당 문제에 관련된 다양한 접근 방법과 최적화 팁을 확인할 수 있습니다.
- 2-S 질문있습니다.: 시간복잡도에 대한 상세한 설명과 문제 접근 방법에 대한 인사이트를 제공하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
진행 방법 질문드립니다!
0
26
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
54
2
2주차 개념#12 트리 순회
0
25
2
백준사이트가 종료된다고 합니다.
0
284
2
백준 서비스 종료
9
881
1
sk 하이닉스 코테 대비
0
367
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
83
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
169
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
73
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
91
2
5-Q 질문
0
64
2