Coding Test

계수 정렬에 대해서 알아보자. 기존에 Arrays.sort()만 거의 사용했던 것 같다.Arrays.sort()는 고성능 퀵소트를 사용한다고 알고있다. 그래서 시간복잡도는 아래와 같다.평균 시간복잡도: O(n log n)퀵소트도 충분히 빠른 정렬이긴 하지만 0을 포함한

깊이우선 탐색인 dfs 알고리즘부터 알아보자. 이전에 여러번 공부했었는데 역시 제대로 정리하고 넘어가는게 나을거 같아서 해보겠다.

최대공약수, 최소공배수 가끔 등장하는 알고리즘이다. 피보나치수열 처럼 알면 간단하게 풀 수있어서 정리하고 넘어가보자!최대공약수는 유클리드 호재법으로 계산한다. 식은 아래와 같다. 재귀함수로 작성하면 된다.최소공배수는 두 수(a, b)의 곱을 최대공약수로 나눠주면 구할

누적 합 알고리즘은 연속된 구간의 합을 빠르게 구할 수 있게 해준다. 이 알고리즘을 알아두면 for문 한 차원을 줄일 수 있어서 시간 제한에서 안걸릴 수 있다. 전에 내 블로그 포스터 중 계수 정렬의 핵심 개념도 누적 합 알고리즘을 사용한 것이다. 가장 핵심 개념은 아