내일배움캠프 37일차 - 자료구조 & 알고리즘 6주차 : 자료구조 선택의 기술
Level 1 자료구조 총정리
| 자료구조 | 핵심 특성 | 접근 | 검색 | 삽입/삭제 |
| vector | 순서 있는 연속 배열 | O(1) | O(n) | 최대 O(n) |
| queue | FIFO (선입선출) | front만 | ─ | O(1) |
| stack | LIFO (후입선출) | top만 | ─ | O(1) |
| map | key-value, 정렬 | O(log n) | O(log n) | O(log n) |
| set | key만, 정렬 | ─ | O(log n) | O(log n) |
| unordered_map | key-value, 해시 | O(1) 평균 | O(1) 평균 | O(1) 평균 |
| unordered_set | key만, 해시 | ─ | O(1) 평균 | O(1) 평균 |
선택 가이드
"순서대로 담고 싶다" → vector
"되돌리기" → stack
"대기열" → queue
"이름표로 찾고 싶다" → map
"있는지 없는지만" → set
같은 문제, 다른 도구
문제1. 출석부 문제
학생 30명의 출석을 관리합니다. 필요한 기능:
- (A) "김철수 출석했어?" - 특정 학생 출석 여부 확인
- (B) 전체 출석 학생 목록 출력
- (C) 출석한 학생 수 세기
이걸 vector / set / unordered_set 세 가지로 풀어보자.
: 검색이 핵심이면 set 계열 → 정렬 필요 없으면 unordered_set이 최적
문제2. Undo 기능
성능이 같다면, 의도를 더 잘 표현하는 도구를 고르자.
: vector와 stack은 성능이 O(1)로 동일하지만,
Undo는 가장 최근의 것만 필요로 하므로 stack이 더 안전.
문제3. 매출집계 - 세 가지 요구사항
편의점 매출 데이터가 있습니다. 해야할 일:
- (A) 각 상품이 몇 개 팔렸는지 집계
- (B) 가장 많이 팔린 상품 찾기
- (C) 전체 상품 목록을 이름순으로 출력
vector<pair>: 매번 순회하며 검색 + 직접 정렬 → 코드가 길어짐
map<string,int>: 카운팅을 sales["콜라"]++ 한줄로 구현가능, 순회 시 자동정렬
unordered_map<string, int>: 카운팅은 동일, 하지만 이름순 정렬 안됨
| 요구사항 | vector | map | unordered_map |
| (A) 상품별 집계 | △ 직접 구현 | ◎ m[key]++ | ◎ m[key]++ |
| (B) 최다 판매 | △ 정렬 후 | ○ 순회 | ○ 순회 |
| (C) 이름순 출력 | △ 정렬 필요 | ◎ 자동 정렬 | △ 별도 정렬 |
| 종합 평가 | △ | ◎ | ○ |
모든 면에서 최고인 도구는 없다
: 요구사항을 보고 가장 균형 잡힌 선택을 하는 것이 실력
도구 선택의 세 가지 기준
1. 성능 - "이 연산을 얼마나 자주 하는가?"
: 자주 하는 연산이 빠른 도구를 고른다. (ex1:출석부)
2. 의도 표현 - "읽는 사람이 의도를 알 수 있는가?"
: LIFO라면 stack, key-value라면 map (ex2: Undo)
3.요구사항 매칭 - "정렬? 중복? key가 있는가?"
: 기능이 맞는 도구를 고른다. (ex3: 매출집계)
※ 정답은 없고, 상황에 따른 "좋은 선택"이 있을 뿐이다.
CS돋보기
시간복잡도는 프로그래머의 예산 감각
: n =10000일때, O(1)=1번, O(log n)=~14번, O(n)=10,000번
: O(1)과 O(n)의 차이는 1만배, 도구 선택이 중요한 이유.
추상 자료형(ADT) - 설계도와 제품
: 규칙(인터페이스)는 같지만, 내부 구현은 다를 수 있는 자료형
ex) 자동판매기의 버튼기능(인터페이스)는 같지만, 내부 기계(구현)은 제조마다 다르다.
stack또한 사실 개념(규칙)이지, 특정 구현은 아니다.
: LIFO로 동작하면 그것이 stack.
실제 사용 예시
게임 개발
자료구조 선택은 프레임 레이트에 직결된다.
60 FPS게임에서 매 프레임 O(n) 검색을 넣으면?
→ 오브젝트가 많아질수록 프레임이 떨어진다.
UE5에서는 빈번한 검색에 TSet, TMap, 순서 처리에 TArray(=vector역할) 을 사용.
※ 게임 면접 빈출: "이 상황에서 어떤 자료구조를 사용하겠는가?"
웹/서버
자료구조 선택은 서버 비용에 직결된다.사용자 100만명의 접속 상태를 관리할 때?
→ vector로 순회: O(n) = 100만번
→ unordered_set: O(1) = 1번
Redis(캐시 서버)도 이 원리 그대로 상황별 자료구조를 자동 선택한다.
CS 전반
도구 선택 감각 = 알고리즘의 본질코딩 테스트 시간 초과의 가장 흔한 원인: 잘못된 자료구조 선택
→ vector에서 O(n)검색을 반복: O(n^2)
→ set을 사용하면: O(n log n)
자료구조를 바꾸는 것만으로 시간 복잡도가 내려간다.
오늘의 핵심
- 같은 문제라도 자료구조에 따라 성능이 달라진다.
: vector의 O(n) vs set의 O(log n) vs unordered_set의 O(1). 1만배 차이
- 도구 선택의 세 가지 기준
(1) 성능 - 자주 하는 연산이 빠른 도구
(2) 의도 표현 - 코드로 의도를 말한다
(3) 요구사항 매칭 - 정렬을 하나? 중복이 되나? key가 있나?
- 정답은 없고, 좋은 선택이 있다.
: 상황에 따른 양자택일을 이해하고 균형 잡힌 선택을 하는 것이 실력
- Level 1 완주: 시간 복잡도 → 자료구조별 특성 → 도구 선택
: "도구를 아는 것"에서 "도구를 고르는 것"으로 성장
댓글
댓글 쓰기