이 내용은 고등-문과, 전공-문과, 3년차 어린이집 교사가 개발자가 되기 위해 공부하며 적은 글입니다.
내가 문과생/비전공자라면 한 번 읽어보세요 !
최근 코딩테스트를 준비하다가 한계에 부딪히면서 단순히 코딩테스트 연습이 중요한 것이 아니라 알고리즘, 자료구조 등이 더 중요하고 일단 그걸 완벽히 이해해야 코테를 더 잘할 수 있을 것 같다는 생각이 들었다.
그래서 하나하나 차근차근 깊게 공부해보고 싶었다.
(늦었다고 생각할 때가 진짜 너무 늦었기 때문에 빨리 시작한다)
그 시작은 빅오 표기법!
보통 들으면 '아 이건 이런 것 같은데?' 하는 감이 오는데 이건 전혀 안오는,,
그래서 일단 구글에 검색해보았다.
문과생 비전공자는 구글을 보고도 이해를 하지 못해 블로거들이 써놓은 볼로그들과 유튜브를 여러 개 보았다.
(개발자가 영어 공부가 꼭 필요한 이유 1)
Big-O 관련
빅오표기법 블로그
시간복잡도와 Big-O표기
빅오표기법이란?
엔지니어대한민국
위의 순서대로 글을 정독하고 영상을 집중했더니 어느 정도 이해가 갔다. (이 순서 매우 추천 👍)
Big-O 알아보기 전 잠깐!
시간 복잡도와 공간 복잡도가 있다.
알고리즘을 공부하려고 조금이라도 서치 해본 사람이라면 한 번쯤은 들어보았을 것이다.
- 시간 복잡도
- 알고리즘의 실행 속도
- 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화
- Big-O 표기법 사용
- '어떤 방법이 더 효율적일까?' 라는 생각을 한다면 시간 복잡도를 고민한다는 것
- 알고리즘은 정해진 답이 없기 때문에 가장 실행 속도가 적은 최적의 코드를 짜야 한다.
- 공간 복잡도(Space Complexity)
- 알고리즘이 사용하는 메모리의 크기(메모리를 얼마나 사용하느냐)
- 얼마나 많은 자원이 필요한가?
결국 좋은 알고리즘이란
시간도 적게 걸리고 메모리 사용도 적어야 하는 것
하지만 시간과 공간은 반비례적인 성향이 있어 시간 복잡도를 위주로 판단한다. 또한, 요즘 메모리의 발전으로 공간 복잡도의 중요도가 낮아졌다.
그래서 시간 복잡도가 중요하다는 것 !
이런 시간 복잡도를 나타내는 데 사용되는 표기법 중 하나가 바로 Big-O(빅-오)표기법이다.
Big-O 표기법이 왜 필요해?
상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 한다.
개발자는 문제를 해결하기 위해서도 존재하지만 하루를 온종일 사용자를 위해 투자하는 사람들인만큼 최대한 짧은 시간을 활용해서 효율적으로 쓰기 원한다.
(여기서 클린 코드가 왜 중요한지도 알 수 있다. 이건 다음에 한 번 고민 해봐야겠다.)
아무튼 그렇기 때문에 문제 해결시 시간 복잡도를 나타내는 빅오표기법을 활용해서 해당 알고리즘의 처리 시간을 예측해 효율성을 높일 수 있다.
Big-O 표기법
입력값의 변화에 따라 연산을 실행할 때, '연산 횟수에 비해 시간이 얼마만큼 걸리는가?'를 표기하는 방법
빅오 표기법은 최악의 경우를 고려하고, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려한다.
"이 정도 시간이 걸린다" 보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야한다.
(현실 세계에서는 조금 다를 수 있지만 항상 최고의 방법만은 찾지 않잖아요?.. 최악의 방법을 생각하고 있어야 그만큼 대비 할 수 있다와 비슷한 맥락,,)
위의 사진을 보면 표기 방법이 나와있다.
O(1)로 갈수록 실행 횟수가 적고, 시간 복잡도가 낮은 것
O(2^n)로 갈수록 실행 횟수가 많고, 시간 복잡도가 높은 것
한 눈에 보기 쉽게 그래프로도 나와있다.
활용 코드
조금 더 이해하기 위해 코드를 통해 알아보자.
1. O(1)
- 입력데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
- 데이터가 증가해도 성능과 수행 시간에 변함이 없다
l = [1, 2, 3]
for n in l:
print(n)2. O(n)
- 입력데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
- 언제나 데이터와 시간이 같은 비율로 증가
l = [1, 2, 3]
for n in l:
print(n)3. O(n^2)
for문안에 또for문- n을 돌릴 때 또 n을 돌리니 n의 면적만큼 생긴다
- n^3도 똑같다 : 입체 사각형 형태 (3중 for문)
def bubble_sort(l):
swap = True
while swap:
swap = False
for i in range(len(l)-1):
if l[i] > l[i+1]:
l[i], l[i+1] = l[i+1], l[i]
swap = True
lst = [41, 452, 223, 1, 23, 55, 666]
bubble_sort(lst)
print(lst)4. O(2^n)
- 피보나치 수열(재귀함수)
- 함수가 호출 될 때마다 두 번씩 또 호출
def recursive_fibonacci(n):
if n <= 1:
return n
else:
return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
steps = 10
# 양수만
if steps <= 0:
print("양수만")
else:
print("직전 숫자와 그 전 숫자의 합이 현재 숫자:")
for i in range(steps):
print(recursive_fibonacci(i))
5. O(log n)
- 이진 검색
- 반을 나누고 또 나누면서 key값과 비교
l = [1, 2, 3, 5, 8, 22, 34, 55]
for index in range(0, len(l), 3):
print(l[index])끝나기 전 가장 중요한 것 !
빅오표기법에서 상수는 과감히 버린다!
F(int[] n) {
for i = 0 to n.length
print i
for i = 0 to n.length
print i
}위의 코드를 자세히 보면 O(n^2)의 코드 배치와 다르게 for문이 따로 떨어져 있다.
이렇게 되면 O(n^2)이 아닌 O(2n)로 볼 수 있다.
하지만 빅오표기법에서는 상수를 버리고 O(n)로 표시한다.
왜냐하면 빅오표기법은 실제 알고리즘의 러닝 타임을 재기 위해 만든 것이 아니라 장기적으로 데이터가 증가함에 따른 처리 시간의 증가율을 예측하기 위해서 만들어진 표기법이다.
상수는 고정된 숫자(내가 입력한 그대로고 변하지 않음) 이고, 증가율에 영향을 미칠 때 고정된 상수만큼만 영향을 미치기 때문에 증가하지 않는 숫자는 신경쓰지 않겠다는 것이다.
