20강 / 20강

자료구조 고르는 법 — 문제에 맞는 그릇

20강의 마무리, 그리고 여러분이 만들 것

19강까지 오면서 계속 반복된 말이 있습니다 — "무엇을 자주 하느냐에 달렸다". 이제 그 판단을 체계적으로 하는 법을 정리합니다.

자료구조를 고를 때 던져야 할 질문은 딱 다섯 개입니다.

1️⃣

순서가 중요한가?

몇 번째인지가 의미가 있나

2️⃣

무엇을 자주 하나?

찾기 · 넣기 · 빼기 중

3️⃣

어디서 넣고 빼나?

앞 · 뒤 · 중간 · 아무데나

4️⃣

중복을 허용하나?

같은 값이 여럿 있어도 되나

5️⃣

얼마나 큰가?

100개인가 1억 개인가

고등학생문제에 맞는 그릇

마지막 강입니다. 19강까지 계속 반복된 말이 있어요.

"무엇을 자주 하느냐에 달렸다"

왜 "가장 좋은 자료구조" 가 없나

모든 자료구조가 무언가를 포기했기 때문입니다.

구조	얻은 것	포기한 것
리스트	번호 접근	중간 삽입
연결 리스트	중간 삽입	번호 접근
해시	즉시 찾기	순서
트리	순서 + 빠른 찾기	해시보다 느림
힙	최솟값 즉시	나머지 순서

모든 줄에 포기한 것이 있다 — 그게 이 강의의 결론

비유 — 신발

신발	좋은 곳	나쁜 곳
운동화	대부분	정장
등산화	산	무겁다
슬리퍼	가깝다	멀리 못 간다

"가장 좋은 신발" 은 없다 — 어디를 가느냐 에 달렸다

그리고 대부분의 경우 운동화면 됩니다. 자료구조에서는 그게 리스트와 딕셔너리예요.

🎮 자료구조 고르기 도우미

조건을 체크하면 알맞은 자료구조와 그 이유를 알려 줍니다. 아래에 있는 실전 문제 10개도 풀어 보세요.

고등학생가장 자주 쓰는 셋

실전에서는 세 가지가 대부분을 차지합니다.

구조	언제	비율
리스트	순서대로 담을 때	가장 많다
딕셔너리	이름으로 찾을 때	그다음
집합	중복 제거 · 포함 검사	그다음

이 셋으로 대부분이 해결된다 — 나머지는 특수한 경우

그럼 나머지는 왜 배웠나

이유	설명
안에 들어 있다	딕셔너리 = 해시 · deque = 연결 리스트
왜 빠른지 안다	느릴 때 원인을 찾는다
특수한 때	힙 · 그래프는 필요할 때 결정적
발상	재귀 · 나누어 정복은 어디에나

직접 안 만들어도 고를 줄 알아야 한다

흔한 실수 세 가지

실수	고치면
리스트로 포함 검사	집합으로 → 수백 배
리스트를 큐로	deque 로
정렬을 매번	필요할 때만 · 힙 고려

세 가지만 고쳐도 대부분의 성능 문제가 사라진다

그리고 이 셋은 한 줄씩만 고치면 됩니다. 성능 개선치고 비용이 아주 싸요.

한눈에 보는 선택 지도

이런 상황이면	이걸 쓰세요	왜
순서대로 쌓고 순서대로 읽는다	리스트	인덱스 접근 O(1), 가장 단순
절대 바뀌면 안 된다 / 열쇠로 쓴다	튜플	불변이라 안전하고 해시 가능
"있나 없나"만 자주 묻는다 / 중복 제거	집합	포함 검사 O(1)
이름으로 값을 찾는다	딕셔너리	열쇠 조회 O(1)
마지막 것부터 되돌린다	스택 (리스트)	LIFO — 실행 취소, 되짚기
먼저 온 것부터 처리한다	deque	FIFO — 앞뒤 모두 O(1)
가장 급한 것부터 처리한다	힙 (heapq)	최솟값 꺼내기 O(log n)
정렬된 순서 + 범위 검색이 필요하다	이진 탐색 트리 / 정렬 리스트 + bisect	해시는 범위를 못 다룸
계층 구조다 (폴더, 조직도)	트리	부모-자식 관계를 그대로
임의의 관계다 (친구, 도로)	그래프 (인접 리스트)	아무 점끼리 이을 수 있음

Counter — 딕셔너리 + 세기. 실전에서 정말 자주 씁니다.

Python 브라우저에서 실행

# 실전 ① 실시간 인기 검색어 top 5
import heapq, random
from collections import Counter

검색기록 = [random.choice(["자료구조", "파이썬", "급식", "축제", "시험", "동아리"])
            for _ in range(1000)]

세기 = Counter(검색기록)              # 딕셔너리의 친척 — 세는 데 특화
print("전체:", dict(세기))
print("top 3:", 세기.most_common(3))   # 안쪽에서 힙을 씁니다

deque 의 maxlen — 이런 옵션을 아는 것도 자료구조 공부입니다.

Python 브라우저에서 실행

# 실전 ② 최근 본 상품 5개 (중복 제거 + 순서 유지 + 개수 제한)
from collections import deque

최근 = deque(maxlen=5)                # maxlen! 넘치면 자동으로 앞이 빠집니다

def 봤다(상품):
    if 상품 in 최근:
        최근.remove(상품)             # 이미 있으면 빼고
    최근.append(상품)                 # 맨 뒤로 다시
    print(f"{상품:6} 조회 → {list(최근)}")

for ㅅ in ["신발", "모자", "가방", "신발", "티셔츠", "양말", "장갑"]:
    봤다(ㅅ)

print()
print("→ deque(maxlen=n) 하나로 '최근 n개' 기능이 끝납니다.")

고등학생고르는 순서

실제로 어떻게 판단하는지 순서를 만들어 봅시다.

"자주 하는 일" 을 먼저 적는다

1단계 — 무엇을 자주 하나

동작	맞는 구조
순서대로 훑기	리스트
번호로 꺼내기	리스트
있나 확인	집합
열쇠로 값 찾기	딕셔너리
양끝에서 넣고 빼기	deque
최솟값 계속 꺼내기	힙
범위 검색 · 정렬 유지	트리 (또는 정렬 리스트)

동작을 적으면 표에서 찾을 수 있다

2단계 — 얼마나 큰가

크기	판단
수백 개	뭘 써도 된다 — 읽기 쉬운 것
수만 개	차수를 신경 쓴다
수백만 개	메모리도 같이 본다

작으면 단순함이 이긴다 — 조기 최적화는 해롭다

3단계 — 재 본다

19강의 결론이에요. 짐작 말고 측정.

비유 — 여행 짐 싸기

순서	물음
1	어디 가나 — 무엇을 할 것인가
2	얼마나 오래
3	넣어 보고 무게를 잰다

가방을 먼저 고르지 않는다 — 할 일을 먼저 정한다

20강의 결론을 숫자로. 그릇 선택이 곧 성능입니다.

Python 브라우저에서 실행

# 실전 ③ 같은 문제를 세 가지 그릇으로 — 무엇이 다른가
import time, random

이름들 = [f"학생{ㅇ}" for ㅇ in range(30000)]
찾을이름 = ["학생29999"] * 2000

# ㄱ) 리스트 — 이름을 순서대로 훑는다
시작 = time.time()
for ㅇ in 찾을이름:
    ㅇ in 이름들
ㄱ = time.time() - 시작

# ㄴ) 집합 — 있나 없나만
집합 = set(이름들)
시작 = time.time()
for ㅇ in 찾을이름:
    ㅇ in 집합
ㄴ = time.time() - 시작

# ㄷ) 딕셔너리 — 있는지 + 값까지
점수표 = {ㅇ: random.randint(0, 100) for ㅇ in 이름들}
시작 = time.time()
for ㅇ in 찾을이름:
    점수표.get(ㅇ)
ㄷ = time.time() - 시작

print(f"리스트   : {ㄱ*1000:8.1f} ms   O(n)  — 있는지만 알 수 있음")
print(f"집합     : {ㄴ*1000:8.1f} ms   O(1)  — 있는지만 알 수 있음")
print(f"딕셔너리 : {ㄷ*1000:8.1f} ms   O(1)  — 값까지 알 수 있음")
print()
print("자료를 담는 그릇을 바꾼 것뿐인데 이만큼 달라집니다.")

고등학생20강을 한 장으로

여기까지 오신 것을 축하합니다. 🎉 상자 하나에서 시작해 여기까지 왔어요.

배운 그릇들

그릇	한 줄	강
리스트	번호로 즉시, 중간은 밀린다	2·3
튜플 · 집합	못 바꾼다 · 중복이 없다	4
딕셔너리	열쇠로 즉시	5
스택 · 큐	어느 끝에서 꺼내나	6·7
연결 리스트	번호 대신 화살표	8
트리 · BST	계층 · 절반 버리기	10·11
힙	최솟값만 보장	12
해시	찾지 않고 계산한다	13
그래프	아무 관계나	14

그런데 진짜 남는 것은 이름이 아닙니다

배운 것은 "무엇을 포기하고 무엇을 얻나" 를 묻는 습관이다

반복해 나온 다섯 가지

규칙이 있으면 절반을 버릴 수 있다 (11·16강)
제한이 있으면 단순하고 빨라진다 (6·12강)
계산이 찾기보다 빠르다 (5·13강)
같은 것을 가리키는 발상이 자란다 (8·10·14강)
측정하지 않으면 모른다 (19강)

언어가 바뀌어도 이 다섯은 그대로다

그리고 맞바꿈

얻는 것	내주는 것	어디서
즉시 접근	중간 삽입	리스트 (2강)
즉시 찾기	순서	해시 (13강)
정렬 유지	속도	트리 (11강)
넣는 속도	찾는 속도	연결 리스트 (8강)

공짜는 없다 — 무엇을 내줄지 고르는 것이 설계다

이제 대학생 눈높이로 한 번 더 읽어 보세요. 코드가 훨씬 잘 읽힐 겁니다.

여러분이 배운 것

1부 — 그릇의 기본형
변수 하나에서 시작해 리스트·튜플·집합·딕셔너리로 값을 담는 법을 배웠고, 스택과 큐로 꺼내는 규칙이 자료구조를 만든다는 걸 봤습니다. 연결 리스트에서 화살표라는 발상을, 재귀에서 스택이 숨어 있다는 사실을, 트리에서 계층을 담는 법을 익혔습니다.

2부 — 문제를 푸는 도구
힙으로 우선순위를, 해시로 즉시 찾기를, 그래프로 관계를 표현했습니다. BFS와 DFS는 큐냐 스택이냐라는 한 글자 차이였고, 탐색과 정렬은 같은 결과에 이르는 여러 길을 보여 줬습니다. 그리고 미로 하나에 그 모든 게 들어간다는 것도 확인했죠.

3부 — 판단의 기준
Big-O로 빠르기를 말하는 법을 배웠고, 마지막으로 완벽한 자료구조는 없고 문제에 맞는 자료구조가 있을 뿐이라는 결론에 닿았습니다.

이제 여러분에게 필요한 건 강의가 아니라 만들고 싶은 것 하나입니다. 동아리 회원 관리든, 급식 추천기든, 간단한 게임이든 좋습니다. 만들다 보면 반드시 이런 순간이 옵니다 — "이거 느린데, 그릇을 바꿔 볼까?"
그 순간이 오면, 이 20강이 여러분 안에서 작동하기 시작한 겁니다. 🎉

🤔 확인 문제

"회원 아이디로 회원 정보를 즉시 찾고 싶다" — 알맞은 자료구조는?

🤔 확인 문제

"작업이 계속 들어오는데 급한 것부터 처리해야 한다" — 알맞은 것은?

🤔 확인 문제

"점수가 80~90점인 학생을 자주 조회한다" — 해시(딕셔너리)를 쓰면 안 되는 이유는?

🤔 확인 문제

자료구조를 고를 때 가장 먼저 생각해야 할 것은?