코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 고급 자료구조
100만 개 데이터에서 중복 제거:
배열 + 정렬: O(n log n) ≈ 20ms
해시 셋: O(n) ≈ 5ms
중첩 반복(순진): O(n²) ≈ 2800초 ← 47분!
예시 — 빈번한 삽입/삭제:
10만 개 데이터 중간에 삽입/삭제 10만 회:
배열: O(n) × 10만 = O(n²) ≈ 50초
연결 리스트: O(1) × 10만 = O(n) ≈ 0.1초
선택의 핵심 질문:
1. 어떤 연산을 가장 많이 하는가?
2. 데이터의 크기는 얼마인가?
3. 순서가 중요한가?
4. 중복을 허용하는가?
5. 갱신이 있는가?
이 레슨에서 모든 자료구조를 상황별로 정리합니다.여러분, 자료구조 선택이 왜 중요할까요?
같은 문제를 풀더라도 자료구조에 따라 성능이 극적으로 달라집니다.
그림 왼쪽 위를 보세요.
100만 건의 데이터에서 이름을 검색하는 시나리오가 있어요.
배열로 순차 탐색하면 평균 50만 번 비교해야 합니다.
그런데 해시맵을 쓰면 단 1~3번이면 찾아요.
오른쪽 주황색 박스를 보세요.
무려 50만 배의 성능 차이가 납니다.
이게 바로 자료구조 선택의 위력이에요.
그러면 어떻게 올바른 자료구조를 고를 수 있을까요?
그림 아래쪽의 의사결정 흐름을 보세요.
첫 번째 질문은 핵심 연산이 무엇인가입니다.
검색이 많은지, 삽입이 많은지, 삭제가 많은지 파악하세요.
두 번째 질문은 데이터의 크기예요.
수십 개면 뭘 써도 비슷하지만, 수백만이면 복잡도가 결정적이에요.
세 번째는 순서가 필요한지입니다.
정렬 상태를 유지해야 하면 힙이나 균형 트리가 필요해요.
네 번째는 중복 허용 여부와 갱신 빈도예요.
읽기 위주라면 배열이 캐시 효율이 좋고, 쓰기 위주라면 연결 리스트가 유리합니다.
이 네 가지 질문에 답하면 최적 자료구조가 자연스럽게 결정돼요.
이번 레슨에서 각 상황별 최적 선택법을 체계적으로 배워봅시다.