[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) 자료구조 기본 지식들

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

📌 어떻게 나온 계산인가?

1. CPU의 클럭 속도
   • 현대적인 CPU는 보통 3GHz ~ 4GHz 정도의 클럭 속도를 갖는다
   • 1GHz = 10⁹ 클럭/초, 따라서 3GHz = 3 × 10⁹ 클럭/초
2. 클럭당 연산 수
   • 보통 CPU는 한 클럭 사이클당 1개의 연산을 처리할 수 있다 

※ 그러나 연산 종류에 따라 다르다

• 덧셈, 뺄셈: 1클럭
• 곱셈: 1~3클럭
• 나눗셈: 3~10클럭
• 메모리 접근: 2~5클럭 (캐시 여부에 따라)

 

(계산 예시)

• 3GHz CPU는 3 × 10⁹ 연산/초가 가능하다
• 그러나 실제 프로그램에서는 메모리 접근, 분기문(조건문), 함수 호출 등이 있어 CPU 성능을 100% 활용하지 못한다
• 경험적으로 30% 정도의 성능만 활용된다고 가정:
  • 3 × 10^9 × 0.3 = 9 × 10^8 연산/초
  • 이를 여유 있게 1억 번(10⁸)으로 잡은 것이 이 법칙의 시작이다!

 

따라서 "1억(10^8)번의 연산 = 1초"
이 원리를 이용해 입력 제한값으로 알고리즘을 유추할 수가 있다
 
 
 
[입력 제한값에 따라 가능한 최대 시간 빅-오]
1. n <= 20 : 빡구현, 브루트 포스(완전 탐색), 백트래킹(완전 탐색에서 가지치기)
웬만한 저질 구현도 통과
O(n^n), 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

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