고급 자료구조·정렬·탐색

10강의 그릇(자료구조) 위에서 데이터를 줄 세우고(정렬)·찾아내는(탐색) 도구를 다룬다. 매 회차 선·삽·버 1회전 추적과 이분 탐색 정렬 전제가 확실한 점수밭. 10강의 큐·스택·완전 이진 트리·Big-O 빅쓰리가 여기서 BFS·DFS·힙·탐색 복잡도로 그대로 살아난다.

핵심 암기: 정렬 8종 선삽버퀵병힙셸기 · 1회전 추적 선삽버 · 탐색 3종 순이해 · 해시 함수 5종 제폴기숫제 · 충돌 해결 개체 · 그래프 탐색 BFS=큐·DFS=스택

고급 자료구조 — 그래프와 힙

그래프(Graph) ·자료구조·

[정의] 정점(Vertex) 과 그 사이를 잇는 간선(Edge) 으로 이루어진 비선형 자료구조. 트리도 그래프의 한 종류로, 트리는 사이클이 없고 부모-자식이 명확한 반면 그래프는 자유롭게 연결되고 사이클도 허용된다.

[분류] 간선에 방향이 있느냐로 갈린다.

⚠️ 함정 '트리는 그래프가 아니다' 보기는 함정. 트리 = 사이클 없는 연결 그래프로, 그래프의 특수한 한 종류다. 🎯 빈출 정의 키워드(정점·간선)와 방향/무방향 구분 매칭까지가 출제 범위. 깊이 들어가지 않는다.

그래프 표현 — 인접 행렬 vs 인접 리스트 ·표현·

[정의] 그래프를 메모리에 저장하는 방식은 두 가지뿐. 어느 게 더 좋은지는 정답이 없는 trade-off라, '~에 적합한 표현법은?' 형태로 나온다.

🔑 즉답 공간 복잡도로 판별 — O(V²) 보이면 인접 행렬, O(V+E) 보이면 인접 리스트. 💡 비유 인접 행렬 = 30×30 출석부 표(짝꿍 한눈에, 빈 칸 낭비) / 인접 리스트 = 학생별 친구 이름만 적은 노트(절약, 일일이 펴봐야 함). 🎯 빈출 매 회차는 아니지만 공간 복잡도 매칭으로 간헐 등장.

그래프 탐색 — BFS·DFS ·탐색·1순위·

[정의] 그래프 위 모든 정점을 훑는 두 방법. 10강의 큐·스택이 그대로 재료가 된다.

🔑 암기 BFS=큐, DFS=스택 — 가까운 곳부터 한 명씩 → 먼저 발견한 정점 먼저(FIFO·큐) / 한 길 끝까지 파고들다 되돌아감 → 가장 최근 정점부터(LIFO·스택). ⚠️ 함정 'BFS=스택', 'DFS=큐' 형태 보기는 모두 거꾸로. BFS=큐, DFS=스택이 정답. 🎯 빈출 변형 출제 거의 없는 매 회차 단골. 거의 100% 점수밭. 📝 기출 BFS 구현 자료구조를 직접 물음.

힙(Heap)과 우선순위 큐 ·자료구조·

[정의] 부모-자식 간 크기 순서 규칙을 만족하는 완전 이진 트리. 10강에서 본 완전 이진 트리(왼쪽부터 빈틈없이 채움)가 힙의 토대라, 배열 한 줄로도 표현된다.

[흐름] 힙의 진짜 쓸모는 우선순위 큐(Priority Queue) 구현. 보통 큐는 FIFO(먼저 온 순)지만, 우선순위 큐는 순서가 아니라 급한 정도가 기준 — 늦게 와도 더 급한 일이 먼저 나간다.

💡 비유 보통 큐가 줄서기라면 우선순위 큐는 응급실 트리아지 — 나중에 와도 심정지 환자가 감기 환자보다 먼저 처치받는다. OS 프로세스 스케줄링(우선순위 높은 프로세스 먼저 CPU 할당)도 같은 구조. 🔑 즉답 힙 = 완전 이진 트리 + 최대 힙은 루트가 최댓값 두 키워드면 끝. 🎯 빈출 '힙은 어떤 트리?'(완전 이진 트리)·'최대 힙 루트는?'(최댓값) 매칭 정도.

정렬 알고리즘

정렬 8종 분류와 시간복잡도 ·종합·

[정의] 정렬 = 데이터를 오름차순/내림차순으로 줄 세우는 알고리즘. 정처기 출제는 8종. 다 외우지 말고 분류와 시간복잡도로 묶는다.

🔑 암기 선삽버퀵병힙셸기 — 단순 3(선·삽·버) + 분할정복 2(퀵·병합) + 힙 + 셸 + 기수. 🔑 분류 한 줄 단순 3 = O(n²) · 고급 3(퀵·병합·힙) = O(n log n) · 셸은 중간(n^1.5) · 기수는 별종(dn). ⚠️ 함정 퀵의 최악은 O(n²)(피벗을 정렬된 끝값으로 잡았을 때). '퀵은 항상 O(n log n)' 보기는 함정 — 병합·힙만 최악도 O(n log n) 보장. 🎯 빈출 '평균 O(n²)가 아닌 정렬은?'·'O(n log n)인 정렬은?' 매 회차 한 문제. 안정성은 가끔 — 삽버병기(삽입·버블·병합·기수)=안정, 선셸퀵힙(선택·셸·퀵·힙)=불안정.

선택 정렬(Selection Sort) ·1회전·1순위·

[정의] 전체에서 최솟값을 찾아 맨 앞과 자리 바꾸기. 매 회전마다 남은 영역에서 최솟값을 선택해 앞으로 끌어온다. 1회전이 끝나면 맨 앞 한 자리가 확정.

[추적] 오름차순 1회전 — 초기 [37, 14, 17, 40, 35]:

1단계: 전체에서 최솟값 = 14 (2번째 위치)
2단계: 1번 자리(37) ↔ 14 교환
결과:  [14, 37, 17, 40, 35]
        └ 14가 맨 앞에 확정

💡 비유 운동회 줄세우기 — 전체를 둘러봐 가장 키 작은 학생을 맨 앞으로 데려온다. 🔑 표식 1회전 후 맨 앞 한 자리에 최솟값 확정. ⚠️ 함정 선택·삽입은 1회전 결과가 우연히 같을 수 있다. 차이는 '확정된 자리 개수' — 선택=1번 자리 1개.

삽입 정렬(Insertion Sort) ·1회전·1순위·

[정의] 2번째 원소부터 꺼내, 앞쪽 정렬된 부분의 알맞은 자리에 끼워 넣기. 1번 자리는 정렬됐다 가정. 회전이 늘수록 앞쪽 정렬 영역이 한 자리씩 늘어난다.

[추적] 오름차순 1회전 — 초기 [37, 14, 17, 40, 35]:

1단계: 2번 원소 14 를 꺼낸다
2단계: 앞쪽 [37] 과 비교 → 14 < 37 → 37 앞으로 끼움
결과:  [14, 37, 17, 40, 35]
        └─┴ 14·37 앞 두 자리가 정렬 영역

💡 비유 카드 게임 — 새로 받은 카드를 손에 든 정렬된 카드 사이 알맞은 자리에 쏙 끼운다. 🔑 표식 1회전 후 앞 두 자리 정렬. 회전 수 = 정렬된 영역 길이 − 1. ⚠️ 함정 위 결과 [14, 37, 17, 40, 35]는 선택 정렬과 똑같다. 단서는 어디까지 정렬됐는가 — 선택=1개, 삽입=2개.

버블 정렬(Bubble Sort) ·1회전·1순위·

[정의] 옆 사람과 비교해 큰 사람이 뒤로 한 칸씩 밀려나기. 1번-2번, 2번-3번… 끝까지 옆 자리와 비교. 1회전이 끝나면 가장 큰 값이 맨 뒤로 떠밀려 간다.

[추적] 오름차순 1회전 — 초기 [37, 14, 17, 40, 35]:

1·2번: 37>14 교환  [14, 37, 17, 40, 35]
2·3번: 37>17 교환  [14, 17, 37, 40, 35]
3·4번: 37<40 유지  [14, 17, 37, 40, 35]
4·5번: 40>35 교환  [14, 17, 37, 35, 40]
결과:              [14, 17, 37, 35, 40]
                                └ 최댓값 40이 맨 뒤에 확정

💡 비유 욕조 거품 — 큰 거품이 먼저 위로 떠오른다. 한 회전마다 가장 큰 값 하나가 뒤로. 🔑 표식 1회전 후 맨 뒤 한 자리에 최댓값 확정. ⚠️ 함정 '선택은 맨 뒤 최댓값'·'버블은 맨 앞 최솟값' 보기는 거꾸로. 선택=앞·최솟값, 버블=뒤·최댓값.

선·삽·버 1회전 비교 ·시험1순위·

[정의] 매 회차 한 문제씩 나오는 시험 1순위. 한 표로 압축한다.

[표] 초기 [37, 14, 17, 40, 35] 오름차순 1회전:

🔑 즉답 맨 앞 한 자리 정렬 → 선택 / 앞 두세 자리 정렬 → 삽입 / 맨 뒤 최댓값 → 버블. ⚠️ 함정 매 회차 단골 2종 — ① 선택·삽입 우연 일치(확정 자리 개수로 구분: 선택 1개·삽입 2개) ② 선택과 버블 방향 뒤집기(선택=앞·최솟값, 버블=뒤·최댓값). 보기 읽을 때 방향과 자리 개수 두 단서를 다시 확인. 🎯 빈출 '1회전 수행 후 데이터 상태'를 묻는 추적형이 단연 1순위. 종이에 한 칸씩 적어가며 푸는 게 정확.

고급 정렬 — 셸·퀵·병합·힙·기수 ·고급·

[정의] 여기서부터는 이름과 핵심 키워드만. 1회전 추적은 거의 안 나온다.

💡 비유 퀵 = 반장(피벗) 기준 좌우 분리 후 각 그룹서 또 반장 선출(분할정복) / 기수 = 우편번호 한 자리씩 버킷에 분류. 💡 실무 자바 Arrays.sort(int[]) 원시 타입 정렬 = 듀얼 피벗 퀵 정렬. (객체 정렬·파이썬 sorted()는 Timsort라 퀵 예시로는 부적합.) 🔑 즉답 '비교를 하지 않는 정렬'·'자릿수 기반' → 기수 / '삽입 정렬 개선판' → 셸 / '피벗' → 퀵 / '분할 후 합치며 안정 정렬' → 병합. ⚠️ 함정 '퀵은 항상 O(n log n)' → 최악 O(n²)(피벗 의존). 병합·힙은 최악도 O(n log n) 보장.

탐색과 해싱

탐색 3종 — 순이해 ·탐색·

[정의] 탐색(Search) = 데이터에서 원하는 값을 찾아내는 알고리즘. 정처기 출제는 3종.

🔑 암기 순이해 — 순차·이분·해싱. 10강 Big-O 빅쓰리가 그대로 매칭 — 순차는 한 바퀴(O(n))·이분은 반토막(O(log n))·해싱은 즉답(O(1)). 🎯 빈출 '탐색이 아닌 것은?' 소거형 + 시간복잡도 매칭. 순차 탐색은 'O(n)·정렬 필요 없음' 두 키워드면 끝.

이분 탐색 — 정렬 전제와 비교 횟수 ·함정1순위·

[정의] 중간 값을 본다 → 찾는 값보다 크면 앞쪽 절반, 작으면 뒤쪽 절반으로 범위를 줄인다 → 반복. 전제 조건: 데이터가 정렬돼 있어야 함(시험 함정 1순위).

[추적] 정렬 배열 1, 3, 5, 7, 9, 11, 13, 15, 17에서 15 찾기:

1회: 중간 9  → 9 < 15  → 오른쪽 [11,13,15,17]
2회: 중간 13 → 13 < 15 → 오른쪽 [15,17]
3회: 중간 15 → 15 == 15 → 찾음
총 비교: 3회  (log₂9 ≈ 3.17 → 올림 3)

[표] 데이터 크기별 최대 비교 횟수 = log₂N(올림):

💡 비유 두꺼운 사전을 딱 중간부터 펼쳐, 찾는 단어가 앞 글자면 앞 절반·뒷 글자면 뒤 절반을 또 가운데 펼친다. 한 번에 후보가 절반씩 준다. 💡 실무 DB B-Tree 인덱스가 본질적으로 이분 탐색의 확장(다중 분할). 3과목 DB 인덱스에서 다시 만난다. 🔑 즉답 O(log n) + 정렬 전제 + 중간 값 비교 + 비교 횟수 ≈ log₂N(올림). ⚠️ 함정 '이분 탐색은 정렬 안 된 데이터에서도 빠르다'·'순서와 무관하게 O(log n)' 보기는 모두 함정. 정렬돼 있을 때만 동작. '이분 탐색' 단어가 보이면 '정렬'이 같이 등장하는지부터 확인.

해싱과 해시 함수 5종 — 제폴기숫제 ·해싱·

[정의] 해시 함수(Hash Function) 로 키를 입력해 저장 위치(주소)를 계산해 즉시 찾는 방식. 평균 O(1) — 데이터가 100만 개든 1억 개든 같은 시간. 자료구조 중 가장 빠른 평균 성능.

[표] 핵심 용어 4종.

[표] 해시 함수 5종 — 정처기 출제는 이 다섯이 전부.

💡 비유 도서관 청구기호 — 책 제목(키)을 청구기호(해시 값)로 바꾸면 몇 층 몇 칸인지 바로 계산. 한 권씩 둘러볼 필요 없음. 자바 HashMap·파이썬 dict가 표준 해시 자료구조. 🔑 암기 제폴기숫제 — 제곱·폴딩·기수변환·숫자분석·제산. 직접 계산 문제는 거의 없고 이름·키워드 매칭까지만. 🎯 빈출 '해시 함수가 아닌 것은?'·'소수로 나눈 나머지 → 제산법' 매칭 매 회차.

해시 충돌 해결 — 개체 ·충돌·

[정의] 서로 다른 키가 같은 주소로 계산되는 충돌(Collision) 해결법은 딱 두 분류.

[표] 개방 주소법 세부 3종.

💡 비유 내 좌석에 다른 사람이 앉았을 때 — 옆 빈자리로 옮기면 개방 주소법, 그 사람 옆에 의자를 끌어다 붙이면 체이닝. 🔑 암기 개체 — 개방 주소법 vs 체이닝. '연결 리스트' 키워드 → 체이닝 / '선형·이차·이중' → 모두 개방 주소법. ⚠️ 함정 '선형 조사법은 체이닝의 일종'·'체이닝은 다른 빈 자리를 찾는다' 보기는 거꾸로. 체이닝 = 같은 자리에 매달기, 개방 주소법 = 다른 빈 자리. 📝 기출 '연결 리스트로 매다는 방식은?' → 체이닝.

기출 다지기

[기출 1 출제] 다음 자료를 오름차순 선택 정렬 할 때 1회전(Pass) 후의 결과 는? (1회전 추적형)

초기 배열: 9, 4, 5, 11, 8

• ① 4, 9, 5, 11, 8
• ② 4, 5, 9, 11, 8
• ③ 4, 5, 8, 9, 11
• ④ 9, 5, 4, 11, 8

[기출 2 출제] 다음 자료를 오름차순 삽입 정렬 할 때 PASS 1의 결과 로 옳은 것은? (1회전 추적형)

초기 배열: 8, 3, 4, 9, 7

• ① 3, 8, 4, 9, 7
• ② 3, 4, 8, 9, 7
• ③ 3, 4, 7, 8, 9
• ④ 8, 3, 4, 7, 9

[기출 3 출제] 다음 자료를 오름차순 버블 정렬 할 때 1회전(Pass) 후의 결과 는? (1회전 추적형)

초기 배열: 9, 6, 7, 3, 5

• ① 3, 5, 6, 7, 9
• ② 6, 7, 3, 5, 9
• ③ 3, 9, 6, 7, 5
• ④ 6, 9, 3, 5, 7

초기:  [9, 6, 7, 3, 5]
9>6 교환 → [6, 9, 7, 3, 5]
9>7 교환 → [6, 7, 9, 3, 5]
9>3 교환 → [6, 7, 3, 9, 5]
9>5 교환 → [6, 7, 3, 5, 9]

[기출 4 출제] 다음 정렬 알고리즘 중 평균 시간복잡도가 O(n²)가 아닌 것은? (시간복잡도 분류형)

• ① 선택 정렬(Selection Sort)
• ② 삽입 정렬(Insertion Sort)
• ③ 버블 정렬(Bubble Sort)
• ④ 퀵 정렬(Quick Sort)

[기출 5 출제] 다음 정렬된 데이터 에서 이분 탐색 으로 값 15 를 찾을 때 비교 횟수는? (이분 탐색 추적형)

[1, 3, 5, 7, 9, 11, 13, 15, 17]

• ① 1회
• ② 2회
• ③ 3회
• ④ 4회

1회: 중간 9  → 9 < 15  → 오른쪽 [11,13,15,17]
2회: 중간 13 → 13 < 15 → 오른쪽 [15,17]
3회: 중간 15 → 찾음

[기출 6 출제] 해시 충돌 발생 시 같은 해시 주소에 연결 리스트를 매달아 저장하는 방식은? (키워드 매칭형)

• ① 선형 조사법(Linear Probing)
• ② 이차 조사법(Quadratic Probing)
• ③ 이중 해싱(Double Hashing)
• ④ 체이닝(Chaining)

[기출 7 출제] 그래프의 너비 우선 탐색(BFS)을 구현할 때 사용되는 자료구조는? (키워드 매칭형)

• ① 스택(Stack)
• ② 큐(Queue)
• ③ 트리(Tree)
• ④ 해시 테이블(Hash Table)

한 장 요약

🎯 합격 한 끗: 가장 잦은 세 유형 = 선·삽·버 1회전 추적(선삽버) + 이분 탐색 정렬 전제(순이해) + 해싱 충돌 매칭(개체). 매 회차 출제의 80%. 단골 함정 3종 = '이분 탐색은 정렬 없이도 빠르다'(→정렬 전제 필수), '퀵은 항상 O(n log n)'(→최악 O(n²)), 'BFS=스택·DFS=큐'(→반대). 다섯 묶음(선삽버·선삽버퀵병힙셸기·순이해·제폴기숫제·개체)만 손에 박으면 11강은 거뜬.