코딩 테스트 기초 - 자료구조 별 시간복잡도 정리 (Big O, O(n) ...같은거)

안녕하세요. 제가 요즘 코딩테스트 공부를 하는데요

오늘은 알고리즘을 배울 때 기초가 되는 시간복잡도와 자료구조에 대해 공부하겠습니다.

 

[1] 일단 먼저 요약부터 보여드리겠습니다.

 

네.. 각각

O(1) : 바로 접근
O(log n) : 절반 씩 줄이기
O(n) : 선형 (for 문 한번)
O(n log n) : 선형 로그 (for 문 돌면서 절반 씩 줄이는 작업)
O(n^2) : 이중 for 문

 

이런 느낌 입니다.

 

 

gpt 말로는

문제 읽기 → N 범위 확인 → 가능한 시간복잡도 추정 → 알고리즘 유형 선택

이런식으로 풀라하네여 (맞는 방법인지는 모르겠음)

[2] n 범위허용 복잡도예시 알고리즘

n ≤ 10	O(n!), O(2ⁿ)	완전탐색, 순열
n ≤ 20	O(2ⁿ)	비트마스크 DP
n ≤ 500	O(n³)	플로이드-워셜
n ≤ 3,000	O(n²)	버블/삽입/선택정렬
n ≤ 1,000,000	O(n log n)	병합정렬, 힙정렬
n ≤ 10,000,000	O(n)	선형 탐색, 카운팅
n > 10,000,000	O(log n), O(1)	이진탐색, 해시

여기서 n은 그냥 입력 데이터의 크기입니다.

문제마다 다르게 정의됩니다. 예를 들어:

배열 문제 → 배열의 원소 개수 문자열 문제 → 문자열의 길이 그래프 문제 → 노드 수(V), 간선 수(E) 두 배열 문제 → 각각 n, m으로 따로 씀

예를 들어 "배열에서 최댓값 찾기"라면, 배열에 원소가 100만 개 있으면 n = 1,000,000인 거예요. 그러면 O(n²) 알고리즘은 1조 번 연산 → 시간 초과, O(n)은 100만 번 → 통과, 이렇게 판단하면 됩니다.

 

 

 

 

 

[3] 자료구조 별 연산 복잡도

 

1. 배열/리스트

 

2. 스택/큐

 

 

3. 해시맵/셋

 

 

4. 힙(우선순위 큐)

참고로 힙(Heap) 이란 우선순위 큐를 위한 자료구조 입니다. 부모노드의 key 값이 자식노드의 key 값보다 늘 작습니다.
완전이진트리의 일종 입니다.
(완전이진트리 : 마지막 레벨 제외 그 이전 레벨까지는 모든 레벨이 채워져 있어야 하며, 노드는 왼쪽에서 오른쪽으로 채워져야 함)

 

5. 이진 탐색 트리

이진탐색트리는 부모노드를 중심으로 부모노드보다 작으면 좌, 크면 우. 이런 구조입니다.
중복되는 노드가 없고 최솟값은 좌 최하단, 최댓값은 우 최하단 입니다.

(힙은 각 노드의 값이 자식 노드보다 크거나 같음(작거나 같음) + 좌 우의 크기 상관 X
 최대/최솟값이 root 에 위치함)

 

 

6. 그래프

 

 

7. 덱

 

 

[4] 각 자료구조 별 import