안녕하세요, 오늘은 알고리즘 문제를 풀면서, 코드를 짤 때 효율적인 알고리즘 구현 방법에 대해 고민을 하면서 정리한 알고리즘 시간 복잡도(Time Complexity)의 개념을 정리하려고 합니다.
알고리즘 문제를 풀다 보면 위 사진과 같이 '시간 초과' 메시지를 종종 마주하게 됩니다. 또는 통과한 문제라고 하더라도 실행 시간 최적화를 생각하는 것이 실제로 개발할 때도 중요하다는 것을 느끼게 됩니다. 알고리즘을 처음 배우고 문제를 풀 때는 시간 복잡도를 생각하지 않고, 문제를 해결하는 것만 생각했습니다. 그러나 알고리즘 실력이 점차 늘고 그에 따라 시간 복잡도를 고민해야 하는 문제를 마주하면서 자연스레 효율적인 코드에 대해 고민하게 되었습니다.
'효율적인 방법'을 고민한다는 말은 실행 시간을 단축시키는 방법에 대해 고민한다는 의미입니다. 그래서 아래에서 시간 복잡도와 Big-O(빅-오) 표기법, 알고리즘 코드에서 실행 시간을 단축시키는 방법에 대해 알아보려고 합니다.
1. 시간 복잡도(Time Complexity)가 뭐야?
시간 복잡도를 한 마디로 정의하자면 입력값의 변화에 따라 연산을 수행하는 시간이 얼마나 걸리는지 나타내는 것이라고 할 수 있습니다. 입력 값이 수백 ~ 수천일 때는 시간 복잡도를 깊이 있게 고민하지 않았지만 실제로 방대한 양의 데이터는 수만 ~ 수억 개의 데이터를 처리해야 합니다. 바꾸어 말하면 입력값이 커짐에 따라 연산 처리 시간의 양을 최소화 하는 방법에 대한 고민이 필수적입니다.
시간 복잡도는 주로 Big-O 표기법을 사용해서 나타내는데요, Big-O 표기법에 대해 알아보기 전에 시간 복잡도를 표기하는 다른 방법은 어떤 것이 있는지 알아볼까요?
2. 시간 복잡도 표기 방법
(1) Big-Ω(빅-오메가): 하한 점근
시간 복잡도 최선의 경우를 고려할 때 빅-오메가로 표기합니다. 예를 들어 어떤 연산을 수행하는데 드는 시간이 최선의 경우에 0.01초, 평균 1초, 최악의 경우 1시간이 걸린다고 가정해보겠습니다. 이 연산을 100번 수행했을 때 최선의 경우에 1초(= 0.01초 * 100번)이 걸립니다.
다만 빅-오메가로 접근했을 때 100번 연산에 소요된 시간이 한 시간이 넘게 걸렸다면 어디서 문제가 발생한 건지 파악하기 위해서 알고리즘의 로직을 분석해야 하므로 빅-오메가 방법으로 접근하는 것은 추천하지 않습니다.
(2) Big-Θ(빅-세타): 연산 처리 시간 평균
그렇다면 연산 처리 시간의 평균적인 복잡도를 고려하는 방법이 빅-오메가 접근법보다 효과적이지 않을까요? 빅-세타 접근법은 연산 처리에 걸린 시간 복잡도의 평균값을 고려하는 접근법입니다.
그러나 빅-세타 접근법은 예상한 것과는 달리 컴퓨터 프로세싱 처리 능력, 여러 가지 환경 변수에 영향을 받기 때문에 최적화를 기대하기 어려운 방법입니다. 위의 빅-오메가 접근법과 마찬가지로 최악의 경우가 몇 가지만 포함되더라도 알고리즘의 로직을 분석해야 하는 문제가 생기므로 결국 빅-세타 방법도 선호되는 방식은 아닙니다.
(3) Big-O(빅-오): 상한 점근
위에서 알아본 빅-오메가, 빅-세타 접근법의 단점을 고려해 빅-오 접근법이 시간 복잡도를 고려할 때 가장 선호되는 방식입니다. 빅-오 접근법은 프로그램 실행에 소요되는 최악의 경우를 고려한 방법으로 "이 정도 시간까지 걸린다"는 것을 고려하는 방법입니다.
빅-오 표기법은 입력값의 변화에 따라, 특히 극단적인 케이스를 고려해서 입력값의 변화에 따른 연산 횟수와 그에 따른 처리 시간이 얼마나 걸리는지를 표기하는 방법입니다.
3. Big-O 표기법의 종류
그래프 우측을 보면 연산의 시간 복잡도에 따라 붉은 영역에 있는(그래프 접선의 기울기가 상대적으로 큰) 방법은 입력값의 크기에 따라 연산 시간이 오래 걸리는 방법이고, 가로축에 가까울수록 시간 복잡도가 낮은 방법이라는 것을 알 수 있습니다.
(1) O(1)
O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다. 바꾸어 말하면 입력값의 크기에 관계없이 출력값을 얻어내는데 걸리는 시간이 일정하다는 의미입니다.
O(1)의 시간 복잡도를 가지는 알고리즘
# 파이썬 코드
def big_o_1_algorithm(arr, idx):
return arr[idx]
graph = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
number = 3
result = big_o_1_algorithm(graph, number)
print(result) # 3
위 알고리즘에서는 입력값의 크기에 관계 없이 출력값을 얻어내는데 걸리는 시간이 일정합니다. 위 예시의 graph에 들어간 값의 개수가 100억 개라고 하더라도 결과를 얻는데 걸리는 시간은 위 코드와 차이가 없습니다. (배열의 인덱스에 접근해서 인덱스에 해당하는 배열의 값을 출력하는 알고리즘)
(2) O(log n)
O(log n)은 로그 복잡도(logarithmic complexity)라고 부릅니다. Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가집니다. 입력 데이터 중 경우의 수를 절반으로 줄이면서 해답을 찾는 이진 탐색(Binary Search) 알고리즘의 경우 O(log n) 시간 복잡도를 가집니다.
대표적인 로그 복잡도를 가진 알고리즘의 예시는 이진 탐색 트리(Binary Search Tree, BST)입니다(이진 탐색 트리 위키 백과 링크). 이진 탐색 트리에서는 원하는 값을 탐색할 때 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는 특징을 가집니다. (이진 탐색 트리는 왼쪽 자식 노드는 부모 노드보다 값이 작고, 오른쪽 자식 노드는 부모 노드보다 값이 큽니다. 따라서 찾고자 하는 값의 경우의 수를 한 번 탐색이 진행될 때마다 절반으로 줄일 수 있습니다.)
(3) O(n)
O(n)은 선형 복잡도(linear complexity)라고 부릅니다. 입력값이 증가함에 따라 시간이 같은 비율로 증가하는 것을 의미합니다.
예를 들어 입력값이 1개 있을 때 1초의 시간이 걸리고, 입력값을 100배 증가시켰을 때 처리 시간이 같은 비율로 늘어나 100초가 걸린다면 그 알고리즘은 O(n)의 시간 복잡도를 가진 알고리즘이라고 할 수 있습니다. 배열의 모든 요소를 한 번씩 방문하는 로직을 가지는 알고리즘은 선형 복잡도의 시간이 소요되는 알고리즘이라고 할 수 있습니다.
O(n)의 시간 복잡도를 가지는 알고리즘
# O(n)의 시간 복잡도를 가진 알고리즘 예시: for 문
for i in range(n):
# 1초가 걸리는 작업 수행
# 총 n 초가 걸린다
for j in range(2 * n):
# 1초가 걸리는 작업 수행
# 총 2 * n 초가 걸린다
위 for문 예시에서는 입력값 n이 1씩 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어납니다.
그렇다면 아래 for 문은 n이 1씩 증가할 때마다 코드의 실행 시간이 2초씩 증가합니다. 그렇다면 아래의 for문 예시는 O(2n)이라고 표현할까요? 그렇지 않습니다! 알고리즘 시간 복잡도는 최고차항의 계수(n 앞에 붙어 있는 수)는 제외하고 같은 비율로 증가한다면 알고리즘의 시간 복잡도를 O(n)으로 표기합니다. (참고로 최고차항 외에 추가되는 요소는 시간 복잡도로 표기할 때 표현하지 않습니다)
(4) O(n²)
O(n²)은 2차 복잡도(Quadratic Complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱 비율만큼 증가하는 알고리즘을 의미합니다. O(n)의 시간 복잡도를 가진 대표적인 for문을 이중으로 수행하면 대표적인 2차 복잡도를 가지는 알고리즘이 됩니다. (선택 정렬, 삽입 정렬, 버블 정렬도 대표적인 O(n²) 시간 복잡도를 가지는 알고리즘)
O(n²)의 시간 복잡도를 가지는 알고리즘
# O(n²) 시간 복잡도를 가진 알고리즘 예시: 이중 for문
for i in range(n):
for j in range(n):
# 1초가 걸리는 작업
# 총 소요 시간: n * n = n² 초
위의 O(n) 시간 복잡도를 가진 알고리즘과 마찬가지로 최고차항 계수(n 앞에 붙는 수)는 제외하고 O(n²)의 시간 복잡도를 가지는 알고리즘입니다.
(5) O(2ⁿ)
O(2ⁿ)은 기하급수적 복잡도(exponential complexity)라고 부릅니다. 구현한 알고리즘의 시간 복잡도가 O(2ⁿ)이라면 다른 방법을 고민해보는 것이 좋습니다. (웬만하면 O(2ⁿ) 시간 복잡도를 가지는 알고리즘 사용은 최적화를 위해 지양하는 습관을 들이는 것이 좋아요)
O(2ⁿ)의 시간 복잡도를 가지는 알고리즘
# 재귀로 구현한 피보나치 수열
def fibonacci(n):
if n <= 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
재귀로 구현하는 피보나치 수열은 대표적인 O(2ⁿ) 시간 복잡도를 가지는 알고리즘입니다. 이런 시간 복잡도를 가지는 알고리즘은 대개 동적 계획법(Dynamic Programming, DP) 등의 방법을 활용해서 구현하면 시간 복잡도를 낮출 수 있습니다.
4. 시간 복잡도를 줄이는 방법
(1) 반복문 횟수 줄이기
위의 O(n²) 시간 복잡도의 예시에서 보았듯이 코드의 Big-O를 줄이는 대표적인 방법은 반복문의 숫자를 줄이는 것입니다. 또는 반복문 내의 탐색 범위를 줄이는 것도 고려해볼만 한 선택지입니다.
파이썬의 경우 1초에 약 2000만 번의 연산을 수행하는데, 탐색해야 하는 경우의 수가 10만, 제한 시간이 2초 이내라면 이중 for문으로 연산한다면 Big-O 계산시 100억(10만 * 10만)번의 연산을 수행하고 제한 시간을 가뿐히 초과해서 시간 초과가 날 것이라는 것을 예상하고 다른 알고리즘 방법을 생각해야 합니다.
알고리즘 문제 풀이에 익숙해지신다면 알고리즘 문제를 읽으면서 머릿속으로 시간 초과 날 것 같은 코드를 자연스럽게 소거하면서 풀이 방법을 정립하게 될 거예요. (그렇다고 적당한 방법이 바로 떠오르지는 않은 채 시간만 흐르는데..) 바꾸어 말하면 알고리즘 풀이에 익숙해지는 과정에서는 필연적으로 수많은 시간 초과를 마주해야 하는데 경험을 통해 개선해 나갈 수 있는 부분이라고 생각합니다.
(2) 조건문 줄이기
조건문이 있다면 조건문의 숫자만큼 n 번을 멈춰서 시간이 소요되므로, 실행 시간을 단축시키기 위해서는 조건문을 되도록 적게 사용해서 구현하는 방법을 생각해야 합니다.
(3) 자료 구조를 적절하게 활용하기
효율적인 자료구조를 활용한다면 시간 복잡도를 줄일 수 있습니다. 대표적으로 실행 시간을 단축시켜주는 방식의 알고리즘은 DP(동적 계획법), 비트마스킹 등을 활용한 알고리즘이 있습니다.
(4) 적절한 알고리즘을 활용하기
실행 시간을 줄이기 위해 적절한 알고리즘을 시의적절하게 활용하는 방법이 실행 시간을 단축시키는 마지막 방법입니다. (Greedy, Dynamic Programming, Bitmasking, Binary Search, Two Pointer 등) 마지막 방법인만큼 끊임 없이 고민하고 시행착오를 경험해야 하는 부분인데요, 실행 시간을 줄이기 위해 자신이 짠 코드, 또는 문제에서 주어진 상황을 해결하기 위해 적절한 알고리즘을 생각하고 구현하는 것이 개발자의 기본 덕목이자 능력이라고 생각합니다.
이번 기사에서는 시간 복잡도, 특히 빅-오 표기법을 중심으로 한 알고리즘의 시간 복잡도 기본 개념에 대해 알아보았습니다. 알고리즘을 공부하는 분들께 도움이 되었으면 좋겠다는 말과 함께 이번 글을 마무리하겠습니다. 감사합니다~!
'SSAFY > SSAFYcial' 카테고리의 다른 글
| 리액트 상태 관리 라이브러리 Zustand (1) | 2024.03.03 |
|---|---|
| 자바스크립트 코딩 테스트 준비하기 (7) | 2024.03.03 |
| SSAFY 1학기 자치회 가이드 (2) | 2024.01.14 |
| 프로젝트 잘하는 팀의 비법, JIRA(지라) 사용 가이드 (2) | 2023.12.30 |
| 리액트(React) 공부 시작하기 (3) | 2023.12.27 |
