리스트를 유용하게 만드는 것
리스트: 첫 번째 데이터 구조
리스트(일부 언어에서는 배열이라고 부름)는 항목들을 특정 순서대로 저장합니다. 다음과 같은 것들을 할 수 있습니다:
- 위치로 항목 접근하기: names[0]은 첫 번째 항목을 가져갑니다. O(1) — 즉시입니다.
- 끝에 항목 추가하기: names.append("Zoe"). O(1) — 즉시입니다.
- 모든 항목을 순서대로 순회하기: for name in names. O(N) — 각 항목을 한 번씩 방문합니다.
리스트는 항목들을 입력한 순서대로 보존합니다. 첫 번째 항목은 첫 번째로 유지됩니다. 마지막 항목은 마지막으로 유지됩니다.
# 애완동물 리스트
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) 즉시
print(pets[3]) # "fish" — O(1) 즉시
print(len(pets)) # 5 — 중복이 보존됨주목: "cat"은 두 번 나타납니다. "dog"도 두 번 나타납니다. 리스트는 중복을 허용합니다. 리스트는 정확히 입력한 대로, 입력한 순서대로 저장합니다.
하지만 리스트에는 약점이 있습니다. 다음과 같은 질문을 할 때 무슨 일이 일어나는지 보세요: "fish"가 이 리스트에 있는가?
# 멤버십 확인 — "fish"가 리스트에 있는가?
if "fish" in pets: # ["cat", "dog", "cat", "fish"...]을 하나씩 스캔
print("found!") # 찾기 전에 4개 항목을 확인했음컴퓨터가 "cat"을 확인합니다 — 없음. "dog" — 없음. "cat" — 없음. "fish" — 맞음! 4개 항목을 스캔한 후 찾았습니다. 1,000개 항목이 있으면 모두 1,000개를 스캔할 수도 있습니다. 그 멤버십 확인 비용은 O(N)입니다.
스캔 비용 예측하기
500명의 학생 이름이 무작위 순서로 리스트에 있습니다.
리스트에 "Zara"가 있는지 확인하고 싶습니다.
students = ["Alex", "Maria", ..., "Zara", ...] # 500명
if "Zara" in students:
print("enrolled")집합이 다르게 작동하는 방식
집합: 멤버십 질문을 위해 만들어짐
집합은 해싱이라는 기술을 사용하여 고유한 항목들을 저장합니다. 항목을 추가할 때 컴퓨터는 해시(숫자 지문)를 계산하여 해당 항목을 정확히 어디에 저장할지 알려줍니다.
멤버십을 확인할 때 컴퓨터는 같은 해시를 계산하고 올바른 위치로 직접 이동합니다. 스캔할 필요가 없습니다.
# 애완동물 집합
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — 중복 제거됨
print(len(pets)) # 3 — 고유 항목만리스트와의 세 가지 차이점에 주목하세요:
1. 중복 없음. "cat"이 입력에서 두 번 나타났지만 집합은 한 개의 사본만 보유합니다.
2. 보장된 순서 없음. 집합은 어떤 배열로든 항목을 출력할 수 있습니다.
3. 인덱스 접근 없음. pets[0]을 쓸 수 없습니다 — 집합에는 위치가 없습니다.
트레이드오프: 순서와 중복을 잃습니다. O(1) 멤버십 테스트를 얻습니다 — 항목이 있는지 확인하는 데 걸리는 시간은 집합에 5개 항목이 있든 500만 개 항목이 있든 같습니다.
# 멤버십 확인 — "fish"가 집합에 있는가?
if "fish" in pets: # hash("fish") → 버킷으로 이동 → 찾음
print("found!") # 정확히 1개 위치만 확인했음, 4개 아님집합 vs 리스트 멤버십
500명의 학생 이름이 리스트 대신 집합에 저장되어 있습니다.
students = {"Alex", "Maria", ..., "Zara", ...} # 500명
if "Zara" in students:
print("enrolled")나란히 비교하기
작업 비용 치트시트
다음이 필요할 때 리스트를 사용하세요:
- 항목이 특정 순서로 있음 (재생 목록, 레시피, 큐)
- 위치로 접근 (items[3])
- 중복이 보존됨 ("cat"이 3번 나타나면 = 3마리의 고양이)
다음이 필요할 때 집합을 사용하세요:
- 빠른 멤버십 확인 ("이것을 전에 봤나?")
- 자동 중복 제거
- 순서에 상관없음
순서와 빠른 조회가 모두 필요할 때 둘 다 사용하세요:
seen = set() # O(1) 멤버십 확인
result = [] # 삽입 순서 보존
for item in data:
if item not in seen: # O(1) 확인
seen.add(item) # O(1) 추가
result.append(item) # O(1) 추가
# 합계: O(N) — 한 번의 통과, 각 단계 O(1)이 "집합 + 리스트" 패턴은 둘의 최고를 제공합니다: 빠른 중복 감지를 사용한 정렬된 결과.
올바른 구조 선택하기
세 가지 문제가 있습니다. 각각에 대해 다음을 결정하세요: 리스트, 집합, 또는 둘 다?
1. 사용자가 추가한 순서대로 노래의 재생 목록을 저장해야 합니다.
2. 사용자명이 이미 사용되었는지 빠르게 확인해야 합니다.
3. 메일링 리스트에서 중복 이메일을 제거해야 하지만 가입 순서대로 유지해야 합니다.
중복 제거 문제
문제: 중복 제거, 순서 유지
이메일 가입 목록을 받았습니다. 일부 사람들이 두 번 가입했습니다. 각 사람에게 한 개의 이메일을 보내야 하며, 처음 가입한 순서대로 보내야 합니다.
시도 1: 리스트만 (느림)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
if email not in unique: # unique 리스트의 O(N) 스캔
unique.append(email)
# 작동합니다! 하지만: O(N) 확인 × N 항목 = O(N²)100개 가입으로는 ~5,000번 확인. 10,000개 가입으로는: ~50,000,000번 확인.
시도 2: 집합 + 리스트 (빠름)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
if email not in seen: # O(1) 해시 조회
seen.add(email) # O(1) 집합에 추가
unique.append(email) # O(1) 리스트에 추가
# O(1) 확인 × N 항목 = O(N)같은 결과. 같은 순서. 하지만: 10,000개 가입은 ~50,000,000번이 아닌 ~10,000번 확인이 필요합니다.
속도 향상 계산하기
리스트만 버전은 O(N²)에서 실행됩니다. 집합+리스트 버전은 O(N)에서 실행됩니다.
10,000개 이메일 가입이 있습니다.
공통 요소 찾기
문제: 두 리스트 모두에 있는 항목 찾기
두 개의 클래스 명단이 있습니다. 두 클래스에 모두 등록된 학생을 찾아야 합니다.
느린 접근법: 중첩 루프 O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N 반복
if student in class_b: # 매번 M번 스캔
both.append(student)
# O(N × M) — 각 학생이 class_b의 모든 학생에 대해 스캔됨빠른 접근법: 한 리스트를 집합으로 변환 O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) 빌드
both = []
for student in class_a: # N 반복
if student in class_b_set: # 매번 O(1)
both.append(student)
# O(N + M) — 집합을 한 번 빌드, N번 O(1)로 확인또는 Python의 내장 집합 교집합을 사용하여 더 간단하게:
both = set(class_a) & set(class_b) # O(N + M)& 연산자는 두 집합 모두에 나타나는 모든 항목을 찾습니다.
속도를 위해 다시 작성하기
한 학교에는 각각 200명의 회원이 있는 두 개의 동아리가 있습니다. 이 코드는 두 동아리에 있는 학생들을 찾습니다:
chess_club = [...] # 200명
art_club = [...] # 200명
both_clubs = []
for student in chess_club:
if student in art_club:
both_clubs.append(student)결정 프레임워크
데이터 구조 결정 프레임워크
항목 컬렉션을 저장하는 코드를 쓸 때마다 다음을 묻으세요:
1. 항목이 순서대로 필요한가? → 리스트
2. 빠른 멤버십 확인이 필요한가? → 집합
3. 순서와 빠른 확인이 모두 필요한가? → 집합 + 리스트 함께
4. 중복이 필요한가? → 리스트 (집합은 중복을 떨어뜨립니다)
---
이 수업의 핵심 통찰력: 같은 프로그램, 같은 문제를 해결하면서도 단지 올바른 데이터 구조를 선택하는 것만으로 1,000배에서 1,000,000배까지 빠르게 실행될 수 있습니다. 영리한 트릭은 없습니다. 복잡한 수학은 없습니다. 단지 다음과 같이 묻는 것입니다: 코드가 가장 자주 하는 작업은 무엇인가? 그 다음 해당 작업이 O(N) 대신 O(1)에서 비용이 드는 구조를 선택합니다.
이 수업은 리스트와 집합을 다루었습니다. 다른 문제를 해결하는 다른 데이터 구조가 있습니다 (딕셔너리, 트리, 힙). 결정 프레임워크는 동일합니다: 작업을 이해하고, 그러한 작업을 싸게 만드는 구조를 선택합니다.
---
더 깊이 있게 알고 싶으신가요? 우리의 Big O 수업은 성장률 & 확장 계산을 자세히 다룹니다. Big O: 얼마나 빠른 것이 충분히 빠른가?를 보세요. 우리의 unhamming 과정은 이 정확한 리스트-집합 수정이 프로덕션 소프트웨어에서 1,000배 속도 향상을 생성한 실제 결함 (MOAD-0001)을 다룹니다. 누락된 장: 알고리즘 복잡도를 보세요.
이 코드 디버그하기
한 학생이 책에서 나타나는 고유한 단어의 개수를 세기 위해 이 코드를 작성했습니다:
words = book.split() # 모든 단어의 리스트
unique_count = 0
checked = []
for word in words: # N개 단어
if word not in checked: # checked 리스트 스캔
checked.append(word)
unique_count += 1
print(unique_count)책에는 100,000개 단어가 있습니다.