오늘 한 일
- 자료구조 & 알고리즘 기초 개념 정리
- 배열, 연결리스트, 스택, 큐, 해시 테이블 학습
배운 내용
시간·공간 복잡도
- 빅 오(Big O): 실행 시간의 점근적 상한 — 최악의 경우
- 빅 세타(Θ): 평균, 빅 오메가(Ω): 하한 (최선의 경우)
- 실무에서는 Big O가 기본 지표
배열 vs 연결리스트
| 배열 | 연결리스트 |
|---|
| 메모리 | 순차 할당 | 비순차 (포인터 연결) |
| 임의 접근 | O(1) | O(n) |
| 삽입/삭제 (위치 주어질 때) | O(n) — 이동 필요 | O(1) |
- 자주 헷갈리는 점: 연결리스트의 삽입·삭제가 O(1)인 건 위치(노드 포인터)가 이미 주어졌을 때. 탐색까지 포함하면 O(n)
스택 & 큐
- 스택(LIFO): 한 쪽 끝에서만 삽입·삭제 (
push / pop)
- 큐(FIFO): 앞에서 삭제(
dequeue), 뒤에서 삽입(enqueue)
- 변형: 원형 큐(메모리 재사용), 덱(양방향), 우선순위 큐
해시 테이블
- 해시 함수 → 버킷 인덱스 결정, 평균 탐색 O(1)
- 충돌 해결 방법 두 가지
- 체이닝: 같은 인덱스에 연결리스트로 이어 붙임 → 최악 O(n)
- 개방 주소법: 충돌 시 다른 빈 버킷 탐색
- 선형 조사법: 군집화(clustering) 발생 가능
- 이중 해싱: 두 번째 해시 함수로 탐사 거리 결정 → 군집화 완화
내일 할 것
- what-i-want 프로젝트: OG 이미지 → 랜딩 → E2E
- 트리·그래프 개념 예습 (다음 자료구조 주제)