[241210] 프로그래머스 코딩테스트 입문 문제

1. 분수의 덧셈

Q. 첫번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두번째 분수의 분자와 분모를 뜻하는 numer2, denom2 가
매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타내었을 때, 분자와 분모를 순서대로 담은 배열을 return 하도록
solution 함수를 완성해보세요.

A. 프로그래머스는 모듈 적용이 안되니까 일일이 구현을 해줘야 하는데,
어떻게 해줘야 하는지 모르니까 일단 보라선생한테 물어봐서 얻은 코드를 데려와봤습니다.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def solution(numer1, denom1, numer2, denom2):
    # 공통 분모 계산
    common_denom = lcm(denom1, denom2)
    print(f"공통 분모: {common_denom}")  # 4
    
    # 분자 계산
    new_numer1 = numer1 * (common_denom // denom1)
    new_numer2 = numer2 * (common_denom // denom2)
    print(f"조정된 분자1: {new_numer1}")  # 2
    print(f"조정된 분자2: {new_numer2}")  # 3
    
    total_numer = new_numer1 + new_numer2
    print(f"분자 합: {total_numer}")  # 5
    
    # 기약 분수로 만들기
    divisor = gcd(total_numer, common_denom)
    print(f"최대공약수: {divisor}")  # 1
    
    result = [total_numer // divisor, common_denom // divisor]
    print(f"결과: {result}")  # [5, 4]
    return result

 

해당 코드의 원리는
: 최대공약수와 최소공배수를 구하는 기능의 함수를 만들어 줍니다.
최대공약수, 최소공배수 함수들을 가지고 두 분수의 합을 만들어 줍니다.
두 분수의 합을 기약 분수로 나타냈을 때, 분자와 분모를 순서대로 담은 배열을
return 해줍니다.

def gcd(a, b):  # 최대공약수 함수 생성
    while b:  # b가 0이 될 때까지 반복
        a, b = b, a % b  # a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다.
    return a  # 결론적으로 a가 최대공약수가 된다.

 

최대공약수 함수 gcd 를 만들어 줍니다.

while b: 단락에서
while b != 0 과 같은 조건은 명시적으로
달아주지 않아도 됩니다.

기본적으로 0은 False값,
0이 아닌 숫자는 True값으로 평가되는데,
while문은 True일 경우(ex. while b:) 무한 반복되다가
b가 0이 될 경우 False로 평가되어 루프가 종료된다.

while b 인 동안
a, b = b, a % b 이다.
예를 들어,
20(a)과 12(b)의 최대공약수는 20을 12로 나눈 나머지의 최대공약수와 같다.
: 20 / 12 = 1(몫)... 8(나머지)
: 12 / 8 = 1... 4
: 8 / 4 = 2... 0
나머지가 0이 되었으므로 마지막으로 8을 나눈 숫자인 4가
20과 12의 최대공약수가 된다.

좀 더 이해가 쉽게 설명해보자면,
gcd(a, b) = gcd(b, r)
여기서 r은 a와 b를 나눈 나머지 값이다.
위의 예제를 대입해보자면,

20(a) / 12(b) => 12(b) / 8(r) 가 되므로,
위의 예시처럼
: 20(a) / 12(b) = 1(몫)... 8(r)
: 12(b=a) / 8(r=b) = 1... 4
: 8 / 4 = 2... 0
나머지가 0이 나올 때까지
a와 b자리에 b와 r의 수가 대체를 하면서 공약수 찾는
행위를 반복한다.

설령,
a가 b보다 작은 수일 지라도,
마찬가지로 첫 단계에서 두 수의 위치가 정상적으로 교체되어
계산이 진행된다.

ex.
: 18(a) / 48(b) = 0(몫)... 18(r)
: 48(b=a) / 18(r=b) = 2... 12
:18 / 12 = 1... 6
:12 / 6 = 2... 0

나머지가 0이 되었으므로,
18과 48의 최대공약수는 6.
이런 식으로 a가 b보다 수가 작아도 계산이 정상적으로 마무리가 된다.

def lcm(a, b):  # 최소공배수 함수 생성
    return a * b // gcd(a, b)  # a와 b를 곱한 값을 a와 b의 최대공약수로 나눠줍니다.

 

최소공배수 함수 lcm을 생성해줍니다.

예를 들어,
lcm(a, b) 는
: 12 * 18 // gcd(12, 18)
: 12 * 18 = 216
: 216 // (12, 18)의 최대공약수 6
: 36
이므로, 12와 18의 최소공배수는 36이 됩니다.

보다 쉽게 설명하자면,
예를 들어, 4와 6의 최소공배수를 구하려고 한다.
일단 4와 6을 먼저 곱해줍니다.
24는 4와 6의 공배수입니다.

그러나 우리의 목적은 최소공배수를 구하는 것.

그래서 24를 4와 6의 최대공약수로 나눈다.
: 4와 6의 최대공약수 = 2
: 24 / 2 = 12
이렇게 해서 나온 12가 4와 6의 최소공배수이다.

나눗셈을 할 때 /가 아닌 //를 사용하는 이유는,
실수가 아닌 정수 나눗셈(몫)을 보장하기 위해서 // 를 사용합니다.

def solution(numer1, denom1, numer2, denom2):
    # 공통 분모 계산
    common_denom = lcm(denom1, denom2)  # denom1, 2의 최소공배수를 구해줍니다.
    print(f"공통 분모: {common_denom}")  # 4 << 4(최소공배수)가 denom1, 2의 공통분모가 되었음.
    
    # 분자 계산
    new_numer1 = numer1 * (common_denom // denom1)  # 분자1 곱하기 (공통분모 나누기 분모1)
    new_numer2 = numer2 * (common_denom // denom2)  # 분자2 곱하기 (공통분모 나누기 분모2)
    print(f"조정된 분자1: {new_numer1}")  # 2
    print(f"조정된 분자2: {new_numer2}")  # 3
    
    total_numer = new_numer1 + new_numer2  # 분자합은 7번라인 더하기 8번라인
    print(f"분자 합: {total_numer}")  # 5
    
    # 기약 분수로 만들기
    divisor = gcd(total_numer, common_denom)  # divisor 는 (분자합과 공통분모)의 최대공약수
    print(f"최대공약수: {divisor}")  # 1
   
    result = [total_numer // divisor, common_denom // divisor]
    print(f"결과: {result}")  # [5, 4]
    return result

 

common_denom 변수에
denom1과 denom2의 최소공배수를 할당해줍니다.
2와 4의 최소공배수는 4.

new_numer1 변수에
numer1(1) * (common_denom(4) // denom1(2)) 값을 할당.
: 1 곱하기 (4 나누기 2) = 2
new_numer2 변수에
numer2(3) * (common_denom(4) // denom2(4)) 값을 할당.
: 3 곱하기 (4 나누기 4) = 3

total_numer 변수에 new_numer1 + new_numer2 값을
할당해줍니다.
그럼 total_numer의 값은 5.

기약 변수를 만들기 위해서 divisor 변수를 지정합니다.
divisor 변수에 total_numer(5)와 common_denom(4)의
최대공약수를 할당.
이제 divisor 변수의 값은 1.

result = [total_numer // divisor, common_denom // divisor]
: result 는 [5 나누기 1, 4 나누기 1] 이므로
: return result 값은 [5, 4]

아 어렵다^____^
최대한 이해하기 쉽게 적어봄.
혹시나 이해 안가셨던 분들이 계시다면
이 글이 이해에 도움이 됐음 좋겠음다.

---

2. 중앙값 구하기

Q. 중앙값은 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치한 값을 말합니다.
예를 들어, 1, 2, 7, 10, 11의 중앙값은 7입니다. 정수 배열 array 가 매개변수로 주어질 때,
중앙값을 return 하도록 solution 함수를 완성해보세요.

A.

def solution(array):
    answer = 0
    answer = array  # answer 변수에 array 할당.
    sorted_data = sorted(answer)  # answer 값을 정렬해줍니다.
    n = len(sorted_data)  # 정렬된 answer 의 길이값(=데이터 개수)을 변수 n에 할당.
    
    if n % 2 == 0:  # n과 2를 나눈 값의 나머지가 0일 때:
        return (sorted_data[n//2 -1] + sorted_data[n//2] / 2)  # 데이터 짝수형 중앙값 반환
    else:  # 아닐 때(나머지가 있을 경우):
        return sorted_data[n//2]  # 데이터 홀수형 중앙값 반환

 

if n % 2 == 0:
은 데이터의 갯수가 짝수일 경우이다.
이 때는 중앙에 위치한 값이 두 개가 되므로,
두 개 값의 평균을 중앙값으로 치부한다.

(sorted_data[n // 2 - 1] + sorted_data[n // 2] / 2)

: (sorted_data[인덱스 = 해당 데이터가 리스트 내에 위치된 값]
+
sorted_data[인덱스 = 해당 데이터가 리스트 내에 위치된 값] / 2)

(sorted_data[n // 2 - 1] + sorted_data[n // 2] / 2) 에서 - 1이 들어가는 이유는
짝수 개의 데이터에서 중앙값을 구할 때 중간에 위치한 두 값을 정확히 선택하기 위함이다.

1. 짝수 개의 데이터에서 중앙값은 가운데 두 수의 평균.
2. n // 2는 데이터의 중간 지점을 가리킨다. 예를 들어, 6개의 데이터가 있다면 n // 2는 3.
3. 하지만 파이썬에서 리스트의 인덱스는 0부터 시작하므로, n // 2는 실제로 중간 지점 바로 다음 요소를 가리킵니다.
4. 그래서 중간 지점의 왼쪽 값을 선택하려면 n // 2 - 1을 사용해야한다.

예를 들어, [1, 2, 3, 4]라는 리스트가 있다면:

• n // 2는 2이고, sorted_data 는 3입니다.
• n // 2 - 1은 1이고, sorted_data 는 2입니다.

따라서, (sorted_data[n // 2 - 1] + sorted_data[n // 2] / 2)는
: (2 + 3) / 2 = 2.5가 되어 정확한 중앙값을 구할 수 있습니다.

else:
나머지가 존재하는 경우 >> 결국은 데이터 개수가 홀수인 경우다.
홀수 개의 데이터에서 중앙값은 한 개가 되므로,
sorted_data[n // 2] 를 return 합니다.