[Algorithm] 백준 1735

---

문제

풀이

내가 생각한 알고리즘 : 시간초과

1. 수 입력 받기
2. 분모, 분자 계산 후
3. 2부터 돌면서 나누어지면 나누기

코드 : 시간초과

a, b = map(int, input().split(' '))
c, d = map(int, input().split(' '))

e = a*d + c*b
f = b*d

n = min(e // 2, f // 2)

for i in range(2, n):
    if e % i == 0 and f % i == 0:
        e = e // i
        f = f // i

print(e, f)

큰 수가 들어오면 오래 걸려서 그런거 같다.
아마 소수찾기 해야할꺼 같다...ㅠㅠ

주어진 코드에서 시간 초과가 발생하는 이유는 두 가지입니다.

1. 반복문 범위 설정: 주어진 반복문에서는 ( n )을 ( e )와 ( f )의 최소값을 2로 나눈 값까지만 설정하고 있습니다. 그러나 이 범위는 매우 커질 수 있습니다. 예를 들어, ( e )와 ( f )가 매우 큰 수라면 반복문이 매우 오랜 시간이 걸릴 수 있습니다.

2. 최대공약수 계산: 반복문 내에서 ( e )와 ( f )의 최대공약수를 계산하는 과정이 포함되어 있습니다. 이것은 반복문이 매번 실행될 때마다 수많은 계산을 수행하므로 시간이 오래 걸릴 수 있습니다.

시간 초과를 피하기 위해 다음과 같은 개선이 필요합니다:

• 반복문 범위를 설정할 때, ( e )와 ( f )의 최대공약수가 될 수 있는 범위까지만 반복을 실행하도록 수정합니다.
• 최대공약수 계산을 반복문 안에서 수행하는 대신, 유클리드 알고리즘 등을 사용하여 최대공약수를 효율적으로 계산합니다.

이러한 개선을 통해 코드의 성능을 향상시킬 수 있습니다.

내가 생각한 알고리즘 : 틀렸습니다

1. 사용자로부터 두 분수의 분자와 분모를 입력받습니다.
2. find_sosu(num) 함수는 주어진 수 num의 소인수분해를 수행하여 소인수를 리스트로 반환합니다. 이때, 소인수는 중복되지 않게 하기 위해 이미 찾은 소인수는 리스트에서 제거합니다.
3. mo_list에는 분모 b와 d의 소인수 리스트를 합친 결과가 저장됩니다.
4. ch_list1과 ch_list2에는 각각 분자 a, c와 분모 d, b의 소인수 리스트가 저장됩니다.
5. find_same() 함수는 ch_list1과 ch_list2에서 공통된 소인수를 찾아내어 제거하고, 이를 리스트로 반환합니다.
6. same 리스트에는 두 분수의 분자 중에서 공통된 소인수가 저장됩니다.
7. 공통된 소인수가 제거된 후에도 남은 소인수들은 서로 곱하여 최종 분모 result_mother를 구합니다.
8. 남은 공통된 소인수는 서로 곱한 후에 두 분수의 나머지 분자들을 더한 값에 곱하여 최종 분자 result_child를 구합니다.
9. 최종적으로 기약분수로 표현된 분모와 분자를 출력합니다.

암튼 소인수분해를 해서 겹치는거 삭제하는거를 하려고 했다.

코드 : 틀렸습니다.

틀린 코드 1

a, b = map(int, input().split(' '))
c, d = map(int, input().split(' '))

def find_sosu(num):
    list = []
    n = num // 2

    for i in range(2, n):
        if num % i == 0:
            num = num // i
            list.append(i)
    list.append(num)
    return list

mo_list = find_sosu(b) + find_sosu(d)
ch_list1 = find_sosu(a) + find_sosu(d)
ch_list2 = find_sosu(c) + find_sosu(b)

def find_same():
    same_list = []
    for num in ch_list1:
        if num in ch_list2:
            same_list.append(num)
            ch_list1.remove(num)
            ch_list2.remove(num)
    return same_list

same = find_same()

for number in same:
    if number in mo_list:
        same.remove(number)
        mo_list.remove(number)

result_child = 0

def list_to_num(list):
    result = 1
    for number in list:
        result *= number
    return result

result_mother = list_to_num(mo_list)
result_child = list_to_num(same) * (list_to_num(ch_list1) + list_to_num(ch_list2))

print(result_child)
print(result_mother)

틀린 코드 2

# a, b = map(int, input().split(' '))
# c, d = map(int, input().split(' '))

# e = a*d + c*b
# f = b*d

# n = min(e // 2, f // 2)

# for i in range(2, n):
#     if e % i == 0 and f % i == 0:
#         e = e // i
#         f = f // i

# print(e, f)

a, b = map(int, input().split(' '))
c, d = map(int, input().split(' '))

def find_sosu(num):
    list = []
    n = num // 2

    for i in range(2, n):
        if num % i == 0:
            num = num // i
            list.append(i)
    list.append(num)
    return list

mo_1 = find_sosu(b)
mo_2 = find_sosu(d)
mo_list = mo_1 + mo_2

ch_1 = find_sosu(a)
ch_2 = find_sosu(c)
ch_list1 = ch_1 + mo_2
ch_list2 = ch_2 + mo_1

def find_same():
    same_list = []
    for num in ch_list1:
        if num in ch_list2:
            same_list.append(num)
            ch_list1.remove(num)
            ch_list2.remove(num)
    return same_list

same = find_same()
temp = same.copy()

for number in temp:
    if number in mo_list:
        same.remove(number)
        mo_list.remove(number)

result_child = 0

def list_to_num(list):
    result = 1
    for number in list:
        result *= number
    return result

result_mother = list_to_num(mo_list)
result_child = list_to_num(same) * (list_to_num(ch_list1) + list_to_num(ch_list2))

print(result_child)
print(result_mother)

코드가 상당히 거지같다.

유클리드 알고리즘 : 최대공약수 구하기

도저히 모르겠어서 도대체 어떻게 접근을 해야하나 질문 게시판을 통해 확인했다.

유클리드 알고리즘

을 사용하라고 해서 그렇게 했다.
(유클리드 알고리즘 정리는 따로 포스팅했다.)

개선

유클리드 알고리즘 적용하기

입력 값들이 기약 분수가 아닐 수도 있다.
그래서 입력 분수들을 전부 기약 분수로 바꾸어 주고, 곱한 다음에 또 기약 분수로 바꾸었다.

1. 사용자로부터 두 분수의 분자와 분모를 입력받습니다.
2. 두 분수의 분모에 대해 각각 gcd 함수를 사용하여 최대공약수를 구합니다.
3. 구한 최대공약수를 이용하여 각 분수의 분자와 분모를 약분합니다.
4. 약분된 분수들을 이용하여 두 분수의 합을 구한 후, 분자와 분모를 각각 e와 f에 할당합니다.
5. 합쳐진 분수의 분자와 분모에 대해 다시 한 번 gcd 함수를 사용하여 최대공약수를 구합니다.
6. 최종적으로 구한 최대공약수를 이용하여 합쳐진 분수를 약분합니다.
7. 약분된 분수의 분자와 분모를 출력합니다.

이 알고리즘은 주어진 분수를 기약분수로 표현하기 위해 최대공약수를 활용하고, 이를 통해 분수를 약분하는 방식으로 동작합니다.

코드 : 정답

a, b = map(int, input().split(' '))
c, d = map(int, input().split(' '))


# 최대공약수 구해서 약분하기
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
    
temp_1 = gcd(a, b)
temp_2 = gcd(c, d)

a, b = a // temp_1, b // temp_1
c, d = c // temp_2, d // temp_2

e = a*d + c*b
f = b*d

temp_3 = gcd(e, f)
e, f = e // temp_3, f // temp_3

print(e, f)

드디어 정답..

Lesson Learn

• 자료구조 적으로 접근하지 말고 우선 어떻게 하면 간단하게 풀 수 있는지 접근하기
• 알고리즘 공부하기..