[프로그래머스] 09/27 (6)

[N개의 최소공배수]

My answer

def gcd(a,b):
    if(b>a):
        a,b=b,a
    a=a%b
    if(a==0):
        return b
    return gcd(b,a)
    
def solution(arr):
    if(len(arr)%2==1):
        arr.append(1)
    while(len(arr)!=1):
        for i in range(0,len(arr)-1,2):
            arr[i]=arr[i]*arr[i+1]//gcd(arr[i],arr[i+1])
            arr[i+1]=0
        while(arr.count(0)!=0):
            arr.remove(0)
             
    return arr[0]

Another answer

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)


def solution(arr):
    arr.sort()
    temp = 1
    for i in range(len(arr)):
        temp = (arr[i] * temp) / (gcd(arr[i], temp))
    return temp

아래 코드는 재귀함수에서 a,b의 대소를 비교하지 않고 메인함수에서 먼저 정렬한뒤 함수를 실행시켰고, 나는 앞에서부터 건너뛰면서 두개씩 짝지어서 최소공배수를 구하는 방식을 썼는데, 아래 코드는 더 간단하게 그냥 맨앞에서부터 차례대로 최소공배수를 구했다.

[JadenCase 문자열 만들기]

My answer

def solution(s):
    s=s.lower()
    for i in range(len(s)):
        if(i==0 or s[i-1]==" "):
            s=s[:i]+s[i].upper()+s[i+1:]
    return s

.title()

이 문제에서는 공백이 여러개일수도 있어서 적용이 안되지만 .tilte()이라는 단어의 맨앞 글자만 대문자로 바꿔주는 함수가 있다.

[행렬의 곱셈]

My answer

import numpy as np

def solution(arr1, arr2):
    answer=[[]]
    arr1=np.array(arr1)
    arr2=np.array(arr2)
    answer=np.dot(arr1,arr2).tolist()
    return answer

Another answer

def productMatrix(A, B):
    return [[sum(a*b for a, b in zip(A_row,B_col)) for B_col in zip(*B)] for A_row in A]
------------------------------------------------------------------------------------
def productMatrix(A, B):
    answer = []
    for y1 in range(len(A)):
        a=[]
        for x2 in range(len(B[0])):
            n = 0
            for x1 in range(len(A[0])):
                n += A[y1][x1] * B[x1][x2]
            a.append(n)
        answer.append(a)
    return answer

아래 코드는list comprehension으로 우선 맨뒤부터 보면 A의 행 한줄을 가져오고, 이후 zip(*B)를 통해 B의 열을 가져온다. 여기서 *의 의미는 리스트나 튜플을 언팩할 때 사용된다. 이후에 하나씩 곱하는 것이다. 

zip의 언팩: https://m.blog.naver.com/pmw9440/222058936063

2.14 Python 반복가능한 자료형 packing와 unpacking 하기(Zip() 함수)

그 아래코드는 더 직관적인 행렬의 곱셈 코드이다. 나는 numpy로 내장함수인 .dot을 이용하여 했지면 코테에서는 numpy는 사용이 안될 수도 있다고 한다. .dot은 행렬의 곱셈을 하는 함수이고, tolist는 ndarray를 리스트로 바꿔주는 함수이다.

[피보나치수]

My answer

def solution(n):
    answer=pibonachi(n)%1234567
    return answer

def pibonachi(n):
    if(n==0): return 0
    if(n==1): return 1
    return pibonachi(n-1)+pibonachi(n-2)

Another answer

def fibonacci(num):
    a,b = 0,1
    for i in range(num):
        a,b = b,a+b
    return a
-----------------------------------
def solution(n): 
    p = [0 for i in range(n+1)] 
    p[0] = 0 
    p[1] = 1 
    for i in range(2,n+1): 
        p[i] = p[i-2] + p[i-1] 
    return p[n]%1234567
-----------------------------------
def solution(n): 
	f_list = [0,1] 
	for i in range(2,n+1): 
	f_list.append((f_list[i-2]%1234567+f_list[i-1]%1234567)%1234567) 
    return f_list[-1]

우선 내 코드는 런타임에러가 뜬다. 이 이유는 밑에 적겠다. 우선 아래 코드중 첫번째는 파이썬의 동시할당이라는 특징을 이용하여 쉽게 구현하였다. 두번째 코드는 직관적이고 이해하기 쉽게 구현하였다. 세번째 코드도 똑같은 방법인데 여기서 내 코드가 런타임이 뜬 이유가 나온다. 우선 나는 간단하게 재귀함수를 이용하여 피보나치 코드를 짯다. 이론적으로 맞는 코드인데 입력값에 따라서 런타임에러가 뜬다. 요약하면 피보나치수는 기하급수적으로 커지는데 이 수를 int안에 담지 못한다. 따라서  (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재하게 계산하여야 한다고 한다. 자세한 설명은 아래 적겠다. 

---

일반적인 프로그래밍 언어는 CPU에서 제공하는 최소 읽기 단위(word라고 하는 것으로 기억합니다)를 기준으로 변수의 범위를 지정합니다. 일반적인 x86 시스템(인텔이나 AMD가 만든 그거입니다)은 word의 크기가 4byte라고 가정하며, 그렇기 때문에 int라는 자료형은 -2,147,483,648 ~ 2,147,483,647까지의 값만을 표현할 수 있습니다(계산해보시면 총 숫자 개수가232 개입니다. 1 바이트는 8비트니까요)
그래서 프로그래밍을 하면 정수의 범위에 정말! 정말!! 신경을 쓰셔야 합니다. 예를 들어서 2,147,483,647을 저장하고 있는 int 변수에 1을 더하면 그 숫자는 2,147,483,648이 아닌, -2,147,483,648이 됩니다(이는 2의 보수라는 개념으로 인해서 발생하는데, 관심이 있으시면 구글에서 검색해보세요). 다시 말해서, 각각의 변수가 사용하는 자료형은 사용할 수 있는 숫자의 범위가 있고, 이를 벗어나면 예상치 못한 이상한 결과를 내놓는다는 겁니다. 이는 이 글을 보고 계시는 분이 지금 사용하시는 프로그래밍 언어가 1바이트 하나도 소중히 여겨서 프로그래밍 해야하는 시절에 설계됐으며, 그렇기에 프로그래머가 알아서 변수를 범위 내에 둘 만큼 현명하다고 상정하고 있기 때문입니다.
그런데 피보나치 수는 엄청나게 빠르게 증가합니다. 44번째 피보나치 수만 가도 2,971,215,073로 int 범위를 넘어버립니다. 이대로면 피보나치의 수를 구하라는 문제는 int를 사용할 수가 없겠지요? 그런데 우리에게는 고마운 성질이 있습니다. 숫자 A, B, C가 있다고 하면 (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다는 성질입니다. 이 외에도 여러가지 있는데 알고 싶으시다면 모듈러 연산의 성질을 검색해보세요.
그래서 문제가 1234567로 나눈 나머지를 출력하라고 하는 겁니다. 조금만 숫자가 커져도 피보나치는 int로 표현할 수 있는 범위를 넘겨버리는데, 매번 1234567로 나눈 나머지만을 저장하는 것은 int의 범위에서 가뿐하니까요(당연하다면 당연하지만, 1234567로 나눈 나머지는 항상 1234567보다 작습니다). 이 글을 읽고 계시는 분이 문제를 풀 수 없었던 이유는, n번째 피보나치 수라고 구한 숫자가, 이미 int의 범위를 넘긴 상태라 엉망진창이 된 상태일 것이고, 이것을 1234567로 나눈다고 한들 정확한 값을 구하는 것은 불가능했기 때문입니다. 지문이 명백히 잘못된 것이 아니라, 이미 잘못된 값의 나머지 값을 답으로 내놓으셨으니, 정답이 아니라고 한 것입니다. 요약하자면! 열심히 피보나치 수를 계산한 다음에 나올 수를 1234567로 나눈 나머지는 각 연산을 수행할 때마다 1234567로 나누는 것과 완벽하게 동일한 숫자가 나온다는 겁니다
혹시나 이것이 믿겨지지 않는다면 자체적으로 자료형 구분 없이 큰 수를 저장할 수 있는 Python등의 언어를 사용해서 오류가 났던 그대로 구현해보세요. 전부 정답 처리 될 것입니다.

한줄요약: 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다. 

By. 프로그래머스 이준희님 

[최솟값만들기]

My answer

def solution(A,B):
    A.sort()
    B.sort(reverse=True)

    answer=sum(a*b for a,b in zip(A,B))

    return answer

 

[최댓값과 최솟값]

My answer

def solution(s):
    answer=""
    tmp=s.split(" ")
    tmp=[int(i) for i in tmp]
    tmp.sort()
    answer+=str(tmp[0])+" "+str(tmp[-1])
    return answer

Another answer

def solution(s):
    s = list(map(int,s.split()))
    return str(min(s)) + " " + str(max(s))

아래 코드는 내코드에서 우선 map(함수를 실행시키는 함수)를 통해 int함수를 불러옴으로써 내가 list comprehension을 이용한 코드를 하나로 줄였고, 어차피 이미 리스트로 변환되었기 때문에 따로 정렬을 하지 않고 그냥 max,min함수를 이용하여 간단화하였다.