(코딩테스트)최대공약수와 최소공배수(꼬리재귀)

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

풀이의 선택과정

1. 최대공약수와 최소공배수를 구하는 공식이나, 함수가 있을것이니 이것을 활용

2. 장황하지 않고, 깔끔한 코드를 적을 수 있도록 가급적 반복문 남용은 자제

 

문제고민

보통 이런 수학 문제는 선조형아들이 만들어둔 최적 계산법이나 함수가 있을거고..

그것을 코틀린에 알맞는 간결한 문법으로 만들 수 있지 않을까?

 

해결방안

유클리드 호제법에 꼬리재귀(tailrec)를 엮는다.

 

꼬리재귀(tailrec)

= 추가적인 연산이 없이 자신을 재귀적으로 호출하다가

어떤 값을 리턴하는 함수를 의미한다.

이로 인해 while의 자원적 이점과 재귀함수의 가독성적 이점을 동시에 가질 수 있다.

코틀린에선 tailrec이라 선언하면 컴파일러가 루프로 변환을 해준다고 한다.

다만, 꼬리재귀엔 조건이 있는데, 앞서 설명했듯 추가적인 연산이 없어야 한다는 것이다.

예를 들어 return n+func(a,b)는 안된다는 것이다. 

 

유클리드 호제법

= 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.

자세한 설명은 이 곳을 보면 될거 같다.

 

 

정답풀이

class Solution {
    fun solution(n: Int, m: Int)= intArrayOf(gcd(n,m), n*m/gcd(n,m))
    private tailrec fun gcd(n: Int, m: Int):Int=if(m<=0) n else gcd(m, n%m)
}

 

핵심로직

private tailrec fun gcd(n: Int, m: Int):Int=if(m<=0) n else gcd(m, n%m)

꼬리재귀를 통해 while문의 코드를 간략하게 간추려 내었다.

로직 자체는 유클리드 호제법을 참고하고, 이것을 코틀린에 알맞게 개량한 것이다.

 

새로 알게된 것

꼬리재귀란 무엇인가?

꼬리재귀에 대해서 계속 알아보니, 코틀린에서 따로 선언을 받아줄 뿐이지,

재귀함수의 여러가지 방법론중 하나라는 것을 알 수 있었다.

코딩을 하면서 재귀함수는 재귀함수지! 하면서 써왔는데,

재귀함수도 그 밑으로 여러 방법들로 나뉠 수 있다는 것을 알게 되었다. 

이론만 보면 뭐라는지 모르겠는데, 막상 적용해보면 쉽거나, 잘만 써왔던 것들이다.

직군 특유의 고질병일지는 모르겠지만, 말로만 들으면 거창하고 세세한 부분까지 개념화 하는게 있다.

확실한건 이론부터 배웠으면 "대체 무슨 말이야!" 하다가 때려쳤을지도 모를 일이라는 것이다.