[ps 팁] 문제의 입력 제한값으로 알고리즘 유추하기

t = O(n) 함수라 생각하자

 

https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B8%B0%EB%B3%B8-%EC%A7%80%EC%8B%9D%EB%93%A4

[자료구조] ep1) 자료구조 기본 지식들

 

 

 

일반적으로 연산을 10^8 번 하면 1초다

10^8 = 1초

이 원리를 이용해 입력 제한값으로 알고리즘을 유추할 수가 있다

 

 

 

[입력 제한값에 따라 가능한 최대 시간 빅-오]

1. n <= 20 : 빡구현, 브루트 포스(완전 탐색)

웬만한 저질 구현도 통과

O(n!), O(2^n)

 

 

2. n <= 100 : 플로이드-와샬 알고리즘

적당한 삼중루프

O(n^3)

 

 

3. n <= 1000 : 벨만-포드 알고리즘

적당한 이중루프

O(n^2)

 

 

4. n <= 10000 : DP, 이진 탐색, 다익스트라 알고리즘, 유니온 파인드, 세그먼트 트리, 투 포인터

선형 (머리 좀 써야한다)

O(n), O(n logn)

 

 

5. n <= 10^8 : 유클리드 호제법

적당한 수학적 기믹 필요

O(log n)

 

 

 

 

 

 

 

 

참고 및 출처: 저세상개발자 유튜브

https://www.youtube.com/watch?v=PFKPdjdWbQ8

개인적으로 매우 좋아하는 유튜버이다