해설 보기
정답15개 — 6C2 = 6 × 5 / 2 = 15입니다.
핵심 개념
무방향 완전 그래프의 간선 개수
완전 그래프(complete graph)는 서로 다른 모든 정점 쌍이 정확히 하나의 간선으로 연결된 그래프입니다. 무방향 그래프에서는 (u, v)와 (v, u)가 같은 간선으로 취급되므로, 정점이 n개일 때 간선 수는 서로 다른 두 정점을 고르는 조합의 수인 nC2 = n(n-1)/2가 됩니다. 만약 방향 그래프였다면 양방향을 따로 세어 n(n-1)개가 된다는 점도 함께 기억해 두시면 좋습니다. 이 문항은 n = 6을 대입해 6 × 5 / 2 = 15를 구하면 되는 기본 계산 문제입니다.
선지별 해설
①6은 정점의 개수와 같은 값이며, 정점 6개를 하나의 사이클로만 연결했을 때의 간선 수입니다. 완전 그래프는 모든 정점 쌍을 빠짐없이 연결해야 하므로 이보다 훨씬 많습니다.
②12는 n(n-1)/2가 아니라 2n으로 잘못 계산한 값입니다. 올바른 식에 대입하면 6 × 5 / 2 = 15이므로 12는 답이 될 수 없습니다.
③6C2 = 6 × 5 / 2 = 15로, 정점이 6개인 무방향 완전 그래프의 간선 수와 정확히 일치하므로 이 선지가 정답입니다.
④21은 7 × 6 / 2의 값으로 정점이 7개일 때의 간선 수입니다. 자기 자신을 잇는 루프까지 포함해 n(n+1)/2로 계산한 경우에도 나오는 값이라 틀렸습니다.
해설 보기
정답(가) (2, 5), (나) (2, 5, 7), (다) (5, 7)
핵심 개념
큐(Queue)의 FIFO 동작 추적
큐는 먼저 들어온 원소가 먼저 나가는 FIFO(First In First Out) 자료구조입니다. enqueue는 뒤쪽(rear)에 원소를 넣고, dequeue는 앞쪽(front)의 원소를 꺼내며, 빈 큐에 dequeue를 하면 이 문제처럼 오류를 출력합니다. 스택의 LIFO와 헷갈리지 않는 것이 핵심입니다. 4번 연산까지 진행하면 큐는 (1, 2, 5) 상태이고 표기에서 가장 왼쪽이 front입니다. 이후 dequeue → enqueue(7) → dequeue를 차례로 적용한 결과를 추적하면 됩니다.