Jacob's Coding Playground

[문제출처 : Codechef] 이번에 풀어볼 문제는 Permutation에 관한 문제입니다. Permutation은 주어진 리스트를 나열하는 순서라고 보실 수 있는데요, 예를 들면, permutation list가 [1, 4, 2, 3] 이렇게 있다면 이 의미는 숫자 1이 첫번째에 있고, 숫자 2가 네번째에 있고, 숫자 3이 두번째, 숫자 4가 세번째에 있는 리스트라는 얘기로써, 이를 복원한 inverse permutation은 [1, 3, 4, 2]가 됩니다.

[문제출처 : Codechef] 이번에 풀어볼 문제는 게임의 승자를 찾는 문제입니다. 다음과 같은 게임이 있다고 가정해 봅시다.

이번에 알아볼 알고리즘은 sorting의 편법(?)이라고 할 수 있는 Counting sort에 대해서 알아보겠습니다. 보통 정렬을 하기 위해서는 두 원소를 집어서 비교를 해야 해서 이렇게 비교 방식으로 정렬하는 방법은 무조건 $O(n\log n)$ 이상이 필요하다는 정리가 있습니다. 하지만 이번에 알아볼 Counting sort는 비교하는 방식이 아니기 때문에 $O(k+n)$이라는 획기적인 속도를 낼 수 있습니다.(여기서 $k$는 list의 원소들의 값의 range 크기를 의미합니다.) 하지만 물론 공짜는 없겠죠? 제약조건이 반드시 따라붙게 되어있습니다.

이번에 살펴볼 정렬 알고리즘은, 실제 정렬 알고리즘 중 가장 인기있고 많이 사용되는 Quick Sort입니다. 이름 그대로 빨라서 quick sort겠지만, 이론적으로는 평균 $O(n\log n)$으로 앞서 배웠던 merge sort와 비슷한 수준입니다. 하지만 메모리 효율성 등의 측면에서 실제로 돌아가는 속도가 조금 더 빠르고 가볍기 때문에 많이들 사용한다고 합니다.

이번에 살펴볼 분야는 제가 학부때에 많이 공부했던 신호처리 분야입니다 :) 그때 당시에는 C언어나 matlab을 사용했었는데, 이렇게 R로 새롭게 해보니까 또 새롭네요. 여기서는 특정 신호를 fft를 이용하여 분석해보고 어떻게 필터를 적용할 수 있는지 살펴보겠습니다.