Chapter - Algorithm whit Math

용어 정리

• 약수: 어떤 수를 나누어떨어지게 하는 수
• 배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수
• 공약수: 둘 이상의 수의 공통인 약수
• 공배수: 둘 이상의 수의 공통인 배수
• 최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
• 최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

최소 공배수 LCM

문제 : 마스크 만들기

코코나 시대를 맞이하여 마스크를 제작/판매하는 MerMeri회사는 호들갑 떠는 한국인들의 호구력을 잡기위해 K-마스크를 만들고 있다. MerMeri회사는 노동력 착취를 위해 사장을 포함하여 외국인 노동자 A, B, C 세명이 전부이고 이들 모두 마스크를 만든다. A는 55분마다 9개, B는 70분마다 15개, C는 85분마다 25개의 K-마스크를 만들 수 있다. 이 회사 사람들은 새벽 4시부터 일어나 추가 수당도 없이 일하기 시작하여 각각 55분, 70분, 85분 동안 연속으로 마스크를 만든 뒤 5분씩 쉰다. 이 외국인 노동자들 세명이 처음으로 동시에 쉬는 시점이 퇴근시간이라면, 이날 하루에 제작한 K-마스크는 모두 몇개일까?

A, B, C의 작업 시간과 쉬는 시간 5분을 더하면 A, B, C는 각각 60분 75분 90분 마다 마스크를 만든다. 세명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 된다. 따라서 쉬고 난 직후가 처음으로 같을 시점으로 구해야 하므로 공배수와 최소공배수의 개념을 알아야한다.

결과적으로 *LCM(60, 75, 90)은 900이다.
(참고로 900분은 15시간이다)

따라서 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개가 된다.

최대 공약수 GCD

문제 : 조명 설치

K-공원을 만들기 위해 가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)

위의 문제는 최대 공약수로 간단하게 문제를 풀 수 있다.
모든 조명을 일정한 간격으로 설치해야 하므로, 가로변과 세로변의 공약수를 구해야한다.

가로와 세로로 각각 나누어 나머지가 없이 떨어지는 수들을 나열한 뒤, 공통된 수만 모으면 공약수를 구할 수 있다. 그리고 공약수를 기준으로 조명을 설치하면 길이가 다른 가로와 세로여도 일정한 간격으로 나누어 조명을 설치할 수 있다.

최소로 필요한 조명의 갯수를 파악해야 하기 때문에 최대 공약수가 필요하다. 따라서 GCD(12, 24)는 12이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 12로 나누어 최소로 필요한 조명의 개수를 구할 수 있다.

12/12 + 24/12) X 2 = 3 X 2 = 6개

그러나 이 문제에서는 꼭지점을 제외한 직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하므로 12를 제외한 최대 공약수로 문제를 해결해야 합니다.

(12/6 + 24/6) X 2 = 6 X 2 = 12개