알고리즘 풀이

[알고리즘] 프로그래머스 | 콜라츠 추측, 부족한 금액 계산하기, 최대공약수와 최소공배수

째깍단 2023. 8. 8. 08:40

콜라츠 추측

답: 

더보기 
def solution(num):
    answer = 0
    if num == 1:
        return answer

    while num != 1:
        if num % 2 == 0:
            num = num // 2
            answer += 1
        else:
            num = num * 3 + 1
            answer += 1
        
        if answer >= 500:
            return -1
        
    return answer

 

 

문제 분석 및 해석

 

콜라츠추측 : 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측

1-1. 입력된 수가 짝수라면 2로 나눕니다. 
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

 

>> 풀이 생각

계속해서 조건을 반복해야하므로 while문을 사용,

 

1. while문 이전에 1인경우 0을 return하는 식을 작성

 

2. while문 조건식과 변화식 작성

  - while문에는 주어진 수가 1이 아닌 경우를 작성,

조건식 : 

  - 짝수인 경우 / 2

  - 홀수인 경우 * 3 +1

변화식 :

  - answer 에 +1을 해주며 500이 될 경우 루프를 빠져나감

 

3. while문 조건을 달성할 경우 return answer값

 

 

 

짚고 넘어갈 것,

print(num)을 실행하자 .0이 붙은 실수형으로 출력이 되었다.

오류는 다행히 생기지 않았지만 본디 정수형으로 푸는 것이 올바르므로 //연산자를 사용하도록 하자.

 

 

*** 파이썬에서 /와 // 차이 

 

/는 실수형 나누기 연산자

result = 7 / 2
print(result)  # 출력: 3.5

 

//는 정수형 나누기 연산자

몫만을 반환한다.

result = 7 / 2
print(result)  # 출력: 3

 

 

부족한 금액 계산하기

답: 

더보기 
def solution(price, money, count):
    need = price * sum([n for n in range(1, count+1)])
    return (need - money) if money < need else 0

 

 

 

산술 평균을 이용한 답변..

def solution(price, money, count):
    return max(0,price*(count+1)*count//2-money)

 

 

문제 분석 및 해석

이용료 price
1번째 1배, N번째 N배의 이용료를 내야함
가진 돈 money에서 count번 타게된다면 부족한 돈을 return
단, 부족하지 않으면 0을 return

 

 

>> 풀이 생각

전체 price를 for range()문을 이용해 구하기

money를 빼고 남은 결과를 return하거나 부족하지 않으면 0을 return하도록 if문 작성

 

 

 

 

과정

바로 리스트컴프리헨션을 쓰기는 어려우니까 하나하나 차근차근 풀었음

 

def solution(price, money, count):
    need = 0 
    for n in range(1, count+1):
        need += price * n

ㄴ 전체 가격 구하기

 

 

    if money >= need:
        return 0
    return (need - money)

구한 값이 money보다 작거나 같으면 0return

아니라면 need에서 money를 뺀 값을 return

 

 

이후 식을 하나씩 줄였다.

 

 

 

최대공약수와 최소공배수

답: 

더보기 
def new(n, m):
    while m != 0:
        n, m = m, n % m
    return n

def solution(n, m):
    answer = []
    if n < m:
        n, m = m, n
        
    # 최대공약수 - 식을 분리하지 않으면 아래에서 최소공배수를 구할수가 없었다.
    new_n = new(n, m)
    answer.append(new_n)
        
    # 최소공배수 구하기
    a = n * m // new_n
    answer.append(a)
    
    return answer

 

 

문제 분석 및 해석

 

n, m 두 수가 주어질 때
[최대공약수, 최소공배수]를 담은 배열 return

 

 

 

*** 최대공약수와 최소공배수 https://imkh.dev/algorithm-gcd-lcm/

구하는 식 예시

 

 

*** 유클리드 호제법 

2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

 

 

 

 

과정

유클리드 호제법을 구현해보고자 했다

 

 

1) 최대공약수 먼저 구하기

 

주어진 수 중 n을 큰 수로 지정하고

m이 0이 아닐 때까지 m과 나머지를 다시 n과 m으로 지정해준다.

 

if n < m:
    n, m = m, n

while m != 0:
    n, m = m, n % m

 

 

 

 

2) 최소공배수를 위한 서로소 구하기

 

while문에 해당 식을 넣었는데, 오류가 발생.

 

num = n // m
numbers.append(num)

ZeroDivisionError: integer division or modulo by zero

 

해당 문제를 해결하려 생각해보니 0으로 나누어지는 경우 오류가 나는 듯

헌데 n과 m을 나눈 몫을 필요로하는게 아님..ㅋㅋㅋ

 

 

 

 

그래서 다시 생각했다.

for문으로 range를 주고 +1해가면서 나누어지는 수를 구하는 식으로... 작성해보자

 

1은 본디 모든 자연수의 약수이므로 2부터 range의 첫번째 인자로 넣어준다

n보다 큰 숫자가 약수가 될수는 없으니 두번재 인자로 n을 넣어주었다 +1

 

나누어떨어지는 것이 약수이므로 n % i == 0 인경우 numbers list에 저장

 

numbers = []
for i in range(2, n + 1):
    if n % i == 0:
        numbers.append(i)

 

 

3) 최소 공배수 구하기

for 문을 돌려 1로 지정한 a에 계속해서 서로소를 곱해주려했음

a = num * a

 

하지만 계산 값이 적절하게 나오지 않음.

 

 

그래서 최소공배수를 구하는 식을 찾아보았음

https://mathbang.net/206#gsc.tab=0

 

두 수 A B

서로소  a, b

최대공약수 G

최소 공배수 L = G * a * b

 

A * B = L * G  이므로 (최소공배수 * 최대공약수) 아래의 식과 같다

A * B = G * a * b * G (최소공배수 * 최대 공약수)

 

 

따라서 구해둔 최소공배수로 A*B 를 나누면 최소공배수를 구할 수 있다!

A * B / G =  G * a * b 

a = n * m // new_n

 

 

수학적 개념이 나오면 모르는 것이라고 겁을 먹게되는 것 같다ㅠ.ㅠ

찬찬히 읽고 생각하고, 찾아보다보면 언젠가는 풀리게 되어있으니 겁먹지말고 도전하기!

저작자표시 동일조건 (새창열림)