Jacob's Coding Playground

수학에는 Fibonacci(피보나치 수)라는 수가 있습니다. 아직 이것이 어디에 사용되는지 확인할 방법은 없지만… 그래도 프로그래밍 쪽에서는 꽤나 많은 예제로 등장하는 문제입니다. Recursive나 Iterative을 보여주는 예제로도 많이 사용되고, 특히나 이번에 소개해 드릴 Dynamic programming 측면에서 자주 예제로 등장하는 개념입니다. 간단하게 정의하면, \[F_n=\begin{cases} &0 &\text{if }n=0 \newline &1 &\text{if }n=1 \newline &F_{n-1}+F_{n-2} &\text{if }n>1\end{cases}\] 이런 형태의 수입니다. 그러면 우리가 가장 쉽게 구현할 수 있는 Recursive 방법으로 구현해 보겠습니다.

[문제 출처 : Codechef] $N$개의 나무 막대기를 가지고 있다고 해 봅시다. 그리고 $N$개의 나무 막대기의 길이는 각각 $L_i$, $1\le i\le N$으로 주어져 있습니다. 만약 여러분의 친구가 와서 “내가 임의로 세 개의 막대기를 뽑아서 삼각형을 만들 수 있으면 내가 이긴거고, 못 만들면 네가 이긴거야 :)”라고 말했을 때, 여러분은 여러분이 이길 확률을 구하고 싶겠죠? $N$개의 막대기 중 임의로 3개를 뽑았을 때 그것이 삼각형을 이루지 못하는 경우는 몇 가지일까요?

학창시절에 적분이라는 것을 배우면서, 그것을 구하는 방법에 대해 배웠었습니다. 가장 처음 접하는 예가 Riemann integral이라는 방식인데요, 미소구간 $dx$를 잡고 $dx$와 $f(x_i+dx)$를 변의 길이로 갖는 사각형들로 함수 면적을 쪼개서 그 합으로 적분 값을 근사해 나가는 방식입니다. 특히나 이 방법은 analytic한 solution이 없을 경우에 numerical solution을 구하기에 매우 핵심적인 방법입니다. 원리는 간단하지만 얼마나 대단한 방법인지 한번 살펴보시죠 :)

[문제 출처 : Codechef] 숫자 n이 주어졌을 때, n보다 큰 가장 가까운 자연수 중 소수이면서 회문인 m을 어떻게 찾을 수 있을까요? 여기서 우리가 기초훈련을 했던 것이 빛을 발할 시간입니다. [참고: 소수, 회문]

이번에 알아볼 machine learning 알고리즘은 K-nearest Neighbors라고 불리는 알고리즘입니다. 컨셉은 간단합니다. 새로운 데이터가 들어왔을 때, 기존에 우리가 가지고 있던 데이터를 기준으로 $K$개의 가장 가까운 점을 찾아서 그들의 평균값(regression의 경우)이나 majority votes(가장 빈번한 class로 분류하는 것. classification의 경우)로 새로운 데이터를 분류하는 방식입니다. 이름 그대로 $K$개의 가장 가까운 이웃인 것이죠 ^^