시간복잡도

시간 복잡도와 공간복잡도는 상호 거래관계라고 볼 수있다.

둘 중 하나를 잡으면 하나는 포기해야함

N사이즈의 이중포문이면 대표적으로 O(N^2)으로 나타냄

---

• 상수시간
• 로그시간
• 선형시간
• 로그선형시간
• 이차시간
• 삼차시간
• 지수시간

등으로 나타낸다.

---

여기서 시간복잡도는 A,B값을 비교하는 것, 리스트의 Sort, append, pop, popleft등도 다 연산으로 취급하며 이들도 각각의 시간복잡도를 가지고 있다.

리스트의 시간복잡도

pop과 insert sort는 모두 O(N)만큼의 시간복잡도를 가지고있으니 주의하자.

C에서는 보통 10^8승 즉 1억번의 연산을 1초로 잡지만 파이썬은 이것보다 느림으로 더 적은 약 2천번의 연산을 1초로 삼아서 계산하자.

시간초과가 난다면 python보다 빠른 pypy로 실행하면 해결될 수도 있다.

---

그리디 알고리즘 : 탐욕법

현재 상황에서 지금 당장 좋은 것만 고르는 방법
나중에 미칠 영향에 대해서는 전혀 고려하지 않는다.

ex) 1260원을 동전으로 거슬러주는 최소 갯수를 구하기

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_type: #제일 큰 동전부터 그냥 무지성으로 나눠버리기
	count += n//coin
	n %= coin

print(count)

ex2) N이 1이 될때까지 다음과정 반복하기
1. N에서 1을 뺀다
2. N을 K로 나눈다.(나눠지면)

n, k = map(int, sys.stdin.readline().split())
result = 0

# N이 K이상이라면 k로 계속 나누기
while n >= k:
	while n% k != 0: #나눠지지 않으면 1계속빼기
    		n-=1
        	result +=1
        n//=k
        result +=1
while n>=1:
	n-=1
    	result +=1
        
print(result)

---

브루트포스 탐색

조합가능한 모든 문자열을 하나씩 대입하여 암호해독하는 방식
(동전문제나 N이 1이 될때까지 문제도 모두 브루트포스를 사용)


10^4승 만큼 시도하면 이 자물쇠를 손쉽게 풀 수 있다.
(파이썬은 2000만번 연산하는데 2초도 안걸리니까 컴퓨터에 맡기면 2초면 열 수 있는 쉬운 자물쇠!)

시간초과가 나기 매우 쉬움 -> N의 크기와 시간복잡도를 잘생각해서 쓰기
특정조건을 변형하거나 Dp로 전환하여 사용가능

비선형구조 탐색과 그래프와 같은 선형구조 탐색에 따른 알고리즘이 세분화됨.
(선형구조의 탐색인 DFS, BFS 등과 같은 알고리즘은 후에 배우는 걸로)