해설 보기
정답총 연산 횟수가 300n + 60000이므로 시간 복잡도는 O(n)입니다.
핵심 개념
이중 반복문의 시간 복잡도 — 상수는 모두 버립니다
빅오(Big-O) 표기는 입력 크기 n이 커질 때의 증가율만 따지므로, 덧셈으로 붙은 상수항과 곱셈으로 붙은 상수배는 모두 무시합니다. 이 코드에서 바깥 for문은 i가 0부터 n+199까지 돌아 총 n+200회 반복하고, 안쪽 for문은 j가 0부터 299까지 도는 고정된 300회 반복입니다. 즉 printf의 총 실행 횟수는 300 × (n+200) = 300n + 60000회입니다. 여기서 계수 300과 상수 60000을 버리면 남는 것은 n뿐이므로 시간 복잡도는 O(n)입니다. 안쪽 루프가 있다고 무조건 O(n²)로 보면 안 되고, 반복 횟수가 n에 의존하는지를 반드시 확인해야 합니다.
선지별 해설
①안쪽 루프는 n과 무관한 300회 고정이므로 전체 반복은 300(n+200)회이고, 상수 계수와 상수항을 제거하면 O(n)이 됩니다.
②O(n²)이 되려면 안쪽 루프의 반복 횟수도 n에 비례해야 합니다. 여기서는 j < 300으로 고정이므로 제곱이 되지 않습니다.
③O(log₂n)은 매 단계마다 문제 크기가 절반으로 줄어드는 이분 탐색류에서 나옵니다. 이 코드는 i가 1씩 증가하므로 로그가 될 수 없습니다.
④O(nlog₂n)은 병합 정렬처럼 n개 원소를 log n 단계에 걸쳐 처리할 때 나옵니다. 이 코드에는 로그에 해당하는 구조 자체가 없습니다.
해설 보기
정답방문 순서가 B → E → A → C → I이므로 정점 I는 5번째입니다.
핵심 개념
깊이 우선 탐색(DFS)의 방문 순서 추적
DFS는 갈 수 있는 곳까지 최대한 깊이 내려간 뒤, 더 갈 곳이 없으면 되돌아와서(백트래킹) 남은 인접 정점을 탐색하는 방식입니다. 이런 추적 문제는 먼저 인접 리스트를 정리하고 조건대로 알파벳 오름차순으로 후보를 고르는 것이 정확합니다. 그래프의 인접 관계는 A-E, B-E, B-F, B-G, C-E, C-I, D-F, D-H, E-I, F-G입니다. 시작 정점 B(1번째)에서 인접 정점 E, F, G 중 알파벳이 앞선 E로 갑니다(2번째). E의 인접 정점 A, B, C, I 중 A로 가고(3번째), A는 E밖에 없으므로 되돌아와 C로 갑니다(4번째). C의 인접 정점 E는 이미 방문했으므로 I로 가서(5번째) 정점 I는 다섯 번째로 방문됩니다.