학습 목표: Big-O 표기법 이해 · 배열 탐색 · 투 포인터 기법 · 문자열 처리 패턴 · 기본 정렬 알고리즘 복습
1️⃣ Big-O 표기법 (시간복잡도)
Big-O
알고리즘이 얼마나 빠른지(느린지)를 수학적으로 표현하는 방법
주요 복잡도 비교 (빠른 순)
| 표기법 | 이름 | 예시 |
|---|---|---|
O(1) | 상수 시간 | 배열에서 인덱스로 값 찾기 |
O(log n) | 로그 시간 | 이진 탐색 |
O(n) | 선형 시간 | 배열 전체 순회 |
O(n log n) | 선형로그 | 병합 정렬, 퀵 정렬 평균 |
O(n²) | 이차 시간 | 이중 for문, 버블 정렬 |
O(2ⁿ) | 지수 시간 | 피보나치 재귀 |
예시로 이해하기
# O(1) — 항상 한 번만 실행
def get_first(arr):
return arr[0] # 배열 크기와 상관없이 1번만 접근
# O(n) — 배열 크기만큼 반복
def find_max(arr):
max_val = arr[0]
for x in arr: # n번 실행
if x > max_val:
max_val = x
return max_val
# O(n²) — 이중 for문
def bubble_sort(arr):
n = len(arr)
for i in range(n): # n번
for j in range(n - i - 1): # 또 n번 → 총 n²번
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
📌 핵심: 중첩 for문이 보이면 일단 O(n²) 의심하기!
Big-O 계산 꿀팁
def example(arr):
# O(n) — 첫 번째 루프
for i in arr:
print(i)
# O(n) — 두 번째 루프
for j in arr:
print(j)
# 합치면? O(n) + O(n) = O(2n) → 상수 무시 → O(n)
💡 Big-O에서는 상수와 낮은 차수의 항은 무시하기
O(3n² + 5n + 100)→ 그냥O(n²)
2️⃣ 배열 탐색
선형 탐색 (Linear Search) - O(n)
처음부터 끝까지 하나씩 확인하는 방법.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # 인덱스 반환
return -1 # 없으면 -1
arr = [3, 7, 1, 9, 4]
print(linear_search(arr, 9)) # 출력: 3 (인덱스)
이진 탐색 (Binary Search) - O(log n)
정렬된 배열에서 쓰는 방법. 중간값을 기준으로 절반씩 범위를 좁혀나가는거
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # 오른쪽 절반으로
else:
right = mid - 1 # 왼쪽 절반으로
return -1
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 출력: 3
3️⃣ 투 포인터 기법 (Two Pointers)
개념
배열에서 두 개의 포인터(인덱스)를 동시에 움직이면서 문제를 푸는 기법.
이중 for문 O(n²) 대신 O(n)으로 풀 수 있어서 매우 중요함.
예시 1 - 두 수의 합 (정렬된 배열)
# 문제: 정렬된 배열에서 합이 target인 두 수의 인덱스 찾기
def two_sum_sorted(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # 합이 작으면 왼쪽 포인터 오른쪽으로
else:
right -= 1 # 합이 크면 오른쪽 포인터 왼쪽으로
return []
arr = [1, 2, 3, 5, 8, 13]
print(two_sum_sorted(arr, 10)) # 출력: [2, 4] → arr[2]+arr[4] = 3+8 = 11 아님
print(two_sum_sorted(arr, 11)) # 출력: [2, 4] → 3+8 = 11 ✅
시각화
[1, 2, 3, 5, 8, 13] target = 11
L R → 1+13=14 > 11 → R--
L R → 1+8=9 < 11 → L++
L R → 2+8=10 < 11 → L++
L R → 3+8=11 = 11 → 정답!
예시 2 - 팰린드롬 확인
def is_palindrome(s):
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False
4️⃣ 문자열 처리 패턴
자주 쓰는 문자열 기법들
① 슬라이딩 윈도우 (Sliding Window)
고정 크기 또는 가변 크기의 윈도우를 이동시키면서 처리하는 패턴.
# 문제: 길이 k인 부분 배열의 최대 합 찾기
def max_subarray_sum(arr, k):
# 첫 윈도우 합 계산
window_sum = sum(arr[:k])
max_sum = window_sum
# 윈도우 슬라이딩
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # 맨 앞 빼고, 새 원소 추가
max_sum = max(max_sum, window_sum)
return max_sum
arr = [2, 1, 5, 1, 3, 2]
print(max_subarray_sum(arr, 3)) # 출력: 9 (5+1+3)
예시**:** 기차 창문으로 밖을 볼 때, 창문 크기는 그대로인데 기차가 이동하는 것처럼
② 해시맵을 이용한 문자 빈도 카운팅
# 문제: 두 문자열이 애너그램인지 확인 (같은 문자 구성)
def is_anagram(s, t):
if len(s) != len(t):
return False
count = {}
for c in s:
count[c] = count.get(c, 0) + 1
for c in t:
if c not in count or count[c] == 0:
return False
count[c] -= 1
return True
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
③ 문자열 뒤집기
# 방법 1: 슬라이싱 (파이썬)
s = "hello"
reversed_s = s[::-1]
print(reversed_s) # "olleh"
# 방법 2: 투 포인터
def reverse_string(s):
s = list(s)
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
5️⃣ 기본 정렬 알고리즘 복습
버블 정렬 (Bubble Sort) - O(n²)
인접한 두 원소를 비교해서 큰 값을 오른쪽으로 밀어내는 정렬.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 시각화:
# [5, 3, 1, 4, 2]
# 1패스: [3, 1, 4, 2, 5] ← 5가 맨 끝으로
# 2패스: [1, 3, 2, 4, 5] ← 4가 자리 잡음
# ...
선택 정렬 (Selection Sort) - O(n²)
매 반복마다 최솟값을 찾아서 맨 앞과 교환하는 정렬.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
삽입 정렬 (Insertion Sort) - O(n²) / 거의 정렬된 경우 O(n)
카드 게임처럼 한 장씩 뽑아 적절한 위치에 삽입하는 정렬.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
병합 정렬 (Merge Sort) - O(n log n)
배열을 반으로 나누고 → 정렬하고 → 합치는 분할정복 방식.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
정렬 알고리즘 비교표
| 알고리즘 | 평균 시간복잡도 | 최악 | 공간복잡도 | 안정 정렬? |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | ✅ |
| 선택 정렬 | O(n²) | O(n²) | O(1) | ❌ |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | ✅ |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | ✅ |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | ❌ |
안정 정렬이란? 같은 값의 원소들이 정렬 후에도 원래 순서를 유지하는 것.
- Big-O: 코드의 시간 효율을 나타내는 표기법
→ 이중 루프 = O(n²), 단순 루프 = O(n), 인덱스 접근 = O(1) - 배열 탐색
→ 선형 탐색: O(n), 이진 탐색: O(log n) (단, 정렬된 배열만) - 투 포인터
→ 양끝에서 좁혀오는 방식으로 O(n²) → O(n) 최적화 - 문자열 패턴
→ 슬라이딩 윈도우, 해시맵 카운팅, 투 포인터 - 정렬
→ 면접 단골: 버블/선택/삽입(O(n²)) vs 병합/퀵(O(n log n))
- 연습 문제 추천
Two Sum— 해시맵 활용Valid Palindrome— 투 포인터Binary Search— 이진 탐색 기본Maximum Average Subarray I— 슬라이딩 윈도우Sort an Array— 정렬 구현 연습