Algorithm with Math - GCD / LCM
약수: 어떤 수를 나누어떨어지게 하는 수
배수: 어떤 수의 1, 2, 3…. 배하여 얻는 수
공약수: 둘 이상의 수들의 공통인 약수
공배수: 둘 이상의 수들의 공통인 배수
최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수
먼저 아래와 같은 최대 공약수 개념이 필요한 문제가 있다고 해봅시다.
문제: Mask States
방역용 마스크를 제작 판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량을 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개를 만들 수 있습니다. 이들은 05:00 시부터 동시에 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 제작한 후 5분씩 쉬게 됩니다. 이들 세 명이 처음으로 동시에 쉴 시점이 퇴근 시간이라면 이날 하루에 제작한 마스크의 개수는 모두 몇 개인가요? (퇴근은 쉬고 난 후에 합니다.)
다양한 풀이 방법이 있겠지만, 이 문제에서 최소 공배수를 떠올릴 수 있으면 더 쉽고 빠르게 문제 해결이 될 수 있습니다.
A, B, C의 작업 시간과 쉬는 시간 5분을 더하면 A, B, C는 60분, 75분, 90분마다 마스크를 만들기 시작합니다. 세 명이 동시에 쉴 시점은 세 명이 쉬고 난 직후가 같을 시점이 됩니다. 따라서 공배수를 알아야 하고 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로 최소 공배수를 알아야 합니다.
LCM(60, 75, 90)은 900입니다. 따라서
A는 B, C와 쉬고 난 직후가 처음으로 같을 시점까지 900/60 = 15턴을 반복하고 15턴 X 9개 = 135개의 마스크를 만들어 냅니다.
B는 900/75 = 12턴을 반복하고 12턴 X 15개 = 180개,
C는 900/90 = 10턴을 반복하고 10턴 X 25개 = 250개의 마스크를 만들어 냅니다.
그러므로 A, B, C가 하루에 제작한 마스크의 개수는 135개 + 180개 + 250개 = 565개가 됩니다.
예시 문제를 통해 최대 공약수와 최소 공배수가 어떻게 활용될 수 있는지 알아보았습니다. 문제의 답을 도출해 내는 것보다 해당 문제에서 최대 공약수와 최소 공배수를 활용해야겠다는 문제 해결 전략을 세우는 것이 중요합니다.
문제: 조명 설치
라운지에 있는 가로 24cm, 세로 12cm인 직사각형 모양의 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이는 반드시 설치하면서 일정한 간격으로 조명을 배열하려고 할 때, 최소로 필요한 조명의 개수는 몇 개인가요?
직사각형의 꼭짓점에는 반드시 하나의 조명이 설치됩니다. 모든 전구를 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 전구는 몇 개일까요? 이 문제의 정답은 12개입니다.
필요한 전구의 개수를 구하려고 할 때, 최대 공약수를 떠올리면 빠르게 문제를 해결할 수 있습니다. 그러나 간단한 문제를 풀더라도, 최대 공약수라는 수학적 개념을 바로 떠올리는 것은 훈련하지 않으면 결코 쉬운 일이 아닙니다. 계속해서 문제를 접하고, 문제를 해결하기 위해 필요한 수학적 개념을 떠올릴 수 있도록 반복해야 합니다.
모든 조명을 일정한 간격으로 설치해야 하므로, 가로변과 세로변의 공약수를 구해야 합니다.
가로와 세로 각각 나누어서 나머지가 없이 떨어지는 수들을 나열한 뒤, 공통된 수만 모은다면 길이가 다른 가로와 세로여도 일정한 간격으로 나누어 조명을 설치할 수 있습니다.
최소로 필요한 조명의 개수를 물어보기 때문에 최대 공약수가 필요합니다. 따라서 GCD(644, 476)는 28이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 28로 나누어주면 최소로 필요한 조명의 개수를 구할 수 있습니다.
(644/28 + 476/28) X 2 = 40 X 2 = 80개
이처럼 알고리즘 문제, 코딩 테스트에는 여러 가지 상황을 주고 "어떤 방법을 사용해서 풀어 볼래?"라는 의도에서 수학적 개념을 사용해야 하는 경우가 종종 등장합니다.
