[TIL] 코드스테이츠 SEB BE Day 25

in TIL

💡 Today I Will Learn

  • Time Complexity
  • Greedy Algorithm

✏️ Summary

Time Complexity

알고리즘 문제 풀이를 더 효율적인 방법을 통해 푼다는 것이 시간복잡도를 고려한다는 의미이다.

즉, 입력값 n에 대해 얼마만큼의 시간이 걸리는가에 대해 표시하는 방법이다.

빅오 표기법(Big-O)

시간복잡도는 Big-O, Big-Ω, Big-Θ 세가지 표기법이 있지만, 최악의 경우를 고려하는 Big-O 표기법을 주로 사용한다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

Greedy Algorithm

눈 앞에 보이는 최적이라 생각되는 해답을 찾아서, 최종 해답을 찾아내는 방법이다.

1. 선택절차: 현재 상태의 최적의 해답
2. 적절성검사: 위 해답이 문제 조건에 맞는지 검사
3. 해답검사: 아직 문제가 해결되지 않았다면 위의 과정 반복

탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족하여야 한다.

📌 정리

눈 앞에 당장 보이는 해결책이 최선의 해결책이 될 수 있다는 것이 매력적이었지만, 그만큼 적용할 수 있는 문제도 많지 않고 떠올리기도 힘들어서 많은 문제를 접해봐야겠다😎

🎯 Tomorrow

  • Brute-Force Algorithm
  • Binary Search Algorithm

Back to [TIL] 코드스테이츠 SEB BE Day 24