[정글 베이직 7] Big O 복잡도 분석 — 배열에서 중복 원소 찾기

 

크래프톤 정글  ·  베이직 7

Big O — 같은 문제,
다른 속도

BRUTE FORCE   O(n²)

for i in range(n):
  for j in range(i+1, n):
    if nums[i] == nums[j]:
      ...
# 모든 쌍을 비교

→

HASH SET   O(n)

for num in nums:
  if num in seen:
    duplicates.add(num)
  else:
    seen.add(num)
# 배열을 한 번만 순회

cedis  ·  2026.3.8

이번 주제는 복잡도 분석이다.
코드가 동작하는 건 당연한 거고, 이제부터는 "얼마나 빠르게, 얼마나 적은 메모리로" 동작하는지를 따져야 한다.

배열에서 중복 원소를 찾는 딱 하나의 문제를 3가지 방법으로 풀면서 시간복잡도와 공간복잡도가 어떻게 달라지는지 직접 확인해보자.

문제 소개

정수 배열에서 두 번 이상 등장하는 원소를 모두 찾아 반환하는 것.

항목	내용
입력	[4, 3, 2, 7, 8, 2, 3, 1]
출력	[2, 3]
핵심 도구	반복문, 정렬, set

📌

이번 챕터의 핵심 키워드: Big O 표기법, O(n²) / O(n log n) / O(n), 시간-공간 트레이드오프

Big O 표기법이란

코드를 실제로 실행해서 시간을 재는 게 아니라, 입력 크기 n이 커질수록 얼마나 느려지는지를 수학적으로 표현하는 방법이다.
빠른 순서로 정렬하면 이렇다.

표기법	이름	예시 연산	n = 1,000,000 기준
O(1)	상수	배열 인덱스 접근	즉시
O(n)	선형	배열 한 번 순회	빠름
O(n log n)	선형로그	정렬(sort)	보통
O(n²)	이차	이중 반복문	느림 / 사실상 불가

⚠️

n = 1,000,000 일 때 O(n²)은 이론상 10¹²번 연산이 필요하다. 현실에서는 실행이 불가능한 수준이다.

방법 1 — Brute Force (이중 반복문)

find_duplicates_brute_force()

시간 O(n²) 공간 O(1)

 

python

def find_duplicates_brute_force(nums): duplicates = [] n = len(nums) for i in range(n): # 기준 원소 for j in range(i + 1, n): # 기준 이후 모든 원소 if nums[i] == nums[j]: if nums[i] not in duplicates: # 중복 추가 방지 duplicates.append(nums[i]) return duplicates

핵심 아이디어: i번째 원소를 기준으로 잡고, 그 뒤에 있는 모든 원소와 하나씩 비교한다.

• 1i = 0 → nums[0]을 nums[1], nums[2], ..., nums[n-1]과 비교
• 2i = 1 → nums[1]을 nums[2], ..., nums[n-1]과 비교
• 3같은 값 발견 시 duplicates에 없는 경우만 추가

# nums = [4, 3, 2, 7, 8, 2, 3, 1] i=0 (4) vs 3, 2, 7, 8, 2, 3, 1 → 일치 없음 i=1 (3) vs 2, 7, 8, 2, 3, 1 → 3 발견 → [3] i=2 (2) vs 7, 8, 2, 3, 1 → 2 발견 → [3, 2] ... 결과: [3, 2] → sorted: [2, 3]

⚠️

중복 추가 방지가 필요한 이유: [2, 2, 2]처럼 같은 값이 세 번 나오면 비교가 여러 번 일치해서 [2, 2]가 될 수 있다. if nums[i] not in duplicates: 조건으로 막아야 한다.

🐌

n = 8이면 최대 28번 비교. n = 1,000이면 약 50만 번. n = 1,000,000이면 약 5 × 10¹¹번 — 현실적으로 불가능하다.

방법 2 — 정렬 후 비교 (Sorting)

find_duplicates_sorting()

시간 O(n log n) 공간 O(1)

 

python

def find_duplicates_sorting(nums): if not nums: return [] nums.sort() # in-place 정렬 → O(n log n) duplicates = [] for i in range(len(nums) - 1): # 인접 원소 비교 if nums[i] == nums[i + 1]: if nums[i] not in duplicates: duplicates.append(nums[i]) return duplicates

핵심 아이디어: 정렬하면 중복은 항상 옆에 붙는다. 인접한 원소만 비교하면 된다.

# 정렬 전: [4, 3, 2, 7, 8, 2, 3, 1] # 정렬 후: [1, 2, 2, 3, 3, 4, 7, 8] i=0: 1 vs 2 → 다름 i=1: 2 vs 2 → 중복! → [2] i=2: 2 vs 3 → 다름 i=3: 3 vs 3 → 중복! → [2, 3] i=4: 3 vs 4 → 다름 ...

💡

nums.sort() vs sorted(nums) 차이
nums.sort() — 원본 리스트 자체를 정렬 (in-place, 반환값 없음)
sorted(nums) — 원본은 그대로 두고 새로운 정렬된 리스트 반환

왜 O(n log n)?
정렬 자체가 전체에서 가장 무거운 단계다. 그 뒤의 순회는 O(n)이지만 더 큰 항이 전체 복잡도를 결정한다. O(n log n) + O(n) = O(n log n).

방법 3 — 해시 집합 (Hash / Set)

find_duplicates_hash()

시간 O(n) 공간 O(n)

 

python

def find_duplicates_hash(nums): seen = set() # 지금까지 본 숫자 duplicates = set() # 중복으로 발견된 숫자 for num in nums: if num in seen: duplicates.add(num) # 이미 봤다 → 중복 else: seen.add(num) # 처음 본다 → 기록 return list(duplicates)

핵심 아이디어: 한 번 본 숫자를 seen set에 기록해두고, 다시 만나면 중복으로 판정한다. 배열을 딱 한 번만 순회한다.

# nums = [4, 3, 2, 7, 8, 2, 3, 1] 4 → seen = {4} 3 → seen = {4, 3} 2 → seen = {4, 3, 2} 7 → seen = {4, 3, 2, 7} 8 → seen = {4, 3, 2, 7, 8} 2 → seen에 있음! → duplicates = {2} 3 → seen에 있음! → duplicates = {2, 3} 1 → seen = {4, 3, 2, 7, 8, 1} 결과: [2, 3]

💡

set의 in 검사가 O(1)인 이유
set은 내부적으로 해시 테이블로 구현되어 있어 값의 위치를 계산으로 바로 찾아낸다. list의 in은 처음부터 끝까지 순회해서 O(n)이지만, set은 평균 O(1)이다.

⚠️

공간복잡도가 O(n)인 이유: seen에 최악의 경우 n개의 숫자가 모두 저장될 수 있다. 빠른 대신 메모리를 더 쓰는 트레이드오프다.

실행 결과

 

python

if __name__ == "__main__": nums = [4, 3, 2, 7, 8, 2, 3, 1] r1 = find_duplicates_brute_force(nums[:]) r2 = find_duplicates_sorting(nums[:]) r3 = find_duplicates_hash(nums[:]) print(f"방법1 (O(n²)) : {sorted(r1)}") print(f"방법2 (O(n log n)): {sorted(r2)}") print(f"방법3 (O(n)) : {sorted(r3)}")

 

output

방법1 (O(n²)) : [2, 3] 방법2 (O(n log n)): [2, 3] 방법3 (O(n)) : [2, 3]

복잡도 비교 정리

방법	시간 복잡도	공간 복잡도	특징
Brute Force 이중 반복문	O(n²)	O(1)	구현 단순. 큰 입력엔 사용 불가
Sorting 정렬 후 인접 비교	O(n log n)	O(1)	추가 메모리 없음. 메모리 제한 상황에 유리
Hash / Set 해시 집합	O(n)	O(n)	가장 빠름. 메모리를 추가로 사용

상황별 선택 가이드

🧠 메모리가 제한될 때

Sorting 방법 선택.
in-place 정렬로 추가 메모리 없이 O(n log n) 해결.

⚡ 속도가 최우선일 때

Hash 방법 선택.
O(n)으로 가장 빠름. 메모리 여유가 있을 때 사용.

❌

Brute Force는 언제 쓰나? 배열 크기가 작거나 (n < 100 정도), 빠르게 동작 검증이 필요할 때만. n = 1,000,000 이상이면 절대 사용하지 않는다.

---

파이썬 문법 핵심 정리

이번 문제에서 나온 주요 문법들.

len(nums)

리스트의 길이(원소 개수) 반환

for i in range(n)

0부터 n-1까지 정수 반복

for num in nums

리스트의 원소를 하나씩 순회

nums.sort()

원본 리스트 자체를 오름차순 정렬 (in-place)

sorted(nums)

원본은 그대로, 새로운 정렬된 리스트 반환

x in s

리스트/set s 안에 x가 있는지 검사 (True/False)

x not in s

리스트/set s 안에 x가 없는지 검사

list.append(x)

리스트 끝에 x 추가

set.add(x)

set에 x 추가 (이미 있으면 무시)

list(duplicates)

set을 list로 변환

#Python #알고리즘 #BigO #시간복잡도 #자료구조 #크래프톤정글 #베이직7

cedis  ·  2026.03.08