11.24 시간복잡도, Greedy, 구현

시간복잡도를 표현하는 방식은 여러가지다. 그중 가장 많이 쓰이는 Big-O 기법에대해 살펴보겠다.

 

ㅇ O(1)

constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나진 않는다.

 

ㅇ O(n)

linear complexity. 입력값이 증가함에 따라 시간증가. 입력값 1증가 2초증가하면 O(2n)

 

ㅇ O(log n)

logarithmic complexity. BST처럼 경우의수를 절반씩 줄어든다. 입력값이 크면클수록 빠르다. O(n)보다 빠를수도 있다.

 

ㅇ O(n^2)

quadratic complexity. 입력값늘때마다 n^2만큼 시간이 늘어남.

 

ㅇ O(2^n)

exponential complexity. 가장 느린 시간복잡도를 가진다. 복리라고 생각하면 편함.

 

ㅇ Greedy Algorithm

탐욕알고리즘? 뭔 이름이 이러지 싶었다. 성립하기 위해 두가지 조건 필요

1. 탐욕적 선택 속성 - 앞의선택이 이후의선택에 영향을 주지않는다.

2. 최적 부분 구조 - 문제에 대한 최종해결 방법은 부분문제에 대한 최적 문제 해결 방법으로 구성됨.

절차를 살펴보면,

1. 선택절차 - 현재 상태에서 최적의 해답을 선택함.

2. 적절성 검사 - 선택된 해가 문제의 조건을 만족하는지 검사함

3. 해답검사 - 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복함.

 

거스름돈990원을 최소한의 동전갯수로 줘야한다면,

1. 선택절차 - 가장 가치가 높은 동전을 우선선택함

2. 적절성 검사 - 1을 통해 선택된 동전을의 합이 금액을 초과하는지 검사, 초과하면 마지막 선택한 동전 삭제, 1로 돌아가 더작은 단위 동전 선택

3.해답검사 - 선택된 동전의 합이 금액과 일치하는지 검사함. 안맞으면 1번부터 반복한다.

알고리즘문제를 실제로 풀어봤는데, 진짜 너무 어려웠다. 하지만 유명한 풀이방법이 템플릿처럼 존재한다고 한다.

 

ㅇ 구현

완전탐색 알고리즘 - 모든 가능성을 시도해서 문제를 해결하는 방법. 최적의 솔루션이 아니기때문에 시간공간복잡도가 높을 수 있다.

이진탐색 알고리즘 - 데이터가 정렬된 상태에서 절반씩 나눠 분할 정복기법으로 특정 값을 찾아내는 BST같은 해경방식.