본문으로 건너뛰기
장원급제

자료구조와 정렬

스택·큐에 직접 넣고 꺼내 보고, 우리가 쓰는 식(중위식)을 연산자를 뒤에 쓰는 식(후위식)으로 바꾸고, 트리를 순서대로 돌아보고, 정렬이 회전마다 배열을 어떻게 바꾸는지 한 단계씩 확인해요.

한마디로스택은 나중에 넣은 것부터, 큐는 먼저 넣은 것부터 꺼내요.

3D 해설 영상

스택 = 접시 더미: 스택은 접시 더미예요. 맨 위(top)에서만 넣고 꺼내요(LIFO). 1·2·3을 쌓으면 3 다음에 1은 못 꺼내요.

스택은 접시 더미예요. 맨 위(top)에서만 넣고 꺼내요(LIFO). 1·2·3을 쌓으면 3 다음에 1은 못 꺼내요.

0:00 / 3:13

직접 해 보기

자료구조

쌓아 둔 접시를 맨 위부터 꺼내듯, 나중에 넣은 값이 먼저 나와요(LIFO). 넣기(push)와 꺼내기(pop)가 모두 맨 위(top) 한쪽에서만 일어나요.

pop·맨 위에서 3 꺼냈어요. 이제 맨 위 값: 2

top 위치(0부터 셈) = 1

꺼낸 순서: 3

연산 기록

  1. 1. push 1
  2. 2. push 2
  3. 3. push 3
  4. 4. pop → 3

스택으로 만들 수 있는 출력 순서

1, 2, 3…을 이 순서로만 넣을 수 있고, 넣는 사이사이 언제든 꺼낼 수 있어요. 원하는 출력 순서를 적으면 만들 수 있는지 알려 줘요. 만들 수 있으면 어떻게 넣고 꺼내는지도 보여 줘요.

값 개수

3 2 4 1: 만들 수 있어요.

  1. push 1 [1]
  2. push 2 [1 2]
  3. push 3 [1 2 3]
  4. pop 3 [1 2]
  5. pop 2 [1]
  6. push 4 [1 4]
  7. pop 4 [1]
  8. pop 1 []

대괄호는 그 연산 뒤 스택(바닥 → 위)이에요.

값 4개를 정해진 순서로 넣을 때 나올 수 있는 출력 순서는 24가지 중 14가지예요(카탈란 수: 3개 5가지, 4개 14가지, 5개 42가지).

탭을 골라 값을 바꿔 보세요. 스택·큐는 버튼으로 넣고 꺼내고, 수식은 식을 고치면 변환 과정이 다시 나오고, 트리는 값을 넣거나 노드를 눌러 지우며 순회를 재생하고, 정렬은 회전마다 배열이 표로 나와요. 정렬은 교재에서 흔히 쓰는 방식(퀵 정렬은 첫 원소 피벗)으로 계산하니, 문제에 다른 조건이 있으면 그 조건을 따르세요.

핵심 정리

스택은 나중 것부터, 큐는 먼저 것부터

접시를 쌓으면 맨 위 접시부터 꺼내고(스택), 번호표 줄은 먼저 온 사람부터 나가요(큐). 스택은 나중에 넣은 것이 먼저 나오는 LIFO 구조라 함수 호출의 복귀 주소, 후위식 계산, 괄호 검사, 되돌리기, 깊이 우선 탐색(DFS, 한 길을 끝까지 가 보는 탐색)에 써요. 큐는 먼저 넣은 것이 먼저 나오는 FIFO 구조라 너비 우선 탐색(BFS, 가까운 곳부터 넓혀 가는 탐색), 프린터 스풀(인쇄 대기열), 프로세스 준비 큐에 써요. 덱은 양쪽 끝에서 모두 넣고 꺼낼 수 있어요.

원형 큐: 배열 끝에서 0번 칸으로 다시 이어요

크기가 5인 배열 큐에서 앞의 값을 꺼내 앞칸이 비었어도, rear(넣는 쪽)가 배열 끝인 4번 칸에 닿으면 보통 큐는 더 넣지 못해요. 그래서 끝 다음을 0번 칸으로 잇는 원형 큐를 써요. front(꺼내는 쪽) = rear이면 빈 큐, (rear + 1) mod 크기(크기로 나눈 나머지) = front이면 가득 찬 큐예요. 둘을 구별하려고 한 칸은 늘 비워 둬요.

중위식을 후위식으로

우리가 쓰는 중위식 (A + B) * C를 후위식(연산자를 뒤에 쓰는 식)으로 바꾸면 A B + C *예요. 바꿀 때 피연산자는 바로 출력하고, 연산자는 스택 위에 우선순위가 같거나 높은 연산자를 먼저 꺼내 출력한 뒤 넣어요. 단, 오른쪽부터 묶는 거듭제곱(^)은 더 높은 것만 꺼내요. 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 여는 괄호까지 꺼내요. 후위식은 괄호 없이 왼쪽부터 스택 하나로 계산할 수 있고, 2026년 계리직에 나온 0-주소 명령어도 이렇게 스택에서 꺼내 계산해요.

이진 트리의 노드 수 공식

높이가 3인 포화 이진 트리에는 1 + 2 + 4 = 7개 노드가 들어가요. 루트를 레벨 1로 세면 레벨 i에는 노드가 최대 2^(i−1)개, 높이 h인 이진 트리에는 최대 2^h − 1개가 들어가요(포화 이진 트리). 노드가 하나라도 있는 이진 트리라면 단말 노드(자식이 없는 노드) 수 n₀ = 자식이 둘인 노드 수 n₂ + 1이고, 간선은 노드 수 − 1개예요. 완전 이진 트리는 마지막 레벨만 왼쪽부터 채운 트리라 배열에 빈칸 없이 담겨요.

트리 순회와 이진 탐색 트리

루트 50, 왼쪽 자식 30, 오른쪽 자식 70인 트리는 전위 50 30 70, 중위 30 50 70, 후위 30 70 50 순서로 방문해요. 전위는 루트 → 왼쪽 → 오른쪽, 중위는 왼쪽 → 루트 → 오른쪽, 후위는 왼쪽 → 오른쪽 → 루트예요. 이진 탐색 트리는 왼쪽에 작은 값, 오른쪽에 큰 값이 와서 중위 순회하면 오름차순이에요. 탐색은 평균 O(log n)이지만, 정렬된 순서로 넣어 한쪽으로 쏠리면 한 줄처럼 길어져 O(n)이 돼요.

정렬 알고리즘: 빠르기와 안정성

이미 정렬된 1 2 3 4 5를 삽입 정렬하면 값마다 바로 앞 값과 한 번씩, 모두 4번만 비교하고 끝나요. 버블·선택·삽입 정렬은 평균 O(n²)이지만, 삽입 정렬은 이렇게 이미 정렬된 입력에서 O(n)이에요. 퀵 정렬은 평균 O(n log n)으로 빠르지만 분할이 한쪽으로 쏠리면 O(n²)이고, 합병 정렬과 힙 정렬은 최악에도 O(n log n)이에요. 같은 값끼리 원래 순서를 지키는 안정 정렬은 버블·삽입·합병이고, 선택·퀵·힙은 불안정해요.

이렇게 외워요

  • 스택 출력, 안 되는 꼴

    큰 수 → 작은 수 → 중간 수(3 · 1 · 2 꼴)가 들어 있으면 불가능. 1·2·3을 넣으면 3 1 2만 안 돼요

  • 순회 이름 = 루트를 언제 적나

    전위는 루트 먼저 · 중위는 루트 가운데 · 후위는 루트 마지막. 왼쪽은 늘 오른쪽보다 먼저

  • 불안정 정렬

    선택 · 퀵 · 힙 · 셸은 멀리 떨어진 값을 한 번에 바꿔서 같은 값의 순서가 뒤집혀요. 버블 · 삽입 · 합병 · 기수는 안정

암기 카드

외운 카드 0 / 9

남은 카드 9장. ‘다시 볼래요’를 누르면 맨 뒤로 가요.

OX 퀴즈

0 / 8 풀었어요
  1. 1

    큐는 너비 우선 탐색(BFS)에 쓰인다.

  2. 2

    1, 2, 3을 차례로 넣는 스택에서 3, 1, 2 순서로 꺼낼 수 있다.

  3. 3

    후위식을 계산할 때 스택에서 먼저 꺼낸 값이 왼쪽 피연산자다.

  4. 4

    완전 이진 트리는 모두 포화 이진 트리다.

  5. 5

    이진 탐색 트리를 중위 순회하면 키가 오름차순으로 나온다.

  6. 6

    퀵 정렬의 최악 시간 복잡도는 O(n log n)이다.

  7. 7

    선택 정렬은 안정 정렬이다.

  8. 8

    삽입 정렬은 이미 정렬된 배열에서 비교를 n − 1번만 한다.

컴퓨터일반 자료 전체의 카드와 OX를 한 번에 풀려면 컴퓨터일반 카드·OX 모아 풀기로 가요.

근거

  • E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C (스택·큐, 트리, 정렬, 퀵 정렬의 분할 방식)
  • D. E. Knuth, The Art of Computer Programming, Vol. 1 (2.2.1 스택·큐·덱), Vol. 3 (Sorting and Searching)
  • C. A. R. Hoare, "Quicksort", The Computer Journal, 1962
  • J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM, 1964 · R. W. Floyd, "Algorithm 245: Treesort 3", 같은 학술지, 1964 (아래에서 위로 힙 만들기)
  • 2026년 계리직 컴퓨터일반 (명령어 형식: 0-주소 명령어와 스택)
  • 계리직 컴퓨터일반 출제 범위는 우정사업본부 공고 확인

학습을 돕는 자료예요. 법령과 제도는 바뀔 수 있으니 시험 직전에는 공식 자료로 다시 확인하세요.

컴퓨터일반 다른 개념

계리직 개념 전체 보기