2021_04_22

TIL - 알고리즘 문제를 보는 관점

1. 알고리즘 문제를 보는 관점

1. 입력의 크기를 고려한다.

2. 극단적인 입력을 가정한다.
   1) 가장 큰 입력값
   2) 가장 작은 입력값

3. 항상 완전탐색(exhaustive search)부터 생각하여 순서대로, 빠짐없이 고려한다.
   1) 문제를 직접 풀어야 한다.(직접 시행)
   -- 방향, 순서를 달리했을 때 똑같은 답이 나오는 경우(동전문제)
   2) 관찰을 통해서 패턴을 찾아야 한다.
   -- 순서를 부여하는 방법 : 문제 자체에서 주어지거나 내가 강제해야하는 경우가 있다.

4. 입력을 고려했을 때 시간복잡도가 1억을 넘지 않으면 그 방법대로 푼다.
   만약 1억을 넘는다면
   1) O(N^2) => O(logN x N)
   2) O(N^3) => O(logN x N^2)
   이와같이 시간복잡도를 줄인다.

5. 대표적인 log 시간복잡도 알고리즘
   1) 이진탐색
   2) memoization
   3) 문제의 성격을 바꿔야 하는 경우
   답을 풀어야 하는 문제 => 어떤 제약 조건에서 가능한지를 따지는 문제 cap(upper bound)