기본 자료구조 및 알고리즘

1과목의 설계도를 코드로 옮기는 2과목의 첫 강. 자료구조 = 데이터를 효율적으로 담고 빠르게 꺼내기 위한 그릇과 규칙. 매 회차 데이터 입출력 영역에서 약 3문항 출제되며, 트리 운행법(전중후) 과 스택/큐 매칭(접줄) 이 단연 1순위.

핵심 암기: 대분류 선비 · 시간복잡도 Big-O 빅쓰리 · 연결 리스트 3종 단이원 · 스택/큐 접줄 · 트리 운행법 전중후

자료구조 기초

자료구조와 대분류 ·선비·분류·

[정의] 데이터를 효율적으로 저장하고 빠르게 꺼내 쓰기 위한 그릇의 모양과 규칙. 같은 데이터라도 어떤 그릇에 담느냐에 따라 꺼내는 속도가 크게 달라진다.

[분류] 데이터를 어떻게 연결하느냐에 따라 두 부류로 나뉜다.

🔑 암기 선비 — 선형 / 비선형, "자료구조 세계의 양반은 두 분" 💡 비유 선형 = 마트 계산대 줄(한 줄) / 비선형 = 가족 가계도·지하철 노선도(갈래) ⚠️ 함정 '트리는 선형이다' '큐는 비선형이다' = 100% 함정. 트리=비선형, 큐=선형. 분류 문제는 양방향 함정으로 단골. 🎯 빈출 분류·소거형이 거의 매회. 선비 한 단어가 양쪽 함정을 즉답 무력화.

시간복잡도 Big-O ·빅쓰리·복잡도·

[정의] 입력 크기 n이 커질 때 처리 시간이 늘어나는 정도. 자료구조마다 꺼내는 속도를 비교하는 단위. 시험은 빈출 3개만 묻는다.

[표] 오늘 다룰 선형 4종의 대표 속도.

🔑 암기 Big-O 빅쓰리 — O(1) 즉답 · O(log n) 반토막 · O(n) 한 바퀴 💡 한 줄 배열은 접근이 빠르고(O(1)), 연결 리스트는 삽입·삭제가 빠르다(O(1)). 정반대 짝. 🌟 정렬·이분 탐색·해시의 복잡도 분석은 11강 범위. 오늘은 빅쓰리 3개만.

선형 자료구조

배열 (Array) ·선형·

[정의] 같은 자료형의 데이터를 연속된 메모리 공간에 일렬로 저장하고, 인덱스(번호) 로 즉시 접근하는 자료구조.

[표]

💡 비유 영화관 좌석 — C열 7번은 거리에 상관없이 바로 찾아감(O(1)). 단 중간 손님이 빠지면 뒷자리가 한 칸씩 당겨 앉아야 함(O(n)). 🎯 빈출 결정 키워드 = 연속 메모리 + 인덱스 O(1) 접근. 보기에 '임의 접근(Random Access)'이 보이면 거의 배열.

연결 리스트 (Linked List) ·선형·O(n) 함정·

[정의] 데이터(값)와 다음 노드의 주소(포인터) 를 한 묶음(노드)으로 만들어 체인처럼 연결한 자료구조. 마지막 노드는 NULL을 가리킨다.

┌──────┬──────┐    ┌──────┬──────┐    ┌──────┬──────┐
│ Data │ Next │ →  │ Data │ Next │ →  │ Data │ NULL │
└──────┴──────┘    └──────┴──────┘    └──────┴──────┘

[비교] 배열과 정반대 짝.

💡 비유 배열 = 번호표 사물함(5번 즉시) / 연결 리스트 = 다음 위치가 적힌 보물찾기 쪽지(1→2→3→4 거쳐야 5번). ⚠️ 함정 '연결 리스트는 인덱스로 O(1) 임의 접근 가능' = 100% 함정. 연결 리스트는 O(n) 순차 접근. O(1)은 배열. 🎯 빈출 결정 키워드 = 노드 + 포인터 + 동적 메모리 할당. 이 단어가 보이면 연결 리스트.

연결 리스트 3종 ·단이원·선형·

[분류] 포인터를 어떻게 두느냐에 따라 3종으로 나뉜다.

단순:  [A] → [B] → [C] → NULL
이중:  NULL ← [A] ↔ [B] ↔ [C] → NULL
원형:  [A] → [B] → [C] → (다시 A)

🔑 암기 단이원 — 단순 · 이중 · 원형, "단번에 이중 원샷" 💡 비유 단순 = 일방통행 / 이중 = 왕복 도로 / 원형 = 트랙(돌고 돌아 시작점) 🎯 빈출 종류 매칭 단골. '이중 = 양방향', '원형 = 끝→처음' 두 키워드를 함께.

스택 (Stack · LIFO) ·접줄·1순위·

[정의] 가장 나중에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO, Last In First Out) 구조. 입출구가 한 곳(top).

        │     │  ← top (입출구 1개)
        ├─────┤
        │  C  │  ← 마지막 입력, 첫 출력
        ├─────┤
        │  B  │
        ├─────┤
        │  A  │  ← 첫 입력, 마지막 출력
        └─────┘
   PUSH 순서: A → B → C   /   POP 순서: C → B → A (역순)

[표] 5연산.

⚠️ 함정 빈 스택에 pop = 언더플로(Underflow), 꽉 찬 스택에 push = 오버플로(Overflow). 이름 매칭 단골. 💡 실무 함수 호출·재귀(Recursion)·괄호 검사·실행 취소(Ctrl+Z)·후위 표기 변환·브라우저 뒤로가기가 모두 스택. 재귀 과다 호출 오류 이름이 곧 Stack Overflow. 🎯 빈출 보기에 '함수 호출·재귀·괄호 검사·Undo' 또는 '입출력 한 곳'이 보이면 스택. push·pop이 가장 잦다.

큐 (Queue · FIFO) ·접줄·1순위·

[정의] 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출(FIFO, First In First Out) 구조. 입구(rear)와 출구(front)가 분리된다.

  [출구] front →  A  B  C  D  ← rear [입구]
         dequeue(먼저 나감)    enqueue(나중 들어옴)

[표] 4연산. 스택의 push·pop과 1:1 대응(enqueue=push, dequeue=pop).

💡 비유 마트 계산대 줄 — 먼저 줄 선 사람이 먼저 나감(새치기 없음). 💡 실무 메시지 지향 미들웨어(MOM·메시지 큐), 작업 처리 대기열, 프린터 작업 큐, 예매 대기열이 모두 큐. 이름에 'Queue'가 들어간 미들웨어(메시지 큐 류)는 99% 큐 자료구조. 🎯 빈출 보기에 '선입선출·FIFO·프린터 큐·메시지 큐·작업 처리' 또는 '입출력 두 곳'이 보이면 큐.

원형 큐와 데크 ·변형·🌟·

[정의] 일반 선형 큐의 한계(앞이 비어도 rear가 끝에 닿으면 더 못 넣는 공간 낭비)를 보완한 변형 큐 2종.

🌟 자주 출제되진 않음. '원형 큐 = 끝↔처음 연결로 공간 재활용', '데크 = 양쪽 입출력' 한 줄씩만. 💡 보충 우선순위 큐(Priority Queue) 는 먼저 들어온 순이 아니라 우선순위 높은 것이 먼저 나가는 변형(힙 기반). 정의만 — 11강에서 본격.

스택 vs 큐 즉답 매칭 ·접줄·1순위·

[비교] 10강 핵심 1순위. 이 한 표가 기출 다지기의 정답 키.

🔑 암기 접줄 — 스택=접시 쌓기(LIFO·입출구 1개) / 큐=줄 서기(FIFO·입출구 2개) 🎯 빈출 매 회차 출제 1순위. 한 회차에 2문항까지 등장. '쌓아서 위에서 꺼냄' → 스택, '먼저 온 사람이 먼저' → 큐.

비선형 자료구조 — 트리

트리 개념과 용어 ·잎=단말·차수 함정·

[정의] 여러 노드가 계층(부모-자식) 관계로 연결된 비선형 자료구조. 사이클(순환)이 없는 그래프의 한 종류.

              [A]            ← 루트(Root)
             /   \
          [B]     [C]        ← A의 자식, 서로 형제
         /  \      \
       [D]  [E]    [F]       ← 잎(Leaf, 단말 노드)

[표] 용어 매칭이 시험 단골. 7개만 정확히.

⚠️ 함정 ① 노드 차수 vs 트리 차수 — 노드 차수 = 그 노드의 자식 수, 트리 차수 = 모든 노드 차수 중 최댓값. 위 트리는 트리 차수 = 2(A·B가 최대). '자식이 셋이라 차수=3'은 함정. ⚠️ 함정 ② 잎 = 단말(Terminal) = 외부(External) 노드 — 같은 노드의 동의어. 다른 이름으로 등장해도 같은 말. 🔑 암기 트리 차수 = 노드 차수 최댓값 / 잎 = 단말 = 터미널 🎯 빈출 'A는 루트? B의 차수는? 단말 노드는?' 형태로 거의 매회. 결정 키워드 = 비선형 + 계층 + 사이클 없음.

이진 트리 3종 ·트리·

[정의] 각 노드가 최대 2개의 자식(왼쪽·오른쪽)만 갖는 트리(모든 노드 차수 ≤ 2). 다시 3종으로 나뉜다.

정(Full): 자식 0 또는 2     완전(Complete): 왼쪽부터     편향(Skewed): 한쪽만
        [A]                       [A]                   [A]
       /   \                     /   \                     \
     [B]   [C]                 [B]   [C]                   [B]
     / \   / \                 / \   /                       \
   [D][E][F][G]              [D][E][F]                       [C]

🔑 암기 정 = 자식 0 또는 2 / 완전 = 왼쪽부터 빈틈없이 / 편향 = 한쪽으로만 💡 보충 노드 수 N인 완전 이진 트리의 높이는 약 log₂N — 'log 형태'라는 감각만. 계산 문제까진 거의 안 나옴. 🎯 빈출 분류 매칭. '자식 0 또는 2(정)', '왼쪽부터(완전)', '한쪽만(편향)' 세 키워드면 즉답.

트리 운행법(순회) ·전중후·1순위·

[정의] 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 순서 규칙. 루트(Root)를 언제 방문하느냐로 이름이 갈린다. 시험 출제율 1위 영역.

[추적] 아래 트리를 세 운행법으로 읽으면 — Root(A) 위치만 다를 뿐.

              [A]
             /   \
          [B]     [C]
         /  \    /  \
       [D]  [E][F]  [G]

🔑 암기 전중후 — 전위(Root 먼저) · 중위(Root 가운데) · 후위(Root 나중). 영문 Pre/In/Post = 전/중/후. 🔑 즉답 Pre는 첫 글자가 루트, Post는 끝 글자가 루트, In은 루트가 가운데. 보기 4개 중 3개를 즉시 선소거. 🎯 빈출 '작은 트리 그림 → 운행 결과' 형태가 거의 매회. 보기에 보통 Pre·In·Post·레벨(BFS) 네 결과를 다 깔아 함정.

수식 트리와 후위 표기 ·응용·

[정의] 운행법을 수식(Expression) 표기에 그대로 적용. 같은 수식 트리도 운행법에 따라 표기가 달라진다.

수식 (A + B) * C 의 트리:

            [*]
           /   \
         [+]   [C]
        /   \
      [A]   [B]

💡 핵심 사람은 중위(A+B)가 익숙하지만 컴퓨터는 후위(AB+) 를 선호 — 후위 표기는 스택을 쓰면 괄호 없이 계산 가능. 컴파일러가 수식 파싱 시 내부적으로 후위로 변환. 앞서 본 스택의 '후위 표기 변환' 사례가 여기서 만난다. 🎯 빈출 '이 수식 트리의 후위 순회 결과는?' 또는 '후위 표기로 변환하면?' 형태. 운행법 추적 그대로 적용.

기출 다지기

[기출 1 출제] 다음 중 스택(Stack)의 특징으로 옳은 것은? (긍정 판단형)

• ① 자료의 입력과 출력이 같은 쪽에서 이루어진다
• ② 가장 먼저 입력된 자료가 가장 먼저 출력된다
• ③ 비선형 자료구조의 일종이다
• ④ 자료의 출력은 항상 자료의 가운데에서 이루어진다

[기출 2 출제] 다음 ( )에 들어갈 가장 적절한 자료구조는? (빈칸형)

운영체제에서 프린터에 출력 요청이 들어오는 순서대로 인쇄 작업을 처리하기 위해 사용하는 자료구조는 ( )이며, First In First Out(FIFO) 방식으로 동작한다.

• ① 스택(Stack)
• ② 큐(Queue)
• ③ 트리(Tree)
• ④ 그래프(Graph)

[기출 3 출제] 다음 트리를 전위 순회(Pre-order)한 결과로 옳은 것은? (시각자료형)

              [A]
             /   \
            [B]    [C]
           /  \      \
         [D]  [E]    [F]

• ① A B D E C F
• ② D B E A C F
• ③ D E B F C A
• ④ A B C D E F

[기출 4 출제] 다음 트리를 후위 순회(Post-order)한 결과로 옳은 것은? (시각자료형 · 같은 트리)

              [A]
             /   \
            [B]    [C]
           /  \      \
         [D]  [E]    [F]

• ① A B D E C F
• ② D B E A C F
• ③ D E B F C A
• ④ A B C D E F

[기출 5 출제] 다음 트리에 대한 설명 중 잘못 짝지어진 것은? (짝짓기 오류형)

              [A]
             /   \
            [B]    [C]
           /  \      \
         [D]  [E]    [F]

• ① 루트 노드: A
• ② 단말 노드(잎): D, E, F
• ③ 트리의 차수(Degree): 3
• ④ 트리의 높이(Height): 3

[기출 6 출제] 자료구조에 대한 설명으로 옳지 않은 것은? (부정형)

• ① 배열은 인덱스를 이용해 O(1) 시간에 임의 접근이 가능하다
• ② 연결 리스트는 노드 간 포인터로 연결되어 동적 메모리 할당이 가능하다
• ③ 연결 리스트는 인덱스로 임의 접근 시 O(1) 시간에 접근 가능하다
• ④ 이중 연결 리스트는 양방향(앞·뒤) 이동이 가능하다

[기출 7 출제] 다음 자료구조 중 분류가 다른 하나는? (소거형)

• ① 스택(Stack)
• ② 큐(Queue)
• ③ 연결 리스트(Linked List)
• ④ 트리(Tree)

한 장 요약

🎯 합격 한 끗: 가장 잦은 두 유형 = 트리 운행법(전중후) + 스택/큐 매칭(접줄). 다섯 단어(선비·Big-O 빅쓰리·단이원·접줄·전중후)만 외워두면 10강은 거뜬. 단골 함정 3종 = '트리=선형'(→비선형), '연결 리스트 O(1) 임의 접근'(→O(n)), '트리 차수=자식 총합'(→노드 차수 최댓값).