코딩테스트 10일차(2025.01.24) - 분수의 덧셈(프로그래머스)

내 풀이

분수를 더하는 것.

또한 최대공약수를 구하는 것이 중요하다. 

 

def solution(numer1, denom1, numer2, denom2):
    denom_total = denom1 * denom2
    numer_total = numer1 * denom2 + numer2 * denom1
    
    def s_find(a, b):
        i = min(a, b)  # 두 수 중 작은 값부터 시작
        while i > 0:  # 1까지 탐색
            if a % i == 0 and b % i == 0:  # 공약수인지 확인
                return i
            i -= 1  # 다음 값 검사
        return 1  # 공약수가 없으면 1 반환
            
    asdf = s_find(numer_total, denom_total)
    answer = [numer_total//asdf , denom_total//asdf]
    return answer

 

일단 분수를 더하는 방법을 시행하고 최대공약수를 찾아서 이를 나누어 해결하였다. 

 

최대 공약수를 구하는 방법은 가장 작은 값을 골라 그것을 나누는 값이 분자, 분모의 몫이 0이되는 것을 찾아내는 방식을 사용하였다.

 

분수의 덧셈 문제를 해결하기 위해, 두 분수를 더한 뒤 최대공약수를 이용해 기약 분수로 만드는 방식을 사용하였다.

먼저, 두 분수를 공통 분모로 맞춰 합산한 후, 결과로 나온 분자와 분모의 최대공약수를 구하여 이를 각각 나누어 약분하였다.

 

최대공약수를 구하는 방법으로는 두 수 중 작은 값을 시작점으로 설정하고, 해당 값을 점차 줄여가며 분자와 분모 모두를 나눌 수 있는 가장 큰 값을 찾는 방식을 사용하였다. 이를 통해 효율적으로 최대공약수를 계산하고 결과 분수를 간단히 나타낼 수 있었다.

 

결과: 정답

더 옳은 정답

import math

def solution(denum1, num1, denum2, num2):
    denum = denum1 * num2 + denum2 * num1
    num = num1 * num2
    gcd = math.gcd(denum, num)
    return [denum//gcd, num//gcd]

 

가장 간단한 방법으로는 math함수를 가져와서 하는 방법이 있다. 이외에도 gcd는 파이썬 내장함수이기도 하기에 이를 사용하면 가장 간단한 방법으로 이를 해결할 수 있다. 

 

고찰

질문: 이외에도 코딩테스트를 풀 때 유용한 라이브러리가 있을까?

 

1. math 라이브러리

- math.gcd(a,b): 최대공약수를 구하는 함수로, 유클리드 알고리즘 기반으로 최적화되어 있다.

- math.lcm(a,b): 최소공배수를 구하는 함수

 

2. itertools 라이브러리

- 조함과 순열 등을 다룰 때 매우 유용하다.

- itertools.permutations(iterable, r): 순열 생성

- itertools.combinations(iterable, r): 조합 생성

- itertools.product(*iterables, repeat=1): 모든 곱집합(cartesian product) 생성

 

3. collections라이브러이

- 데이터 구조와 관련된 유용한 클래스를 제공

- Counter: 요소의 빈도수를 계산

- deque: 빠른 삽입/삭제가 가능한 양방향 큐

- defaultdict: 기본값이 있는 딕셔너리

 

4. heapq 라이브러리

- 우선순위 큐(최소 힙/최대 힙)을 구현할 때 사용

- heapq.heappush(heap, item): 힙에 요소 추가

- heapq.heappop(heap): 힙에서 가장 작은 요소 제거 및 반환

 

5. bisect 라이브러리

- 정렬된 배열에서 이진 탐색을 쉽게 구현

- bisect.bisect_left(array, x): 정렬된 배열에서 x가 들어갈 가장 왼쪽 위치

- bisect.bisect_right(array, x): x가 들어갈 가장 오른쪽 위치

 

6. functools 라이브러리

- 고차 함수 관련 유틸리티 제공

- functools.reduce(function, iterable): 누적 합계, 곱 등을 계산