내일배움캠프 D+107: 0801

📚 알고보면 알기쉬운 알고리즘

✳ 1주차 ❇

✔ 시간 복잡도

▶ 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

상수는 버리고 변동이 가능한 인자를 N으로 본다. 2N+1이라도 N만큼의 연산량이 필요하다고 생각하면 된다. 상수일 경우 1만큼의 연산량이 필요하다고 하면 된다.

✔ 공간 복잡도

▶ 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

N의 n제곱 형태가 될 수 있는 시간 복잡도를 더 신경써야 한다.

✔ 점근 표기법

▶ 알고리즘의 성능을 수학적으로 표기하는 방법

위의 과정도 일련의 점근 표기법이라고 할 수 있다.

• 빅오(Big-O)표기법 최악의 성능 ex) $O(N)$

• 빅 오메가(Big-Ω) 표기법 최선의 성능 ex) $Ω(1)$

입력값에 비례해서 얼마나 늘어날 지 파악해보자!
공간복잡도를 희생해서라도 시간 복잡도를 줄여야한다!
항상 최악의 경우(빅오 표기법)를 생각하고 고민하자!

---

SAVE 💾

알고리즘 문제는 문제를 제대로 파악하는 것도 중요한 것 같다... 숫자 뒤집기는 뭔 말인가 싶었다 ㅎㅎ..
소수 나열하기 문제는 팀원분의 질문으로 해당 풀이에 오류가 있다는 사실을 알게 됐다. 나는 애초에 가장 비효율적이게 풀었어서, 내일 복습하면서 다시 정리해야겠다.