서론

취업을 위한 코딩테스트 준비를 다시 시작하면서 이제 다시 감을 잡아가고있다. 여러 곳에서 정보를 찾아보고 다른 분들과 이야기 하면서 문제를 풀기 전에 check 해야 하는 부분들에 대해 알게되고 이를 점차 적용하기 시작했는데 계속 새로운 부분들이 나오게 된다.

알고리즘 문제 코드로 가기 전 생각할 것

• 시간, 메모리 제한 확인하기 (V1)
  • 인접 리스트, 인접 행렬 등 시간과 메모리에 따라 써야하는 방법이 달라지므로 확인하기
  • 시간제한을 알면 시간 복잡도와 유추해 코드를 짜지 않더라도 사용하지 못하는 알고리즘들을 알 수 있다.(컴퓨터는 1초에 1억번 정도의 연산이 가능하다)
• 제공되는 정보와 변수들을 정리하기 (V2)
  • 문제를 천천히 읽으면서 주어진 조건들을 파악하고 예제 데이터로 내가 이해한 것이 맞는 지 확인하기
  • 이것만 잘해도 써야하는 알고리즘 등이 많이 좁혀질 수 있다.
• 예제에 주어지지 않더라도 가능한 최대, 최소 데이터를 직접 생성해서 확인하기(V3)
  • 생각보다 입력 범위의 시작과 끝에서 예외가 발생하는 경우가 많다.
  • 나 역시 여러 알고리즘에서 초기값을 잘못생각하거나 n이 1이나 0일때 등을 고려못해서 틀린 경험이 많다.
  • 문제 풀기 전 미리 생각해보자

여러 알고리즘의 시간복잡도

알고리즘	시간 복잡도	공간 복잡도
Binary Search	O(NlogN)	O(N)
Quick Sort	평균 O(NlogN), 최악 O(N^2)	O(V)
Dijkstra	O(ElogE) or O(ElogV)	O(V+E)
DFS & BFS	O(V+E)	O(V+E)
Counting Sort	O(N)
Quick Sort	평균 O(NlogN), 최악 O(N^2)

Arrays.sort : DualPivotQuicksort(평균 O(NlogN), 최악 O(N^2))
Collections.sort : TimeSort(삽입 + 합병) O(NlogN)