[알고리즘] 멀쩡한 사각형 - 유클리드 호제법
https://programmers.co.kr/learn/courses/30/lessons/62048
코딩테스트 연습 - 멀쩡한 사각형
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을
programmers.co.kr
위 문제는 주어지는 W * H 만큼의 사각형에서 대각선으로 반으로 쪼갰을 때 사용할 수 있는 정사각형이 몇개인지를 구하는 문제다.
(여기서 정사각형은 W * H 만큼의 수를 뜻한다.
예) 8 * 12의 사각형은 96개의 정사각형을 갖고있다.)
위 문제를 풀기 위해서는 일반적인 산수로는 안되고 유클리드 호제법 이라는 알고리즘을 사용해야한다.
유클리드 호제법은 최대공약수를 보다 효율적으로 구할 수 있게 해주는 알고리즘이다.
유클리드 호제법은 되게 간단하다.
주어진 수 X, Y에 대해서 계속 나머지를 구해 0을 되게 하면 된다.
저렇게 작은 수는 소인수 분해를 통해 금방 구할 수 있지만, 큰 수의 경우에 엄청나게 많은 연산이 들어가야한다.
이럴 때 사용 하는 것이 유클리드 호제법이다.
사용 방법)
X = 8, Y = 12 일 때
- 12 MOD 8 = 4
- 8 MOD 4 = 0
이 때 나머지가 0이 나왔을 때 작은 수가 최대공약수 인 것이다.
8과 12일 때의 최대공약수는 '4' 라는 결론이 나왔다.
이에 대한 자세한 설명으로는 아래 링크를 참조하면 빠르게 이해할 수 있다.
(유클리드 호제법(Euclidean-algorithm))
이것을 이용하면 맨 위에 링크해둔 '멀쩡한 사각형' 문제를 해결할 수 있다.
재귀를 이용한 유클리드 호제법 알고리즘 구현.kt
|
1
2
3
4
5
6
7
8
9
|
fun GCD(w: Long, h: Long): Long {
val result = if(w > h) { w.rem(h) } else { h.rem(w) }
return if(result == 0L) {
min(w, h)
} else {
GCD(min(w, h), result)
}
}
|
cs |
다른 방법도 많은데, 나는 저렇게 풀었다.
저 알고리즘을 이용해서 어떻게 풀지? 라는 생각이 들때는 아래 링크를 참고하면 된다.
단순히 패턴을 보고 푸는 문제인 것 같다.
(링크에 답도 있으니, 주의하세요.)