[kata][python] 헨리 표현법(Henry Representation) 구현
- 7 mins헨리 표현법 구현하기
헨리 표현법을 구현하는 문제이다.
헨리 표현법은 나도 처음 접한 개념이라 설명이 부족할 수 있다.
이해되지 않는다면 문제 원문에 친절하게 설명되어있으니 참고하면 될 것 같다.
헨리표현법을 간단히 설명하자면 이렇다.
1보다 작은 어떤 분수 a/b가 있을때,
이는 반드시 서로 다른 단위분수들의 합으로 표현이 가능하다.
단위분수는 분자가 1인 분수를 말한다.
예를들어
4/23은 1/5 + 1/138로 표현 가능하다.
5/7은 1/2 + 1/5 + 1/70 으로 표현 가능하다.
다시 정리하면,
1보다 작은 특정 분수를 서로 다른 단위분수의 합으로 나타내는 것 이 헨리 표현법이다.
서로 같은 단위분수가 두 개 이상 포함될 수는 없다.
예를들어 2/3 를 1/3 + 1/3 과 같이 표현하는 것은 헨리 표현법이 아니다.
2/3 의 헨리 표현법은 1/2 + 1/6 이다.
반드시 ‘서로 다른’ 단위분수들의 합으로 나타내야한다.
헨리 표현법은 다음과 같이 간단하게 구할 수 있다.
양의 정수 a,b로 이루어진 1보다 작은 분수 a/b가 있을때,
우선 a/b보다 작은 단위분수중 가장 큰 단위분수를 구한다.
5/7 의 경우,
5/7보다 작은 단위분수중 가장 큰 단위분수는 1/2 이다.
5/7에서 1/2를 뺀다.
즉, 처음 주어진 분수에서 구한 값을 뺀다.
5/7 - 1/2를 하면 3/14이 나오는데,
이제부터 계속 앞에서 했던 짓(?)을 똑같이 해주면 된다.
다시 3/14 보다 작거나 같은 단위분수 중 가장 큰 단위분수를 구한다.
그럼 1/5이 나오고,
다시 3/14에서 1/5을 뺀 값보다 작거나 같은 단위분수 중 가장 큰 단위분수를 구한다.
그런데 이 때,
3/15에서 1/5를 빼면 1/70이 나온다.
1/70 자체가 단위분수이므로,
1/70보다 작거나 ‘같은’ 단위분수중 가장 큰 단위분수는 1/70이다.
즉, 1/70 - 1/70 을 하면 나머지가 0이 나온다.
나머지가 0이 된 시점에서 식을 종료하고, 여태까지 구했던 단위분수들을 더해주면 된다.
1/2 + 1/5 + 1/70
즉, 5/7의 헨리 표현법은 1/2 + 1/5 + 1/70 이다.
이 것을 프로그램으로 구현하는 문제이다.
입력의 첫 번째 줄에는 헨리표현식을 구할 분수의 갯수 T가 주어진다.
그리고 a <= b 인 양의 정수 a, b를 T번 입력한다.
그 후, 각 분수 a/b의 헨리 표현식을 구한다.
헨리 표현식에 포함된 단위분수 중, 가장 작은 단위분수의 분모를 출력한다.
다시 말해, 분모가 가장 큰 단위분수의 분모를 출력한다.
입력
3
4 23
5 7
8 11
출력
138
70
4070
내 풀이1 (시간 초과)
1 import sys
2 from fractions import Fraction
3
4 T = int(sys.stdin.readline())
5
6 def henry(numer, denom):
7 x = Fraction(numer, denom)
8 for i in range(2, denom+1):
9 temp_uf = Fraction(1, i)
10 if temp_uf < x:
11 step = x - temp_uf
12 return henry(step.numerator, step.denominator)
13 elif temp_uf == x:
14 return temp_uf
15
16 for _ in range(T):
17 a, b = map(int, sys.stdin.readline().split())
18 print(henry(a, b).denominator)
henry 함수에 집중해보자.
(6): 분자와 분모(numer, denom)를 받아 헨리 표현식의 가장 큰 분모를 리턴하는 함수이다.
(7): 우선 분자, 분모를 받아서 Fraction 모듈을 이용해 분수 x 를 만들었다.
(8~14): 그리고 x보다 작은 단위 분수를 구하기 위해 분모를 2부터 한개씩 증가시키면서 temp_uf를 만들고, x와 비교한다.
(10~12): 단위 분수가 x보다 작다면, x에서 해당 단위분수를 뺀 값을 다시 henry 함수에 넣어 재귀호출한다.
(13~14): 재귀 함수를 계속 호출하다가 단위분수가 x와 같아지는 순간 (즉, 분모가 가장 큰 최종 단위분수)를 리턴해준다.
(18): 리턴받은 단위분수의 분모(denominator)를 출력한다.
알고리즘 자체에 문제는 없지만,
8번라인부터 시작되는 반복문때문에 시간 초과가 발생한다. (백준 알고리즘 채점 기준)
분모를 2부터 한 개씩 증가시키며 값을 비교하는데,
입력받은 함수의 분모가 커짐에따라 이 반복문도 같이 증가하게된다.
그리고 재귀호출을 반복할수록 분모는 점점 커지게되므로,
결국 입력받은 분모의 크기에따라 수행 시간이 기하급수적으로 늘어나는 것이다.
그래서 다른 풀이를 생각해내야했다.
내 풀이2 (정답)
1 import sys
2 from fractions import Fraction
3
4 T = int(sys.stdin.readline())
5
6 def henry(numer, denom):
7 if numer == 1:
8 return denom
9 else:
10 x = (denom // numer) + 1
11 step = Fraction(numer, denom) - Fraction(1, x)
12 return henry(step.numerator, step.denominator)
13
14 for _ in range(T):
15 a, b = map(int, sys.stdin.readline().split())
16 print(henry(a, b))
반복문이 아예 사라진것을 볼 수 있다.
타임아웃의 원인이되는 반복문을 최소화할 수 없을까 고민하다가 규칙을 발견했다.
예를 들어보자.
5/7에 대한 헨리표현법을 구할때,
우리는 일단 5/7보다 작은 단위 분수 1/x중, 단위 분수의 크기가 최대가 되는 x를 구해야한다.
즉, 1/x <= 5/7 를 만족하는 x의 최대값을 구해야한다.
이 부등식의 양 변에 적절한 값을 곱해 식을 바꿔보면
x >= 7/5 으로 바꿀 수 있다.
여기서 잘 생각해보자.
7/5는 1.4이다.
그러므로 위 부등식을 만족시키는 x는 2이다.
이 2라는 숫자는 사실 1.4에다가 1을 더한 후 소숫점 아래를 버리면 나오는 값이다.
즉, x는 언제나 7/5의 “몫”에다가 1을 더한 값이 되는 것이다!
이를 프로그래밍적으로 표현하면 x = (분모를 분자로 나눈 몫) + 1 이다.
코드의 10번 라인에서 이를 표현하고있다.
이러한 로직으로 재귀함수를 계속 호출하다가,
분자가 1이 되는 순간은 더이상 계산을 하지 않고 바로 분모를 리턴해주면 된다.(line 7~8)
기존에 for문을 사용해 O(N2)의 복잡도를 가지던 알고리즘에 비해,
O(1)의 복잡도로 상당한 성능의 향상을 이끌어냈다.
분석
처음 백준 알고리즘을 접했을때 시간까지 채점 기준으로 잡는 것을 너무 깐깐하다고 생각했지만,
이제는 이것이 프로그램의 평가 기준에 반드시 포함되어야 하는 부분이라는 강한 확신이 든다.
경우에따라 약간의 시간차이가 아닌 어마어마한 시간 차이가 발생할 수 있기 때문이다.
그리고 한줄한줄마다 효율성에 대해 끊임없이 고민하면서 코딩할 수 있어서 도움이 많이 되는 것 같다.
어쨌든 이번에는 다른 사람의 코드와 비교하지 않고, 내가 짠 코드 두 개를 비교했다.
시간초과를 해결하기위해 고민하기 전과 후의 코드가 거의 다른 사람의 코드처럼 다르기 때문이다.
첫 번째 짰던 코드가 그대로 통과 됐었다면 과연 나에게 이런 깊이있는 고민을 할 기회가 있었을까?
프로그래머는 수학을 잘해야한다는 말을 종종 보곤 하는데,
잘하지는 못하더라도 최소한 동떨어져있으면 안된다는 생각이 들었다.
어떠한 문제가 막혔을때 주먹구구식으로 코드를 뜯어고치고 실행을 반복하는 작업 대신,
“한 번 수학적으로 접근해볼까?” 하는 정도의 마인드면 충분할 것 같다.
아주 간단한 수학적인 개념이라도 문제풀이에 지속적으로 적용시키려는 노력이 중요한 것 같다.
기존에는 생각하지 못했던 부분에서 간단한 수식만으로 훨씬 효율적인 알고리즘을 이끌어 낼 수 있다.
어찌보면 이런 사소하다고 생각하는 부분에대한 고민이,
실무에서는 서버가 터지느냐 버티느냐의 문제와 직결된다.
몇 줄의 코드로 소프트웨어의 퀄리티와 수명이 달라지는 것이고,
이는 더 나아가 내가 속한 집단의 수준과 미래를 좌우할 수 있다.
코딩장이
-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.