이 편의 문항은 실제 독학사 기출 문제를 그대로 옮긴 것이 아닙니다. 국가평생교육진흥원이 공개한 4단계 알고리즘 과목 출제기준(평가영역)과 공개·복원된 기출의 유형 분포를 바탕으로, 동일한 출제 의도를 갖도록 새로 재구성한 예상·유사 문항입니다. 실제 시험의 문항 수·배점·시간은 매 회차 공고를 통해 반드시 다시 확인하세요.
아래 11개 문항 중 그래프 순회·탐색(1~5번)은 다음 무방향 그래프를 공통으로 사용합니다.
- 정점: A, B, C, D, E, F
- 간선: A–B, A–C, B–D, B–E, C–F, E–F
인접 리스트를 알파벳 오름차순으로 저장했다고 가정합니다(즉 A의 인접 리스트는 B, C 순서).
문제 14지선다
위 그래프 표현 방식에 대한 설명으로 옳지 않은 것은?
문제 24지선다
위 그래프에서 정점 A를 시작점으로 깊이 우선 탐색(DFS)을 수행하되, 각 정점에서 인접 리스트에 저장된 순서(알파벳 오름차순)대로 방문한다고 할 때, 방문 순서로 옳은 것은?
문제 34지선다
같은 그래프에서 정점 A를 시작점으로 너비 우선 탐색(BFS)을 수행할 때(인접 리스트 순서대로 큐에 삽입), 방문 순서로 옳은 것은?
문제 44지선다
정점 수를 V, 간선 수를 E라 할 때 DFS와 BFS의 시간 복잡도에 대한 설명으로 옳은 것은? (인접 리스트로 표현했다고 가정)
문제 54지선다
다음 중 그래프의 연결 요소(connected component) 개수를 구하는 방법으로 옳은 것은?
다음 3문항(6~8)은 위상 정렬 문제입니다. 다음 방향 비순환 그래프(DAG)를 사용합니다.
- 정점: 1, 2, 3, 4, 5, 6
- 간선(방향): 1→2, 1→3, 2→4, 3→4, 4→5, 3→6, 5→6
문제 64지선다
위상 정렬(topological sort)에 대한 설명으로 옳지 않은 것은?
문제 74지선다
Kahn 알고리즘(진입 차수 기반 위상 정렬)으로 위 DAG를 처리한다고 하자. 먼저 각 정점의 진입 차수를 구하면 1은 0, 2는 1, 3은 1, 4는 2, 5는 1, 6은 2이다. 진입 차수가 0인 정점을 큐에 넣고, 정점을 꺼낼 때마다 그 정점에서 나가는 간선을 제거하며 진입 차수가 0이 되는 정점을 새로 큐에 넣는 방식으로 진행할 때, 나올 수 있는 위상 정렬 결과로 옳은 것은?
문제 84지선다
Kahn 알고리즘을 수행하는 도중, 모든 간선을 다 제거했는데도 큐가 비어 아직 방문하지 못한 정점이 남아 있다면 이는 무엇을 의미하는가?
다음 5문항(9~13)은 최소 신장 트리(MST) 문제입니다. 다음 무방향 가중치 그래프를 사용합니다.
- 정점: A, B, C, D, E
- 간선(가중치): A–C(1), B–C(2), D–E(2), A–B(4), B–D(5), B–E(6), C–D(8), C–E(10)
문제 94지선다
최소 신장 트리(MST)의 성질에 대한 설명으로 옳지 않은 것은?
문제 104지선다
위 그래프에서 크루스칼(Kruskal) 알고리즘을 수행한다고 하자. 간선을 가중치 오름차순으로 정렬하면 A–C(1), B–C(2), D–E(2), A–B(4), B–D(5), B–E(6), C–D(8), C–E(10) 순서다. 사이클을 만들지 않는 간선만 골라 트리를 완성할 때, 선택되는 간선 집합과 총 가중치로 옳은 것은?
문제 114지선다
크루스칼 알고리즘에서 어떤 간선의 두 끝점이 이미 같은 그룹(집합)에 속해 있는지, 즉 그 간선을 추가하면 사이클이 생기는지를 판정할 때 표준적으로 사용하는 자료구조는?
문제 124지선다
같은 그래프에서 프림(Prim) 알고리즘을 정점 A에서 시작해 수행한다고 하자. 매 단계마다 현재 트리에 포함된 정점들과 연결된 간선 중 가중치가 가장 작은 것을 고른다고 할 때, 간선이 선택되는 순서로 옳은 것은?
문제 134지선다
프림 알고리즘과 크루스칼 알고리즘의 선택 기준으로 옳은 것은?
다음 4문항(14~17)은 최단경로 알고리즘 문제입니다. 다음 방향 가중치 그래프에서 정점 S를 출발점으로 합니다.
- 정점: S, A, B, C, D
- 간선(방향, 가중치): S→A(4), S→B(2), B→A(1), B→C(8), B→D(10), A→C(5), C→D(2)
문제 144지선다
다익스트라(Dijkstra) 알고리즘을 위 그래프에 정점 S에서 적용한다고 하자. 알고리즘을 진행하는 각 단계에서 아직 확정되지 않은 정점 중 현재까지의 최단 거리 추정값이 가장 작은 정점을 확정(처리)하고, 그 정점을 거쳐 갈 수 있는 인접 정점의 거리를 갱신한다. 이 과정을 반복했을 때 S에서 각 정점까지의 최종 최단 거리로 옳은 것은?
문제 154지선다
다익스트라 알고리즘이 요구하는 전제 조건과, 이를 어겼을 때 생기는 문제로 옳은 것은?
문제 164지선다
위와 같은 방향 그래프에서 S→A 간선의 가중치가 4가 아니라 -3(음수)이라고 바꿔 생각해보자. 다익스트라 알고리즘을 그대로 적용하면 어떤 문제가 발생하는가?
문제 174지선다
벨만-포드(Bellman-Ford) 알고리즘에 대한 설명으로 옳지 않은 것은?
다음 4문항(18~21)은 벨만-포드와 플로이드-워셜의 트레이싱 문제입니다. 벨만-포드는 다음 방향 그래프를 사용합니다.
- 정점: S, A, B, C
- 간선(방향, 가중치): S→A(4), S→B(5), A→B(-2), A→C(3), B→C(4)
문제 184지선다
벨만-포드 알고리즘을 정점 S에서 시작해 위 그래프에 적용한다. 간선을 S→A, S→B, A→B, A→C, B→C 순서로 완화한다고 할 때, 1회차 반복(모든 간선을 한 번씩 검사)이 끝난 직후 각 정점의 거리값으로 옳은 것은?
문제 194지선다
위 1회차 결과(S=0, A=4, B=2, C=6)에 대해 2회차 반복을 같은 순서로 다시 진행하면 어떤 일이 일어나는가?
문제 204지선다
위 그래프에 간선 C→A(-10)을 추가로 넣는다고 하자. 이렇게 하면 A→B(-2), B→C(4), C→A(-10)로 이어지는 사이클의 총 가중치는 -2 + 4 + (-10) = -8로 음수가 된다. 이 상태에서 벨만-포드 알고리즘을 V - 1 = 3회 반복한 뒤 4번째(V번째) 완화를 한 번 더 시도하면 어떤 일이 일어나는가?
다음 2문항(21~22)은 플로이드-워셜(Floyd-Warshall) 알고리즘 문제입니다. 다음 방향 그래프의 직접 연결된 거리(연결이 없으면 무한대)를 사용합니다.
- 정점: A, B, C, D
- A→B(5), A→D(10), B→C(3), C→D(1) (그 외 직접 간선 없음)
문제 214지선다
플로이드-워셜 알고리즘에 대한 설명으로 옳은 것은?
문제 224지선다
위 그래프에 플로이드-워셜을 적용한다고 하자. 초기 dist 값은 A→B=5, A→D=10, B→C=3, C→D=1이고 그 외는 무한대다(자기 자신은 0). 경유지 k를 A, B, C, D 순서로 검토할 때, k=B와 k=C 단계에서 새로 갱신되는 값으로 옳은 것은?
참고 자료
Last updated on