파이썬 AI 알고리즘 완전 정복
파이썬으로 AI 알고리즘의 모든 것을 마스터하세요! 기초 자료구조와 정렬/탐색부터 머신러닝, 딥러닝, 트랜스포머, LLM까지 체계적으로 학습합니다. 그래프 알고리즘, 추천 엔진, 대규모 알고리즘 설계까지 실무에 필요한 핵심 알고리즘을 완벽 정복합니다.
학습 항목
본 콘텐츠의 이미지 및 내용은 AI로 생성되었습니다.
이미지 로딩 중...
알고리즘 개요와 성능 분석 완벽 가이드
알고리즘의 기본 개념부터 빅오 표기법까지, 초급 개발자가 반드시 알아야 할 알고리즘 성능 분석의 핵심을 다룹니다. 실무에서 왜 알고리즘 선택이 중요한지, 어떻게 성능을 측정하는지 쉽게 이해할 수 있습니다.
목차
1. 알고리즘이란 무엇인가
어느 날 김개발 씨가 회사에서 검색 기능을 구현하다가 문득 궁금해졌습니다. "분명히 같은 결과를 내는 코드인데, 왜 선배가 작성한 코드는 순식간에 끝나고 내 코드는 한참 걸리는 걸까?" 이 질문이야말로 알고리즘을 공부해야 하는 이유의 시작점입니다.
알고리즘은 한마디로 문제를 해결하기 위한 단계별 절차입니다. 마치 요리 레시피처럼, 정해진 순서대로 따라가면 원하는 결과를 얻을 수 있는 명확한 지침서와 같습니다.
같은 요리라도 레시피에 따라 맛과 조리 시간이 달라지듯, 같은 문제라도 알고리즘에 따라 성능이 천차만별입니다.
다음 코드를 살펴봅시다.
# 1부터 n까지 합을 구하는 두 가지 알고리즘
def sum_loop(n):
# 반복문으로 하나씩 더하기 - O(n)
total = 0
for i in range(1, n + 1):
total += i
return total
def sum_formula(n):
# 수학 공식 활용 - O(1)
# 가우스 공식: n * (n + 1) / 2
return n * (n + 1) // 2
# 같은 결과, 다른 성능
print(sum_loop(1000000)) # 느림
print(sum_formula(1000000)) # 빠름
김개발 씨는 입사 6개월 차 주니어 개발자입니다. 오늘 맡은 업무는 사용자 목록에서 특정 조건에 맞는 데이터를 찾아 출력하는 기능이었습니다.
어렵지 않은 작업이라 생각했는데, 테스트 데이터 100만 건을 넣자 프로그램이 거의 멈춘 것처럼 느려졌습니다. 옆자리 박시니어 씨가 슬쩍 화면을 들여다봅니다.
"혹시 이중 반복문 쓰고 있어요?" 김개발 씨가 고개를 끄덕이자, 박시니어 씨가 미소를 지었습니다. "알고리즘을 바꿔볼까요?" 그렇다면 알고리즘이란 정확히 무엇일까요?
쉽게 비유하자면, 알고리즘은 마치 내비게이션의 경로 안내와 같습니다. 서울에서 부산까지 가는 방법은 수십 가지가 있습니다.
고속도로를 탈 수도 있고, 국도를 이용할 수도 있으며, 해안도로를 따라 드라이브할 수도 있습니다. 모두 부산에 도착한다는 결과는 같지만, 소요 시간과 연료비는 전혀 다릅니다.
프로그래밍에서의 알고리즘도 마찬가지입니다. 1부터 100까지 더하는 문제를 생각해봅시다.
가장 단순한 방법은 1+2+3+...+100을 순서대로 계산하는 것입니다. 하지만 수학자 가우스가 어린 시절 발견했다는 공식 n*(n+1)/2를 사용하면, 단 한 번의 계산으로 같은 답을 얻을 수 있습니다.
위의 코드를 살펴보겠습니다. sum_loop 함수는 반복문을 사용합니다.
n이 100만이라면 100만 번의 덧셈을 수행해야 합니다. 반면 sum_formula 함수는 n이 얼마든 상관없이 딱 한 번의 계산으로 끝납니다.
결과는 같지만, 효율성은 하늘과 땅 차이입니다. 실제 현업에서는 이런 차이가 서비스의 생사를 가릅니다.
사용자 1000명이 동시에 검색 버튼을 누르는 상황을 상상해보세요. 비효율적인 알고리즘은 서버를 다운시킬 수 있지만, 잘 설계된 알고리즘은 쾌적한 서비스를 유지합니다.
다시 김개발 씨의 이야기로 돌아가 봅시다. 박시니어 씨의 조언대로 알고리즘을 수정하자, 10초 넘게 걸리던 작업이 0.1초 만에 끝났습니다.
"우와, 이게 같은 컴퓨터 맞아요?" 김개발 씨의 눈이 휘둥그레졌습니다. 이것이 바로 알고리즘의 힘입니다.
실전 팁
💡 - 코드를 작성하기 전에 먼저 문제 해결 방법을 종이에 그려보세요
- 같은 결과를 내는 여러 방법이 있다면, 데이터가 많아졌을 때를 기준으로 선택하세요
2. 알고리즘의 단계와 개발 환경
김개발 씨가 알고리즘의 중요성을 깨달은 후, 본격적으로 공부를 시작하려 합니다. 그런데 막상 시작하려니 막막합니다.
"알고리즘 문제를 어떻게 접근해야 하지? 그리고 어디서 연습하면 좋을까?" 박시니어 씨가 알고리즘 개발의 체계적인 단계를 알려주기로 했습니다.
알고리즘 개발은 문제 이해, 설계, 구현, 테스트, 최적화의 단계로 이루어집니다. 마치 건물을 지을 때 설계도를 먼저 그리고, 시공하고, 검수하는 것처럼 체계적인 과정이 필요합니다.
Python은 배우기 쉽고 강력한 라이브러리를 갖춰 알고리즘 학습에 최적의 환경을 제공합니다.
다음 코드를 살펴봅시다.
# 알고리즘 개발 5단계 예시: 최댓값 찾기
# 1단계: 문제 이해 - 리스트에서 가장 큰 값 찾기
numbers = [34, 12, 89, 45, 67, 23]
# 2단계: 설계 - 첫 번째 값을 최댓값으로 가정하고 순회
# 3단계: 구현
def find_max(arr):
if not arr: # 빈 리스트 예외 처리
return None
max_value = arr[0] # 첫 번째 값으로 초기화
for num in arr[1:]:
if num > max_value:
max_value = num # 더 큰 값 발견 시 갱신
return max_value
# 4단계: 테스트
result = find_max(numbers)
print(f"최댓값: {result}") # 89
# 5단계: 최적화 - 내장 함수 활용
print(f"내장 함수: {max(numbers)}") # 동일 결과
박시니어 씨가 화이트보드 앞에 섰습니다. "알고리즘을 잘 만들려면 체계적인 접근이 필요해요.
무작정 코딩부터 시작하면 나중에 꼬이기 십상이거든요." 알고리즘 개발의 첫 번째 단계는 문제 이해입니다. 놀랍게도 많은 개발자가 이 단계를 건너뜁니다.
문제가 정확히 무엇을 요구하는지, 입력은 어떤 형태인지, 출력은 무엇이어야 하는지 명확히 파악해야 합니다. 마치 의사가 진단 없이 처방을 내리지 않는 것과 같습니다.
두 번째 단계는 설계입니다. 여기서 어떤 전략으로 문제를 해결할지 큰 그림을 그립니다.
종이에 흐름도를 그리거나 의사코드를 작성하는 것이 좋습니다. 이 단계에서 시간을 투자하면 구현 단계에서 헤매는 시간을 크게 줄일 수 있습니다.
세 번째는 구현 단계입니다. 설계한 내용을 실제 코드로 옮기는 과정입니다.
Python은 이 단계에서 빛을 발합니다. 직관적인 문법 덕분에 알고리즘의 논리에 집중할 수 있기 때문입니다.
네 번째 단계인 테스트는 절대 생략해서는 안 됩니다. 정상적인 입력뿐 아니라, 빈 리스트, 음수, 아주 큰 값 등 경계 조건도 확인해야 합니다.
버그는 대부분 예상치 못한 입력에서 발생합니다. 마지막 최적화 단계에서는 더 나은 방법이 있는지 검토합니다.
때로는 Python의 내장 함수가 이미 최적화되어 있어 직접 구현한 것보다 빠를 수 있습니다. Python이 알고리즘 학습에 좋은 이유는 명확합니다.
문법이 영어 문장처럼 읽히고, 동적 타이핑으로 빠르게 실험할 수 있으며, Jupyter Notebook 같은 도구로 단계별 실행 결과를 바로 확인할 수 있습니다. 김개발 씨가 고개를 끄덕입니다.
"그러니까 코딩 전에 충분히 생각하는 시간이 오히려 전체 시간을 줄여주는 거군요." 박시니어 씨가 미소 지었습니다. "바로 그거예요.
급하면 돌아가라는 말이 알고리즘에도 적용돼요."
실전 팁
💡 - 코딩 전에 5분만 종이에 설계를 해보면 30분의 디버깅 시간을 아낄 수 있습니다
- Jupyter Notebook을 활용하면 알고리즘의 각 단계를 시각적으로 확인할 수 있습니다
3. SciPy 생태계 소개
알고리즘 공부를 시작한 김개발 씨가 인터넷을 검색하다 보니 NumPy, SciPy, Pandas 같은 이름들이 계속 등장합니다. "이게 다 뭐지?
왜 Python 알고리즘을 공부하는데 이런 라이브러리들이 중요하다는 거지?" 선배에게 물어보기로 했습니다.
SciPy 생태계는 Python에서 과학 계산과 데이터 분석을 위한 핵심 라이브러리 모음입니다. NumPy는 고속 배열 연산을, SciPy는 과학 계산 알고리즘을, Pandas는 데이터 처리를 담당합니다.
마치 주방에서 칼, 도마, 냄비가 각자의 역할을 하듯, 이들은 함께 강력한 도구 세트를 이룹니다.
다음 코드를 살펴봅시다.
import numpy as np
# NumPy 배열 - 빠른 연산의 핵심
# 일반 리스트 vs NumPy 배열 성능 비교
python_list = list(range(1000000))
numpy_array = np.arange(1000000)
# NumPy는 C로 구현되어 훨씬 빠름
# 모든 요소에 2 곱하기
result_numpy = numpy_array * 2 # 벡터 연산, 매우 빠름
# 통계 연산도 간단하게
data = np.array([23, 45, 67, 89, 12, 34, 56])
print(f"평균: {np.mean(data)}") # 46.57...
print(f"표준편차: {np.std(data)}") # 24.69...
print(f"최댓값 인덱스: {np.argmax(data)}") # 3
# 정렬 알고리즘도 내장
sorted_data = np.sort(data) # 최적화된 정렬
print(f"정렬: {sorted_data}") # [12, 23, 34, 45, 56, 67, 89]
박시니어 씨가 커피 한 잔을 건네며 설명을 시작했습니다. "Python이 알고리즘 분야에서 인기 있는 이유 중 하나가 바로 SciPy 생태계예요." NumPy는 이 생태계의 기초입니다.
Numerical Python의 약자로, 대규모 다차원 배열과 행렬 연산에 특화되어 있습니다. 순수 Python 리스트로 100만 개 숫자를 더하면 제법 시간이 걸리지만, NumPy 배열은 순식간에 처리합니다.
비밀은 내부가 C 언어로 구현되어 있기 때문입니다. SciPy는 NumPy 위에 구축된 과학 계산 라이브러리입니다.
최적화, 선형대수, 적분, 보간, 신호처리 등 고급 알고리즘이 이미 구현되어 있습니다. 바퀴를 다시 발명할 필요 없이 검증된 알고리즘을 바로 사용할 수 있습니다.
Pandas는 데이터 분석의 스위스 아미 나이프입니다. 엑셀 같은 표 형태의 데이터를 다루는 데 최적화되어 있습니다.
CSV 파일을 읽고, 필터링하고, 집계하는 작업이 몇 줄의 코드로 가능합니다. 위의 코드에서 NumPy의 강력함을 확인할 수 있습니다.
numpy_array * 2라는 한 줄로 100만 개 요소 모두에 2를 곱합니다. 이것을 벡터 연산이라고 하는데, 반복문 없이도 모든 요소에 동시에 연산을 적용합니다.
김개발 씨가 질문했습니다. "그러면 항상 NumPy를 써야 하나요?" 박시니어 씨가 고개를 저었습니다.
"아니요, 작은 데이터나 단순한 작업에는 일반 리스트가 더 나을 수도 있어요. NumPy는 배열 생성 자체에 오버헤드가 있거든요.
데이터가 수천, 수만 개 이상일 때 진가를 발휘해요." 실무에서 이 생태계는 필수입니다. 머신러닝 라이브러리인 scikit-learn, 딥러닝의 TensorFlow와 PyTorch 모두 NumPy 배열을 기본 데이터 구조로 사용합니다.
알고리즘을 공부하면서 이 생태계에 익숙해지면, 나중에 더 고급 주제로 나아갈 때 큰 도움이 됩니다.
실전 팁
💡 - 대용량 데이터를 다룬다면 NumPy 배열을 사용하세요. 일반 리스트보다 수십 배 빠릅니다
- np.vectorize()를 사용하면 일반 함수도 배열 전체에 적용할 수 있습니다
4. 데이터 차원과 계산 차원
김개발 씨가 코드를 짜다가 이상한 현상을 발견했습니다. 데이터 10개를 처리할 때는 0.01초였는데, 데이터 100개를 처리하니 10초나 걸립니다.
"10배 늘었으니까 0.1초여야 하는 거 아닌가요?" 박시니어 씨가 웃으며 말했습니다. "그건 데이터 차원과 계산 차원을 구분해야 이해할 수 있어요."
데이터 차원은 입력 데이터의 크기와 구조를 의미하고, 계산 차원은 알고리즘이 수행하는 연산의 복잡도를 나타냅니다. 마치 책의 두께(데이터)와 책을 읽는 방식(계산)이 다른 것처럼, 이 둘을 구분하면 알고리즘 성능을 정확히 분석할 수 있습니다.
다음 코드를 살펴봅시다.
# 데이터 차원 vs 계산 차원 이해하기
# 1차원 데이터 - 리스트
data_1d = [1, 2, 3, 4, 5] # n개 요소
# 2차원 데이터 - 행렬
data_2d = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
] # n x m 요소
# 계산 차원 예시: 같은 데이터, 다른 계산량
def linear_search(arr, target):
# O(n) - 데이터 크기에 비례
for i, val in enumerate(arr):
if val == target:
return i
return -1
def all_pairs(arr):
# O(n^2) - 데이터 크기의 제곱에 비례
pairs = []
for i in arr:
for j in arr:
pairs.append((i, j))
return pairs
# n=5일 때: 검색은 최대 5번, 쌍 만들기는 25번
print(f"검색 결과: {linear_search(data_1d, 3)}")
print(f"모든 쌍 개수: {len(all_pairs(data_1d))}") # 25
박시니어 씨가 칠판에 표를 그리기 시작했습니다. "먼저 데이터 차원부터 이해해봅시다." 데이터 차원은 우리가 다루는 입력의 형태입니다.
숫자 하나하나가 나열된 리스트는 1차원입니다. 행과 열로 이루어진 표 형태는 2차원이고, 이런 표가 여러 장 겹쳐진 형태는 3차원입니다.
영상 데이터를 생각하면 쉽습니다. 사진 한 장은 2차원이고, 동영상은 시간 축이 추가되어 3차원이 됩니다.
계산 차원은 이 데이터를 처리하는 데 필요한 연산의 양입니다. 여기서 중요한 점은 데이터 크기와 계산량이 항상 비례하지 않는다는 것입니다.
김개발 씨의 상황을 분석해봅시다. 코드에 이중 반복문이 있다면, 데이터가 10개일 때 연산은 10 x 10 = 100번입니다.
데이터가 100개가 되면? 100 x 100 = 10,000번입니다.
데이터는 10배 늘었는데 계산량은 100배 늘어난 것입니다. 위의 코드에서 linear_search 함수는 데이터를 한 번씩만 살펴봅니다.
데이터가 n개면 최대 n번 연산합니다. 이런 경우 선형으로 증가한다고 합니다.
반면 all_pairs 함수는 모든 요소를 다른 모든 요소와 짝짓습니다. n개 데이터에 대해 n x n번 연산하므로, 제곱으로 증가합니다.
실무에서 이 개념이 왜 중요할까요? 테스트 환경에서는 데이터가 적어서 문제가 없던 코드가, 실제 서비스에서 데이터가 많아지면 급격히 느려지는 경우가 많습니다.
이때 데이터 차원과 계산 차원을 이해하고 있어야 원인을 빠르게 파악할 수 있습니다. 김개발 씨가 무릎을 쳤습니다.
"아, 그래서 제 코드가 그렇게 느려진 거군요. 이중 반복문 안에 또 다른 연산이 있었거든요." 박시니어 씨가 고개를 끄덕였습니다.
"맞아요. 그래서 알고리즘을 선택할 때는 데이터가 커졌을 때 어떻게 될지 미리 생각해야 해요."
실전 팁
💡 - 반복문이 중첩될수록 계산량이 기하급수적으로 늘어납니다. 가능하면 중첩을 줄이세요
- 작은 테스트 데이터에서 잘 작동해도, 실제 데이터 규모로 테스트하는 것이 중요합니다
5. 공간 복잡도와 시간 복잡도
김개발 씨가 메모리 부족 에러를 만났습니다. 분명히 로직은 맞는 것 같은데, 큰 데이터를 넣으니 프로그램이 멈춰버립니다.
"속도만 신경 썼는데, 메모리도 문제가 될 수 있군요." 박시니어 씨가 알고리즘의 두 가지 성능 척도에 대해 설명해주기로 했습니다.
시간 복잡도는 알고리즘이 얼마나 빨리 실행되는지, 공간 복잡도는 얼마나 많은 메모리를 사용하는지를 나타냅니다. 마치 출퇴근할 때 시간과 교통비를 모두 고려해야 하듯, 좋은 알고리즘은 두 가지 모두를 균형 있게 관리해야 합니다.
다음 코드를 살펴봅시다.
# 시간 복잡도 vs 공간 복잡도 트레이드오프
# 방법 1: 공간 절약, 시간 소모
def has_duplicate_slow(arr):
# 공간: O(1) - 추가 메모리 거의 없음
# 시간: O(n^2) - 모든 쌍 비교
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False
# 방법 2: 시간 절약, 공간 소모
def has_duplicate_fast(arr):
# 공간: O(n) - 집합에 모든 요소 저장 가능
# 시간: O(n) - 한 번만 순회
seen = set()
for num in arr:
if num in seen:
return True
seen.add(num)
return False
# 테스트
data = [1, 2, 3, 4, 5, 3, 6, 7]
print(f"중복 있음 (느린 방법): {has_duplicate_slow(data)}")
print(f"중복 있음 (빠른 방법): {has_duplicate_fast(data)}")
박시니어 씨가 커피잔을 내려놓으며 말했습니다. "알고리즘의 성능을 이야기할 때는 두 가지 관점이 있어요.
얼마나 빠른가, 그리고 얼마나 많은 공간을 차지하는가." 시간 복잡도는 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 나타냅니다. 데이터가 2배가 되면 시간도 2배가 되는지, 아니면 4배가 되는지를 분석합니다.
사용자는 빠른 응답을 원하기 때문에, 시간 복잡도는 사용자 경험에 직접적인 영향을 미칩니다. 공간 복잡도는 알고리즘이 사용하는 메모리의 양입니다.
입력 데이터 외에 추가로 필요한 메모리가 얼마나 되는지를 분석합니다. 메모리는 무한하지 않기 때문에, 큰 데이터를 다룰 때는 공간 복잡도도 중요합니다.
흥미로운 점은 이 둘이 종종 트레이드오프 관계라는 것입니다. 위의 코드를 보면, has_duplicate_slow 함수는 추가 메모리를 거의 사용하지 않지만 느립니다.
반면 has_duplicate_fast 함수는 집합(set)이라는 추가 공간을 사용하지만 훨씬 빠릅니다. 비유하자면, 마트에서 물건을 찾을 때와 비슷합니다.
첫 번째 방법은 마트를 여러 번 돌아다니며 직접 찾는 것입니다. 시간은 오래 걸리지만 메모장이 필요 없습니다.
두 번째 방법은 미리 메모장에 본 물건을 기록해두는 것입니다. 메모장 공간이 필요하지만 중복을 빠르게 발견할 수 있습니다.
실무에서는 상황에 따라 선택이 달라집니다. 메모리가 넉넉한 서버에서는 빠른 알고리즘을, 메모리가 제한된 임베디드 시스템에서는 공간 효율적인 알고리즘을 선택합니다.
김개발 씨가 이해했다는 표정을 지었습니다. "그러니까 항상 빠른 게 좋은 건 아니고, 상황에 맞게 선택해야 하는 거군요." 박시니어 씨가 고개를 끄덕였습니다.
"맞아요. 그래서 좋은 개발자는 여러 가지 알고리즘을 알고, 상황에 맞게 고를 줄 알아야 해요."
실전 팁
💡 - 메모리가 충분하다면 시간을 우선시하고, 메모리가 제한적이라면 공간 효율을 고려하세요
- 캐싱은 대표적인 공간-시간 트레이드오프입니다. 메모리를 더 써서 속도를 높이는 기법입니다
6. 빅오 표기법
김개발 씨가 기술 면접을 준비하다가 벽에 부딪혔습니다. "이 알고리즘의 시간 복잡도가 뭐예요?" 면접에서 이 질문을 받으면 어떻게 대답해야 할지 막막합니다.
박시니어 씨가 개발자의 공용어인 빅오 표기법을 알려주기로 했습니다.
**빅오 표기법(Big-O notation)**은 알고리즘의 성능을 간결하게 표현하는 수학적 표기법입니다. 입력 크기 n이 커질 때 연산 횟수가 어떻게 증가하는지를 나타냅니다.
마치 "이 차는 연비가 좋다/나쁘다"처럼, 알고리즘의 효율성을 한눈에 비교할 수 있게 해줍니다.
다음 코드를 살펴봅시다.
import time
# O(1) - 상수 시간: 입력 크기와 무관
def get_first(arr):
return arr[0] if arr else None # 항상 한 번
# 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
# O(n) - 선형 시간: 입력에 비례
def find_max(arr):
max_val = arr[0]
for num in arr: # n번 반복
if num > max_val:
max_val = num
return max_val
# O(n^2) - 제곱 시간: 중첩 반복
def bubble_sort(arr):
n = len(arr)
for i in range(n): # n번
for j in range(n-1): # n번 -> n * n
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 성능 비교 출력
print("O(1): 배열 크기와 무관하게 즉시")
print("O(log n): 100만 개 데이터도 약 20번 연산")
print("O(n): 100만 개면 100만 번 연산")
print("O(n^2): 100만 개면 1조 번 연산!")
박시니어 씨가 화이트보드에 그래프를 그리기 시작했습니다. "빅오는 개발자들이 알고리즘 성능을 이야기할 때 사용하는 공통 언어예요.
면접에서도 자주 나오고, 실무에서도 자주 쓰이죠." **O(1)**은 상수 시간입니다. 입력이 10개든 1억 개든 실행 시간이 동일합니다.
배열의 첫 번째 요소를 가져오는 것이 대표적입니다. 마치 책의 첫 페이지를 펴는 것과 같습니다.
책이 100페이지든 10000페이지든 첫 페이지를 펴는 시간은 같습니다. **O(log n)**은 로그 시간입니다.
입력이 2배가 되어도 연산은 1회만 더 늘어납니다. 이진 탐색이 대표적입니다.
정렬된 전화번호부에서 이름을 찾을 때, 중간을 펴서 알파벳 순서를 비교하고, 앞쪽이나 뒤쪽 절반만 다시 살펴보는 방식입니다. 100만 개 데이터에서도 약 20번의 비교로 원하는 값을 찾을 수 있습니다.
**O(n)**은 선형 시간입니다. 입력이 n배가 되면 시간도 n배가 됩니다.
정렬되지 않은 리스트에서 최댓값을 찾으려면 모든 요소를 한 번씩 확인해야 합니다. 공평하고 예측 가능한 복잡도입니다.
**O(n제곱)**은 제곱 시간입니다. 입력이 10배가 되면 시간은 100배가 됩니다.
버블 정렬처럼 이중 반복문을 사용하는 알고리즘이 여기에 해당합니다. 작은 데이터에서는 괜찮지만, 데이터가 커지면 급격히 느려집니다.
숫자로 비교해보면 그 차이가 명확합니다. n이 100만일 때, O(1)은 1번, O(log n)은 약 20번, O(n)은 100만 번, O(n제곱)은 1조 번의 연산을 수행합니다.
김개발 씨가 놀란 표정을 지었습니다. "1조 번이요?
그러면 평생 걸리겠네요." 박시니어 씨가 웃었습니다. "바로 그래서 알고리즘 선택이 중요한 거예요.
똑같은 문제를 O(n log n) 정렬 알고리즘으로 풀면 약 2000만 번이면 끝나거든요."
실전 팁
💡 - 면접에서 빅오를 물으면 최악의 경우를 기준으로 답하세요
- 중첩 반복문의 깊이가 곧 n의 지수입니다. 이중 반복문은 O(n제곱), 삼중은 O(n세제곱)입니다
7. 알고리즘 선택과 검증 방법
김개발 씨가 이제 빅오 표기법도 알고, 여러 알고리즘도 배웠습니다. 그런데 막상 실무 문제를 마주하니 또 고민이 생깁니다.
"어떤 알고리즘을 써야 할지 어떻게 결정하죠? 그리고 선택한 알고리즘이 정말 올바른지는 어떻게 확인하나요?"
알고리즘 선택은 데이터 특성, 성능 요구사항, 구현 복잡도를 종합적으로 고려해야 합니다. 선택 후에는 다양한 테스트 케이스로 정확성을 검증하고, 실제 데이터 규모로 성능을 측정해야 합니다.
마치 자동차를 고를 때 용도, 예산, 연비를 모두 따지는 것처럼 말입니다.
다음 코드를 살펴봅시다.
import time
import random
def measure_time(func, *args):
"""함수 실행 시간 측정"""
start = time.time()
result = func(*args)
end = time.time()
return result, end - start
# 테스트 케이스로 정확성 검증
def test_sort_algorithm(sort_func):
# 경계 조건 테스트
assert sort_func([]) == [] # 빈 리스트
assert sort_func([1]) == [1] # 단일 요소
assert sort_func([2, 1]) == [1, 2] # 두 요소
# 일반 케이스
assert sort_func([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5]
# 이미 정렬된 경우
assert sort_func([1, 2, 3]) == [1, 2, 3]
# 역순 정렬된 경우
assert sort_func([3, 2, 1]) == [1, 2, 3]
print("모든 테스트 통과!")
# 성능 테스트
def benchmark_search(n):
data = list(range(n))
target = n - 1 # 최악의 경우
# 선형 검색 vs 이진 검색
_, linear_time = measure_time(lambda: target in data)
_, binary_time = measure_time(binary_search, data, target)
print(f"n={n:,}: 선형 {linear_time:.6f}s, 이진 {binary_time:.6f}s")
# 이진 검색 함수 (정렬된 배열 필요)
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
박시니어 씨가 마지막 수업이라며 진지한 표정으로 말했습니다. "지금까지 배운 것들을 종합하는 시간이에요.
실무에서 알고리즘을 어떻게 선택하고 검증하는지 알려드릴게요." 알고리즘 선택의 첫 번째 기준은 데이터 특성입니다. 데이터가 이미 정렬되어 있나요?
중복이 있나요? 크기는 얼마나 되나요?
예를 들어 정렬된 데이터에서 검색한다면 이진 검색이 탁월합니다. 하지만 정렬되지 않은 데이터라면 먼저 정렬 비용을 고려해야 합니다.
두 번째 기준은 성능 요구사항입니다. 응답 시간이 1초 이내여야 하나요?
메모리 사용량에 제한이 있나요? 실시간 처리가 필요한 게임 서버와, 밤새 돌려도 되는 배치 작업은 요구사항이 완전히 다릅니다.
세 번째 기준은 구현 복잡도입니다. 완벽한 알고리즘이라도 구현이 너무 복잡하면 버그가 생기기 쉽습니다.
때로는 조금 느리더라도 단순하고 검증된 알고리즘이 더 나은 선택일 수 있습니다. 알고리즘을 선택했다면 이제 검증 단계입니다.
위의 코드처럼 다양한 테스트 케이스를 준비해야 합니다. 특히 경계 조건이 중요합니다.
빈 입력, 단일 요소, 아주 큰 값, 음수 등 특수한 상황에서 제대로 동작하는지 확인해야 합니다. 성능 테스트도 필수입니다.
작은 데이터에서는 모든 알고리즘이 빨라 보입니다. 실제 서비스 규모의 데이터로 테스트해야 진짜 성능을 알 수 있습니다.
위 코드의 measure_time 함수처럼 실행 시간을 측정하는 습관을 들이세요. 김개발 씨가 정리하듯 말했습니다.
"정리하면, 먼저 데이터와 요구사항을 파악하고, 적절한 알고리즘을 선택하고, 다양한 케이스로 테스트하고, 실제 규모로 성능을 확인하는 거군요." 박시니어 씨가 흐뭇한 미소를 지었습니다. "맞아요.
알고리즘은 외우는 게 아니라 이해하는 거예요. 원리를 이해하면 새로운 문제도 풀 수 있고, 적절한 도구를 선택할 수 있게 되죠.
오늘 배운 내용이 개발자로서의 기초 체력이 될 거예요."
실전 팁
💡 - 항상 경계 조건(빈 입력, 최댓값, 최솟값)을 테스트하세요
- 실제 서비스 데이터 규모로 성능을 측정해야 프로덕션에서의 문제를 예방할 수 있습니다
- 처음에는 단순한 알고리즘으로 시작하고, 성능 문제가 발생하면 최적화하세요
이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!