정처기 실기 순회·정렬 추적 문제, 연필로 푸는 게 정답입니다 (자료구조 빈출 정리)

안녕하세요, 공부하는 감자입니다 🥔

자료구조·알고리즘은 정처기 실기에서 1문제 정도 나오는 영역인데, 다른 암기 과목과 성격이 달라요. 외울 건 적은 대신 과정을 한 단계라도 건너뛰면 통째로 틀리는 구조입니다.

그래서 저는 이 영역만큼은 눈으로 읽지 않고 무조건 연필로 시뮬레이션하면서 공부했어요. 트리 순회, 정렬 한 단계, DFS/BFS 방문 순서 — 이 세 가지를 종이에 다섯 번씩만 따라 그려보면 시험장에서 흔들릴 일이 거의 없습니다.

트리 순회 — 루트가 어디에 오느냐

순회 문제는 이름 그대로 "루트의 위치"만 기억하면 됩니다. 루트를 먼저 찍으면 전위, 가운데 찍으면 중위, 마지막에 찍으면 후위예요.

        F
       / \
      B   G
     / \   \
    A   D   I

순회	규칙	결과
전위(Preorder)	루트 → 왼쪽 → 오른쪽	F B A D G I
중위(Inorder)	왼쪽 → 루트 → 오른쪽	A B D F G I
후위(Postorder)	왼쪽 → 오른쪽 → 루트	A D B I G F
레벨(Level)	위에서부터 층별로	F B G A D I

위 트리는 이진 탐색 트리(BST)이기도 한데, 중위 순회 결과가 오름차순으로 나온 게 보이시죠. "BST를 오름차순으로 출력하려면?" → 중위 순회가 단답 단골입니다.

스택과 큐 — 동작을 끝까지 따라가기

둘을 나란히 놓고 비교하면 이렇습니다.

구분	스택	큐
원칙	LIFO (후입선출)	FIFO (선입선출)
연산	push, pop, peek	enqueue, dequeue
응용	함수 호출, 괄호 검사, DFS	BFS, 대기열 처리

개념은 쉬운데 문제는 연산 나열형으로 나와요. 예를 들어 push 5, push 8, pop, push 2, push 7, pop을 따라가 보면,

1. push 5 → [5]
2. push 8 → [5, 8]
3. pop → [5] (8 반환)
4. push 2 → [5, 2]
5. push 7 → [5, 2, 7]
6. pop → [5, 2] (7 반환)

최종 스택은 [5, 2], pop된 값의 순서는 8, 7입니다. 큐도 같은 방식으로 풀면 돼요.

enqueue 4, 5, 6 → dequeue → enqueue 7 → dequeue라면 4, 5가 차례로 빠져나가고 [6, 7]이 남습니다.

DFS와 BFS — 자료구조부터 다릅니다

DFS는 스택(또는 재귀), BFS는 큐. "BFS의 자료구조는?"에 스택이라고 쓰는 게 가장 흔한 오답이에요.

간선이 1-2, 1-3, 2-4, 2-5, 3-6이고 1에서 시작해 번호 작은 순으로 방문한다고 하면,

• DFS: 한 갈래를 끝까지 파고듭니다 → 1, 2, 4, 5, 3, 6
• BFS: 가까운 노드부터 층층이 → 1, 2, 3, 4, 5, 6

DFS는 경로 존재 여부·백트래킹에, BFS는 가중치가 같을 때 최단 경로에 쓰인다는 용도 구분도 같이 외워두세요.

정렬 — 복잡도 표와 한 단계 추적

복잡도 표부터 보겠습니다.

알고리즘	평균	최악	안정 정렬
버블	O(n²)	O(n²)	O
선택	O(n²)	O(n²)	X
삽입	O(n²)	O(n²)	O
병합	O(n log n)	O(n log n)	O
퀵	O(n log n)	O(n²)	X
힙	O(n log n)	O(n log n)	X

여기서 두 가지가 시험 포인트예요. 하나는 퀵 정렬의 최악은 O(n²)라는 것(이미 정렬된 배열에서 극단값을 피벗으로 고를 때).

다른 하나는 안정 정렬은 같은 값의 원래 순서를 보존하는 정렬이라는 정의입니다.

서술형으로는 "단계별 결과를 쓰시오"가 나옵니다. [4, 1, 5, 2, 3]을 삽입 정렬로 오름차순 정렬하면,

1. 1을 앞으로 → [1, 4] 5 2 3
2. 5는 제자리 → [1, 4, 5] 2 3
3. 2를 4 앞으로 → [1, 2, 4, 5] 3
4. 3을 4 앞으로 → [1, 2, 3, 4, 5]

이런 추적 문제는 결국 양치기인데, 기출 외에 연습 문제가 더 필요하면 문어CBT 무료 모의고사에서 비슷한 유형을 골라 풀 수 있어서 저는 그걸로 채웠어요.

SQLD·정처기·컴활·ADsP 무료 CBT 모의고사

해시와 Big-O는 단답으로 마무리

해시는 서로 다른 키가 같은 인덱스로 떨어지는 충돌(Collision)과 그 해결책 두 가지만 알면 됩니다.

• 체이닝 — 같은 인덱스에 연결 리스트로 이어 붙이기
• 개방 주소법 — 다른 빈 슬롯을 찾아가기

충돌이 심해지면 탐색이 O(n)까지 떨어진다는 것도 같이요.

시간 복잡도는 빠른 순서의 위계만 머리에 넣어두세요.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

이진 탐색이 O(log n)인데, 전제 조건이 배열이 정렬되어 있어야 한다는 점까지 묶어서 묻는 경우가 많습니다. Big-O를 물을 때 기준은 최악이라서, "퀵 정렬의 최악 시간 복잡도는?"의 답은 O(n log n)이 아니라 O(n²)라는 것도 잊지 마세요.

시험 전에 마지막으로 점검할 건 세 줄입니다.

후위 순회는 루트가 맨 뒤, BFS는 큐, 퀵 정렬 최악은 O(n²).

이 세 개에서 의외로 많이들 틀려요.