정보처리기사 자료구조 영역 2회차에서는 트리 순회, 그래프 탐색 알고리즘, 힙(Heap), 인접 행렬 표현 등 심화 개념을 다룹니다. 1회차에서 익힌 스택·큐의 기본 원리를 바탕으로, 실전 시험에 자주 출제되는 응용 문제를 중심으로 구성하였습니다.
본 회차 안내
2과목 소프트웨어개발 – 자료구조 (스택/큐/트리/그래프) (2/2회차)
문제 1. 이진 트리 후위 순회(Post-order)
다음과 같은 이진 트리가 있다. 루트는 A이고, A의 왼쪽 자식은 B, 오른쪽 자식은 C이다. B의 왼쪽 자식은 D, 오른쪽 자식은 E이며, C의 오른쪽 자식은 F이다. 이 트리를 후위 순회(Post-order)한 결과로 올바른 것은?
- A – B – D – E – C – F
- D – B – E – A – C – F
- D – E – B – F – C – A
- D – E – F – B – C – A
정답
③ D – E – B – F – C – A
해설
후위 순회는 왼쪽 → 오른쪽 → 루트 순서로 노드를 방문합니다. B의 서브트리를 먼저 처리하면 D → E → B 순서가 됩니다. C의 서브트리는 왼쪽 자식이 없으므로 F → C 순서가 되고, 마지막으로 루트 A를 방문합니다.
오답: ① 전위 순회(Pre-order: 루트→왼→오) 방식에 가까운 방문 순서로 후위 순회가 아닙니다.
오답: ② 중위 순회(In-order: 왼→루트→오)에 해당하며, C의 오른쪽 자식 F 처리가 잘못되었습니다.
정답: ③ 후위 순회 규칙(왼→오→루트)을 정확히 적용한 결과로 올바릅니다.
오답: ④ C에 왼쪽 자식이 없으므로 B 앞에 F가 올 수 없어 순서가 틀립니다.
문제 2. 그래프 BFS 탐색 순서
다음 무방향 그래프에서 정점 1번부터 BFS(너비 우선 탐색)를 시작할 때 탐색 순서로 올바른 것은? 인접 정점은 번호가 작은 것부터 방문한다고 가정한다. 간선 목록: 1-2, 1-3, 2-4, 2-5, 3-6
- 1 – 2 – 4 – 5 – 3 – 6
- 1 – 2 – 3 – 4 – 5 – 6
- 1 – 3 – 6 – 2 – 4 – 5
- 1 – 2 – 3 – 6 – 4 – 5
정답
② 1 – 2 – 3 – 4 – 5 – 6
해설
BFS는 큐(Queue)를 사용하여 현재 정점과 인접한 모든 정점을 먼저 방문합니다. 1번에서 시작하면 인접한 2, 3을 큐에 넣습니다. 2를 꺼내며 4, 5를 큐에 추가하고, 3을 꺼내며 6을 추가합니다. 따라서 방문 순서는 1 → 2 → 3 → 4 → 5 → 6입니다.
오답: ① 2의 자식(4, 5)을 3보다 먼저 모두 방문하는 DFS식 순서로, BFS 원칙에 어긋납니다.
정답: ② 같은 깊이의 정점을 번호 순서대로 모두 방문하는 올바른 BFS 결과입니다.
오답: ③ 1의 인접 정점 중 3을 2보다 먼저 방문하고 있어 번호 오름차순 규칙에 위배됩니다.
오답: ④ 3의 자식 6을 2의 자식 4, 5보다 먼저 방문하고 있어 큐의 FIFO 원칙에 어긋납니다.
문제 3. 최대 힙(Max-Heap) 삽입
현재 최대 힙(Max-Heap)에 저장된 값이 [50, 30, 40, 10, 20] 순서(배열 인덱스 1부터)로 구성되어 있다. 여기에 새로운 값 45를 삽입한 직후 힙 배열의 루트 값과 전체 배열 상태로 올바른 것은?
- 루트: 50, 배열: [50, 30, 45, 10, 20, 40]
- 루트: 50, 배열: [50, 30, 40, 10, 20, 45]
- 루트: 50, 배열: [50, 45, 40, 10, 20, 30]
- 루트: 45, 배열: [45, 30, 50, 10, 20, 40]
정답
① 루트: 50, 배열: [50, 30, 45, 10, 20, 40]
해설
최대 힙에 값을 삽입할 때는 배열의 마지막 위치에 추가한 뒤 부모 노드와 비교하며 위로 올리는 업힙(Up-Heap) 연산을 수행합니다. 45를 인덱스 6에 삽입하면 부모는 인덱스 3의 값 40입니다. 45 > 40이므로 두 값을 교환하면 배열은 [50, 30, 45, 10, 20, 40]이 됩니다. 45의 새 부모는 루트 50이고 45 < 50이므로 업힙이 종료됩니다.
정답: ① 업힙 연산을 한 번 수행하여 인덱스 3과 6을 교환한 올바른 결과입니다.
오답: ② 삽입 후 업힙 연산을 전혀 수행하지 않아 최대 힙 속성이 위배됩니다.
오답: ③ 업힙 연산 결과를 잘못 적용하여 인덱스 2(값 30)와 교환한 오류로, 실제 부모 방향이 아닙니다.
오답: ④ 루트가 45로 변경되었는데, 50이 여전히 힙에 존재하므로 최대 힙 조건(루트가 최대)에 위배됩니다.
문제 4. 그래프 인접 행렬 표현
정점이 4개(V = {1, 2, 3, 4})인 방향 그래프(Directed Graph)의 간선이 다음과 같다: 1→2, 1→3, 2→4, 3→4. 이 그래프를 인접 행렬로 표현할 때, 행렬의 2행(정점 2에서 출발하는 행)에 해당하는 값으로 올바른 것은? (행·열 순서는 정점 1, 2, 3, 4 순이며, 간선이 있으면 1, 없으면 0으로 표기)
- [ 1, 0, 1, 0 ]
- [ 0, 0, 0, 1 ]
- [ 1, 0, 0, 1 ]
- [ 0, 1, 0, 0 ]
정답
② [ 0, 0, 0, 1 ]
해설
방향 그래프의 인접 행렬에서 행(i)은 출발 정점, 열(j)은 도착 정점을 나타냅니다. 정점 2에서 출발하는 간선은 2→4 하나뿐입니다. 따라서 2행은 정점 1, 2, 3 방향으로는 0이고, 정점 4 방향으로만 1이 됩니다.
오답: ① 1→2, 1→3을 정점 2의 행으로 잘못 읽은 결과로, 1행에 해당하는 값입니다.
정답: ② 정점 2에서 출발하는 간선이 2→4 하나뿐임을 올바르게 반영한 값입니다.
오답: ③ 정점 1과 4 방향에 1이 표시되어 있어, 존재하지 않는 2→1 간선을 포함한 오류입니다.
오답: ④ 정점 2 자기 자신으로 향하는 자가 루프(2→2)가 표시되어 있어 주어진 간선 목록과 다릅니다.
문제 5. AVL 트리와 균형 인수(Balance Factor)
AVL 트리에서 균형 인수(Balance Factor)는 특정 노드의 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값으로 정의한다. AVL 트리가 균형 상태를 유지하기 위한 균형 인수의 허용 범위로 올바른 것은?
- 균형 인수가 항상 0이어야 한다.
- 균형 인수가 -1, 0, 1 중 하나여야 한다.
- 균형 인수가 -2 이상 2 이하여야 한다.
- 균형 인수는 음수가 될 수 없다.
정답
② 균형 인수가 -1, 0, 1 중 하나여야 한다.
해설
AVL 트리는 자가 균형 이진 탐색 트리로, 모든 노드의 균형 인수가 반드시 -1, 0, 1 세 값 중 하나를 유지해야 합니다. 균형 인수의 절댓값이 2 이상이 되는 순간 회전(Rotation) 연산을 수행하여 트리의 균형을 복원합니다. 이 속성 덕분에 AVL 트리의 탐색·삽입·삭제 연산은 O(log n) 시간 복잡도를 보장합니다.
오답: ① 균형 인수가 항상 0이면 완전 균형 트리를 의미하며, 이는 AVL 트리보다 훨씬 엄격한 조건으로 실용적이지 않습니다.
정답: ② AVL 트리의 정의상 허용되는 균형 인수 범위가 정확하게 서술되어 있습니다.
오답: ③ 균형 인수 절댓값이 2인 상태는 이미 불균형으로 회전이 필요한 상태이므로 허용 범위에 포함되지 않습니다.
오답: ④ 오른쪽 서브트리가 왼쪽보다 높을 때 균형 인수는 음수가 되므로, 음수를 허용하지 않는다는 설명은 틀렸습니다.
학습 정리
이번 회차에서는 트리 후위 순회, BFS 탐색 순서, 최대 힙 삽입, 인접 행렬 표현, AVL 트리 균형 인수라는 다섯 가지 핵심 개념을 집중적으로 살펴보았습니다. 특히 순회 순서와 그래프 탐색 방식은 정보처리기사 자료구조 문제에서 반복 출제되는 단골 유형입니다. 각 개념의 원리를 손으로 직접 따라가며 연습하면 실전 시험에서 실수를 크게 줄일 수 있습니다.