[section 2] 알고리즘(3) - 시간복잡도, Greedy

시간복잡도 Time Complexity

입력값과 연산 수행 시간의 상관관계를 나타내는 척도

시간복잡도가 작을 수록 좋은 알고리즘

표기법

• Big-O 빅-오: 최악의 경우를 고려하여 표기(상한)

• Big-Ω 빅-오메가: 최선의 경우 표기(하한)

• Big-θ 빅-세타: 평균

코드에서의 시간복잡도

• 입력에 상관없는 경우 ➡️ O(1)

• 입력에 상관있는 경우

  • for문이 여러개인 경우 ➡️ 각각의 시간복잡도를 계산해서 가장 큰 값으로 계산
  • n번 반복되는 for문이 중첩된 경우 ➡️ O(n^(for문의 개수))

---

탐욕 알고리즘 Greedy

당장 선택할 수 있는 최적의 상황만을 선택해 최종적인 답에 도달하는 방법

❗️그리디로 최적해가 보장되지 않을 수 있음

동전 바꾸기

• 그리디로 최적해가 보장되는 경우

가장 적은 개수의 동전으로 3,256원 만들기

500원 100원 50원 10원 5원 1원 짜리 동전들이 있을 경우

➡️ 500원 6개 + 100원 2개 + 50원 1개 + 5원 1개 + 1원 1개
➡️ 총 11개의 동전 필요

• 그리디로 최적해가 보장되지 않는 경우

가장 적은 개수의 동전으로 1,300원 만들기

1. 500원 100원 50원 10원 5원 1원 짜리 동전들이 있을 경우
   ➡️ 500원 2개 + 100원 3개 = 총 5개의 동전 필요

2. 500원 400원 100원 75원 50원 짜리 동전들이 있을 경우
   ➡️ 500원 1개 + 400원 2개 = 총 3개의 동전 필요

❗️동전의 액면이 증가하면서 앞 액면의 배수가 되지 않는 경우에는 최적해가 보장되지 않음