알고리즘 문제만 보면 머리가 하얘지는 경험을 한적이 있는가.
고등학교 수리영역 응용문제를 푸는 것과 같은 느낌이다.
매번 달라지는 문제에 정신 못차렸던 이유는 알고리즘을 잘 이해하지 못했기 때문이라고 생각한다.
잘 짜여진 알고리즘은 변수에도 끄떡없다.
알고리즘(algorithm)은 어떤 문제를 해결하기 위한 동작(방법)의 집합.
알고리즘을 짤 때 고려해야하는 것은 딱 2가지이다.
바로, 시간복잡도와 빅오이다.
왜그런지 살펴보자.
01. 시간복잡도와 공간복잡도
1) 시간복잡도 : 어떤 알고리즘을 연산하는데 소요되는 시간을 수치화
array의 길이를 도는 연산은 N으로 계산, 대입, 비교연산은 상수 1로 계산
수치화 할때에는 보통 N의 차수가 중요하기 때문에,
N 앞뒤의 상수는 무시하고 상수는 1로 간단히 표시함
array = [3, 5, 6, 1, 2, 4]
for element in array: # array 의 길이만큼 아래 연산이 실행 : N
if number == element: # 비교 연산 1번 실행 : 1
return True # 시간복잡도 : N * 1 = N
return False
2) 공간복잡도 : 어떤 알고리즘을 연산하는데 사용되는 공간을 수치화
array의 길이만큼 공간 계산, 변수하나당 1로 계산
수치화 할때에는 상수는 1로 간단히 표시함으로 아래 알고리즘의 공간복잡도는 1이다.
array = [3, 5, 6, 1, 2, 4]
for element in array: # array : 6
if number == element: # 비교 연산 1번 실행 : 1
return True # 공간복잡도 : 6 + 1 = 7
return False
공간복잡도는 대부분 상수만큼의 공간이기 때문에
공간을 희생하면서까지 시간복잡도를 신경써야한다.
성능은 시간복잡도와의 연관이 가장 크다.
02. 빅오와 빅오메가(알고리즘의 효율성 평가)
빅오 표기법 : 최악의 성능이 나올때의 어느정도 연산량이 걸릴것인지 (예시) O(N)
빅오메가 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지 (예시) Ω(1)
# 숫자 3을 찾는 반복문을 실행하면,
input1 = [3, 5, 6, 1, 2, 4] # 배열을 다 돌지 않아도 첫번째로 값이 반환되기 때문에 Ω(1)의 시간복잡도
input2 = [4, 5, 6, 1, 2, 3] # 배열을 다 돌아야 값이 반환되기 때문에 O(N)의 시간복잡도
for element in array:
if number == element:
return True
return False
최악의 성능을 항상 대비해야하기 때문에 빅오 값이 중요하다.
앞으로 알고리즘 문제들을 풀어갈 것이다.
알고리즘을 구현할 때 위의 내용들을 염두에 두고
좋은 코드를 짜보자💙