문제
1~10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1~20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
풀이
어떤 수 A를 B로 나누었을 때 나머지가 0이라면 (즉, 나누어 떨어진다면) A는 B의 배수이다. 문제에서 예를 든 2520은 1의 배수이면서 2의 배수이자 동시에 3, 4, 5, ... , 10의 배수로 1과 10 사이의 모든 자연수의 공배수이다. 물론 이러한 공배수는 무한히 많지만 그 중에서 가장 작은 값이라 하였으니 최소공배수이다.
따라서 문제는 1~20의 모든 자연수의 최소 공배수를 구하는 문제라 할 수 있다. 셋 이상의 수의 최소 공배수를 구하려면 먼저 두 개의 자연수의 최소 공배수를 구하고, 다시 그 값과 나머지 하나의 수의 최소 공배수를 다시 계산하면 된다.
이와 같은 방식으로 1에서 20 의 최소 공배수를 계산할 수 있는데, 최소 공배수를 계산하는 방법은 다음과 같다.
- 두 수 A, B 가 있을 때, 그 최대 공약수 g를 구한다.
- 이 때 \(A = g \times a, B = g \times b\) 가 된다.
- 두 수 A, B의 최소공배수는 \(g \times a \times b\)로 계산할 수 있다.
문제를 풀기 위해서는 gcd와 lcm을 각각 구하는 함수를 정의해야 할 것 같지만, 이미 줄리아에서는 내장함수로 성능이 준수한 두 개의 함수 gcd(), lcm()을 제공하고 있다.
따라서 1:20의 범위를 lcm() 함수를 통해서 하나로 접으면 원하는 값이 나오게 된다. 풀이는 다음 한줄의 코드.
@time reduce(lcm, 1:20) |> println
# 232792560
# 0.000669 seconds (16 allocations: 480 bytes)
리듀스
리듀스는 2개의 인자를 받아 하나의 값을 내놓는 함수를 사용해서, 배열이나 리스트의 앞에서부터 원소를 하나씩 줄여나가는 연산이다. 줄리아에서는 reduce() 라는 함수로 제공하고 있으며, 첫번째 인자로는 두 개의 인자를 받는 함수가 들어가며 그 뒤에는 연속열이 들어간다. 키워드 인자로 init=을 줄 수 있는데, 이 인자가 들어가면 배열의 첫 원소가 아닌 별도의 초기값을 지정할 수 있다.
연속열이 다른 연속열로 변환되는 것은 맵이며, 연속열이 하나의 값으로 변홛되는 것은 리듀스로 볼 수 있는데, 예를 들어 합계나 길이를 구하는 함수들은 모두 리듀스를 통해서 구현할 수 있다. 물론 리듀스에 사용되는 함수가 (배열, 원소)를 받아 배열을 내놓는 방식으로 동작한다면 리듀스를 통해서 맵을 구현하는 것도 가능하다.