알고리즘 Radix Sort 오랜만에 나는 야호다. 오늘은 라딕스 소트라는걸 배워보자. 본인은 매우 애용한다. Counting Sort Radix Sort를 배우기 전에 우리는 Counting Sort에 대해 알아보아야 한다. 만약 다음과 같은 문제가 주어졌다고 하자. 1000만 개의 숫자가 주어진다. 각 숫자는 0 또는 1이다. 이를 정렬하라. 비교기반 정렬을 때리면, $$O(nlogn)$$으로 매우 오랜시간이 걸린다. 하지만 우리는
알고리즘 키타마사 법 나는 야호다. 오늘은 키타마사법에 대해 배워보도록 하겠다. 선형점화식을 풀자 PS를 하다보면 점화식을 풀 일이 종종 생긴다. 그 중에서 가장 많이 나오는 점화식은 당연히 다음과 같은 선형점화식의 꼴일 것이다. $$ \begin{aligned} a_n&=c_1 a_{n-1}+c_2 a_{n-2}+... +c_m a_{n-m}\\ &=\sum c_i a_{n-i} \end{
알고리즘 merge sort, quick sort를 구현해 보자 걱정이다. 이제 슬슬 내가 알고있는게 다 떨여저 간다. 근데 글쓰는거 왤케 재밋냐. 제목보고 들어왔을테니 정렬구현할꺼다. 머지소트랑 퀵소트(+ 간단한 함수포인터) 그리고 문제로 검증받아야 하니 여러문제의 풀이코드를 올리도록 하겠다. 그전에 신세한탄좀 하자 내가 std::sort()이 함수때문에 C++를 진입하지 못하고 '하... 모르겠다 걍 구현하고 말지' 라는 생각으로 'C'로 문제를 풀어왔다. 이
알고리즘 Heavy Light Decomposition 다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 이 글을 찾아올 정도의 사람이라면 아마 일일이 더하는 것이 아니라 누적합을 구해서 각 쿼리를 O(1)에 처리할 것이다. 저 배열에 단일점 업데이트가 있다면 세그먼트 트리를 쓸 것이고, 구간 업데이트가 있다면 Lazy propagation을 얹어서 쓸 것이고.
