Big-O 복잡도 체크리스트 – 코딩 인터뷰를 더 빠르게 마스터하세요

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

개발 툴

대상자

• 초보~중급 개발자에게 코딩 인터뷰 준비 및 알고리즘 최적화에 실질적 도움
• 난이도: 기초 개념 중심, 복잡도 분석 기법 설명

핵심 요약

• Big-O 복잡도는 알고리즘의 시간/공간 효율성을 측정하는 핵심 지표
• 배열 vs. 링크드 리스트, 해시테이블, 정렬 알고리즘(Quick/Merge/Bubble) 등 주요 구조별 복잡도 비교 제공
• 시간/공간 트레이드오프를 시각적 형태로 정리하여 복잡도 분석의 효율성 향상

섹션별 세부 요약

1. 배열 vs. 링크드 리스트

• 배열: O(1) 접근 시간, O(n) 삽입/삭제 시간
• 링크드 리스트: O(n) 접근 시간, O(1) 삽입/삭제 시간
• 시간/공간 트레이드오프 예시: 배열은 메모리 연속성에 유리, 링크드 리스트는 동적 확장성에 유리

2. 해시테이블, 트리, 그래프

• 해시테이블: O(1) 평균 검색/삽입/삭제 시간, O(n) 최악의 경우
• 트리: 이진 탐색 트리 O(log n), 균형 트리 O(log n)
• 그래프: 깊이 우선 탐색(DFS) 및 너비 우선 탐색(BFS) O(V + E)

3. 정렬 알고리즘

• Quick Sort: 평균 O(n log n), 최악 O(n²)
• Merge Sort: O(n log n) 시간, O(n) 공간
• Bubble Sort: O(n²) 시간, O(1) 공간

4. 시간/공간 트레이드오프

• 캐싱 기법: O(1) 접근 시간을 위해 O(n) 공간 사용
• 압축 알고리즘: O(n) 시간 대신 O(1) 공간 절약
• 트레이드오프 예시: 해시테이블의 O(1) 검색 대신 O(n) 공간 소요

결론

• Big-O 체크리스트는 인터뷰에서 알고리즘 효율성 판단, 코드 최적화에 필수적
• 시각적 비교와 핵심 개념 요약을 통해 복잡도를 빠르게 파악 가능
• bigocheatsheet.com을 참고하여 실무에서 바로 적용 가능