[코딩 테스트 합격자 되기] 시간 복잡도

코딩 테스트 스터디

기간 : 2024-07-08 ~ 2024-08-25

 

스터디 참가 이유 및 목표

1. 알고리즘 기초 개념 복기
2. 평소 쓰는 언어인 파이썬 대신 C++를 사용해보면서 코드의 동작 원리를 깊이있게 이해 

스터디 방식

[인프런] 코딩 테스트 합격자 되기 - C++ 강의를 보고 금요일까지 블로그에 내용 정리

일요일 14:00에 디스코드를 통해 공부한 내용에 대해 소통

---

학습 날짜 : 2024-07-08

학습 주제 : 시간 복잡도

 

[목차]

• 알고리즘이란?
• 알고리즘 성능측정법 및 시간 복잡도 개념
• 시간 복잡도를 빅오 표기법으로 표기하기
• 코딩 테스트에서 꼭 알아둬야 할 시간 복잡도
• 실전 예시

---

알고리즘 성능은 구현된 코드가 동작하는 절대 시간이나 연산 횟수를 파악하여 측정할 수 있다

코딩테스트에서 알고리즘의 성능은 연산 횟수로 측정 / 최악의 경우를 연산 횟수로 생각 => 시간 복잡도 / 빅오표기

정확한 연산 횟수가 아닌, 연산 횟수의 추이를 파악

 

ex. 이진 탐색 트리에서 원소 탐색 : O(logN)

   1 + 2 + 2^2 + ... + 2^h = N

   트리의 높이 h = log_2^{N}

 

[시간복잡도를 코딩테스트에 활용하기]

입력값의 크기를 통해 어느정도 시간 복잡도까지 허용되는지 추측하여

구현 시 알고리즘/자료구조 선택을 명확히 함

=> 입력값이 100만(1,000,000 = 10^6)이라면 O(NlogN)인 알고리즘 부터 사용 가능, 2중 포문 불가

 

동일한 동작을 하는 것 처럼 보이지만 시간 복잡도가 다른 경우

성능 비교 : codingtest_cpp/performance at main · dremdeveloper/codingtest_cpp · GitHub