[Algorithm/Study] 1주차 - 시간복잡도

 

해당 스터디는 <코딩 테스트 합격자 되기 C++> 저자님과 함께하는 스터디입니다.

---

 

이번 주부터 아래 인프런 강의를 보며 매주 알고리즘의 기초를 다지는 스터디를 시작했다. 기본 개념을 다시 한번 복습하고 싶었는데 저자님께서 직접 운영하시는 스터디고, C++ 강의이지만 다른 언어도 가능하다고 하셔서 참여하게 되었다. 7주간 열심히 달리자!🔥

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

시간복잡도

• 코딩테스트를 할 때 연산횟수를 매번 정밀하게 측정할 필요X → 점근적 표기법으로 표기함.
• 점근적 표기법 : 연산횟수의 추이를 활용해 시간복잡도를 표기하는 방식 → 최악의 경우를 고려해서 점근법 표기법으로 나타내는 것을 빅오표기라고 함.
• 빅오표기 방법
  • 다항식에서 가장 영향을 미치는 항을 남기고 제거함.
  • 마지막 남은 항의 계수를 제거함.

코딩테스트에서 자주 보이는 시간복잡도 

• 1차원 배열탐색 O(N)
• 2차원 배열탐색 O(N*M)
• 이진탐색트리에서 원소 탐색 O(logN) → 트리의 높이
• 동전을 N개 던졌을 때 경우의 수 O(2^N)

이런 것들을 어떻게 코딩테스트에 활용하냐면...

• 입력값의 크기를 통해 시간복잡도가 어느정도까지 허용되는지 추측할 수 있음.
  • 구현 시 알고리즘/자료구조의 선택을 명확히 할 수 있음.
  • 구현한 코드가 시간초과가 발생할 것인지 미리 파악 가능함.
  • 대략 초당 1000 ~ 2000만 정도 연산을 한다고 가정하면 됨.
•  

  시간복잡도	최대 입력 크기
  O(N!)	10
  O(2ⁿ)	20~25
  O(N³)	200~300
  O(N²)	3,000~5000
  O(NlogN)	100만
  O(N)	1,000~2000만
  O(logN)	10억