문제

https://www.acmicpc.net/problem/11050

이항계수 내놔! 드리겠습니다! 필요없어!

풀이

일단 이항계수가 뭐냐...

조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

라는데요? 그래서 이거 어케구함?

이렇게요. 악 내눈! 이게머야! 선형대수학 들고왔어요? 아니 저거 조합임. 조합 원래 저렇게 쓰는게 맞아요.

사실 이거 풀이가 투트랙이라서 팩토리얼 코딩해서 조합 쓰거나 math 불러와서 comb 쓰거나 하면 된다. 나는 둘다 해서 둘다 맞았음. 팩토리얼이요? 조합이요?

# n개의 원소 중 r개를 택하는 것이 조합입니다. nCr로 표기합니다. 
def factorial(a):
    factorial = 1
    if a < 0:
        return False
    elif a == 0:
        factorial = 1
        return factorial
    elif a % 1 != 0:
        return False
    else:
        for i in range(int(a),0,-1):
            factorial *= i
        return factorial
# 아 얘는 조합 구하는데 순열이 필요해서 어쩔 수 없음. 
# nCr을 구하는 공식은 n!/r!(n-r)!입니다. 
n = int(input("n에 들어가는 수를 입력해주세요: "))
r = int(input("r에 들어가는 수를 입력해주세요: "))
bunmo = factorial(r) * factorial(n - r)
C = factorial(n)/bunmo
print("{}개의 원소들 중 {}개를 무작위로 선택하는 가짓수는 {}입니다. ".format(n,r,int(C)))

옛저녁에 순열조합도 코딩해서 깃헙에 올려뒀다.

조합으로 직접 계산하기

import sys

N, K = map(int,sys.stdin.readline().split(' '))

# 재귀함수의 재귀함수의 재귀함수의 재귀함수의...
def factorial(a):
    if a == 0:
        return 1
    else: 
        return a * factorial(a-1)

# nCr=n!/r!(n-r)!
bunja = factorial(N)
bunmo = factorial(K) * factorial(N - K)

print(bunja // bunmo)

팩토리얼은 재귀함수 버전인데, 위 코드랑 달리 좀 간소화됐다. 위 코드는 음수, 정수가 아닌 유리수(감마퐝숀 필요함)에 대한 처리가 같이 들어가서 좀 복잡시러운데(놀랍게도 그것도 코딩했음), 백준에서 뭐 팩토리얼 주고 음수 때려박진 않을 거 아뉴. 그래서 간소화했음.

그 밑에 있는 건 조합 구하는 공식이다.

math 불러오기

import sys
from math import comb

N, K = map(int,sys.stdin.readline().split(' '))

# math.comb(조합)
print(comb(N,K))

단 네 줄로 끝내는 방법도 있다. comb(N,K) 입력하면 nCk 바로 나옴. 공식 까먹었다 하시면 저거 쓰십쇼 저것도 맞음.

문제

https://www.acmicpc.net/problem/24723

괴물이 녹색거탑을 내려오는 가짓수를 계산하시오

풀이

이 문제도 패턴만 찾으면 쉽다. 본인은 3개째에서 바로 도출함.

N이 1일때: 2(좌, 우)
N이 2일때: 4(좌-좌, 좌-우, 우-좌, 우-우)
N이 3일때: 8(좌-좌-좌, 좌-좌-우, 좌-우-좌, 좌-우-우, 우-좌-좌, 우-좌-우, 우-우-좌, 우-우-우)

import sys
N = int(sys.stdin.readline())

print(2 ** N)

그래서 이게 답임.

문제

https://www.acmicpc.net/problem/15439

옷 가짓수 찾는 문제.

풀이

옷부자네… 와…

자, 봅시다. 1일때 0인 이유는 서로 다른 색이 없기 때문인거고, 2일때 2인 이유는 각각 하나씩 있기 때문이다. 그럼 3은요? 옷이 검정/회색/하양 이렇게 있다면 검정-하양, 회색/회색-검정, 하양/하양-검정, 회색 이렇게 조합이 가능한데… 가능하면 국물 있는 음식 먹는 날은 흰옷 조심하십쇼. 아무리 조심해도 뭐 묻으니께…

N = int(input())

print(N * (N-1))

근데 답 진짜 심플하다고? 에이 첫빠따부터 빡신거 뜨면 안됨…

문제

https://www.acmicpc.net/problem/27433

N!을 출력하면 되는데, 이제 재귀함수를 곁들이셔야 한다.

풀이

일단 여러분들, 재귀함수가 뭔가요? 그죠 내가 나를 부르고 나를 부르고 나를 부르고 부르고 부르고 하는 게 재귀함수 아닙니까. 그걸로 팩토리얼이 되냐고? 된다. 재귀함수 할 때 기본적으로 해 보는 두 개가 팩토리얼하고 피보나치 수열이다. 그래서 좀 해보신 분들한테는 되게 쉬운 문제다.

N = int(input())

# 팩도리얼을 재귀함수로 구현해보자... 
# n! = n * (n-1) * (n-2) * ... * 1이다. 
def factorial(N):
    # 0! = 1
    if N == 0:
        return 1
    # 재귀함수는 내가 나를 부르는 구조임을 잊지 맙시다. 
    else: 
        N *= factorial(N-1)
        return N

print(factorial(N))

함수 안쪽에 있는 것까지 N으로 깔맞춤할 필요는 없다. 여기서 크게 신경써야 하는 두가지는 0!에 대한 처리랑 팩토리얼을 재귀함수로 구현하는건데, 0!은 1이기때문에 if문을 써서 0이 들어오면 1을 내놓거라 하면 되고, 나머지는 n! = n * (n-1) * (n-2) * ... * 1이니까 N * 팩토리얼(N-1) 하면 된다. 괄호 안쪽을 N-2로 수정하면 이중계승도 된다. 

문제

https://www.acmicpc.net/problem/2566

주어진 9*9 배열에서 최댓값을 찾고, 최댓값과 좌표를 출력하시오.

Reference

https://dev-won0313.tistory.com/entry/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EC%A0%84%EC%B2%B4-%EA%B0%92-%EC%A4%91-%EC%B5%9C%EB%8C%80-%EC%B5%9C%EC%86%8C-%EA%B0%92-%EA%B5%AC%ED%95%98%EA%B8%B0

https://minjoos.tistory.com/2

풀이

요즘 부트캠프를 듣는데, 거기 강사님이 항상 하시는 말씀이 주석 많이 달아라+코드 짜기 전에 설계부터 해봐라(뭘 어떻게 구현할지)임. 그래서 이번 풀이도 그렇게 해봤다.

이번 문제의 코드는 총 3단계… 아니 모듈은 빼… 어차피 sys 불러오는게 다임. 출력도 뭐 없으니가 걍 빼셈. 그래서 3단계가 뭔데요? 일단 2차원 배열 만들고, 2차원 배열에서 최댓값을 찾고, 최댓값 좌표 찾을거다.

2차원 배열 생성

array = [0 for i in range(9)]
coord_list = [] # 최댓값 인덱스 저장할 리스트

for i in range(9): 
    array[i] = list(map(int, sys.stdin.readline().split()))
# 배열 만들기가 너무 힘듭니다

coord_list는 최댓값 인덱스 저장하는 리스트고, 2차원 배열은 array에 만들거다. 이거는 예전에 2차원 배열 만들었던 거 활용해서 list, map 써서 만들었음. 최종 제출은 9*9인데 테스트 하면서 9*9 입력하기 귀찮아서 테스트는 3*3으로 먼저 했다.

최댓값을 찾아서

# 여기서 끝이 아니다. 최댓값 찾아야 한다. 
# 2차원 배열은 max 두개 겹치면 될 줄 알았죠? 나도 그렇게 생각했어요. 
arr_max = max(map(max, array))

이게요… 지금 한줄로 압축된거지 진짜 개삽고생도 이런 개삽고생이 없었어요… 아니 2차원 배열인데 max 두 번 하면 되지 않아요? 그렇게 생각했던 시절이 나한테도 있었어… 근데 max 두 번 주면 어떻게 되게?

[[1, 6, 65], [35, 47, 38], [8, 13, 21]] 47

이 배열의 최댓값은 65인데 뜬금포로 47이 왜 나오는겨? 그래서 방법 찾다가 map을 알게 된 것이다. 일단 왜 65가 아니라 47이 최댓값이 된 건지부터 알아보자.

[[6, 8, 13], [35, 31, 23], [22, 70, 54]] 35 70 # 1
[[1, 99, 90], [48, 7, 32], [9, 44, 54]] 48 99 # 2
[[33, 68, 73], [22, 82, 10], [11, 95, 74]] 73 95 # 3
[[13, 22, 71], [66, 21, 2], [40, 48, 29]] 66 71 # 4
[[11, 73, 75], [1, 88, 90], [5, 7, 2]] 75 90 # 5

이 배열들은 내가 왜 그런지를 보기 위해 테스트용으로 만들어본 배열이다. [] 안에 있는 게 배열이고 그 옆은 max 두 번 겹쳐서 쟤가 최댓값이라고 내놓은 결과물이고 맨 오른쪽은 진짜 최댓값. 그니까 map 줘서 찾은 최댓값 말하는거다. 잘 보면 max 두 번 줘서 최댓값이라고 내놓은 값들이 어디에 있나요?

[35, 31, 23] -> 35
[48, 7, 32] -> 48
[33, 68, 73] -> 73
[66, 21, 2] -> 66
[11, 73, 75] -> 75

이제 이 배열의 0번째 값을 다른 행의 0번째 값과 비교해보자. 어? 최댓값이 들어있는 행의 0번째 값보다 큰데요? 그게 문제라는거다. 진짜 최댓값이 숨어있는 행의 0번이 작은 수면 max만 두 번 써서는 아예 다른 행으로 가버린다는 것.

[75, 90, 7] 90

왼쪽은 list(map(max, array)), 오른쪽은 max(map(max, array))를 준 결과이다. 쟤는 어떻게 최댓값을 찾았냐면 행마다 제일 큰 값을 찾아서 1차원 배열로 만든 다음 거기서 다시 최댓값을 찾은 것이다. 그래서 찐 최댓값이 나온 것. 여기까지 이해 하셨죠?

배열에서 최댓값 좌표 찾기

# 9*9 배열로 고정되어있음
for x in range(9):
    for y in range(9):
        # 배열의 인덱스 값이 최댓값임?
        if array[x][y] == arr_max:
            # 어 내놔 근데 1 더해서(파이썬은 0부터 셈)
            coord_list = [x+1,y+1]

여기는 아까보다 쉽다. x랑 y는 각각 0부터 8까지가 되고, 이게 배열의 좌표가 된다. 그리고 [0][0]부터 시작해서 쭉 배열 순회를 돌다가 최댓값(아까 찾아서 변수에 저장함)을 발견하면 좌표를 아까 선언했던 좌표 리스트에 넣어두면 되는데! 아니! 넣지마! 아직 넣지마!!! 그냥 넣으면 틀려!!!

파이썬 인덱싱은 0부터 시작인데 우리 좌표 출력할때 1부터 시작하잖음. 그러면 최댓값이 3열 4행에 있으면 3, 4가 나와야 되는데 2, 3이 나온다. 그럼 어떻게 하냐고? 각 좌표에 1 더하십쇼.

import sys

array = [0 for i in range(9)]
coord_list = [] # 최댓값 인덱스 저장할 리스트

for i in range(9): 
    array[i] = list(map(int, sys.stdin.readline().split()))
# 배열 만들기가 너무 힘듭니다

# 여기서 끝이 아니다. 최댓값 찾아야 한다. 
# 2차원 배열은 max 두개 겹치면 될 줄 알았죠? 나도 그렇게 생각했어요. 
arr_max = max(map(max, array))

# 9*9 배열로 고정되어있음
for x in range(9):
    for y in range(9):
        # 배열의 인덱스 값이 최댓값임?
        if array[x][y] == arr_max:
            # 어 내놔 근데 1 더해서(파이썬은 0부터 셈)
            coord_list = [x+1,y+1]

print(arr_max) # 최댓값
print(*coord_list) # 찍어라 좌표

이거… 내기 전에 한가지 확인하셔야 할 게 있다. 좌표 출력하는데 그냥 coord_list 내놓고 이 코드 따라했는데 틀렸잖아요!! 하지 마십쇼. 출력 형식이 x, y라 배열 안에서 걔네를 꺼내야 하니까. 아니 그럼 님은 뭐 했는데요? 저기 배열 이름 옆에 애스터리스크(*) 보임? 언패킹 해서 냈음.

문제

https://www.acmicpc.net/problem/13909

마지막에 열려있는 창문의 개수는 몇 개인가?

풀이

문제가 얼탱이없어서 뇌정지 오는 것에 비하면 풀이 진짜로 별거 없다. 수학책에서 소금물 농도 계산하던건 양반이여.

일단 이 문제, 입력이 3일떄 왜 1이냐... 일단 1번이 모든 창문을 열고 시작해서 그렇다. 2, 3까지는 다 공통적으로 1인데 2, 3번에 해당하는 사람이 자기 창문을 닫고 땡이거든. 그 뒤로 한 4, 5까지는 머릿속에서 계산이 되는데 6부터는 이제 암산으로 하기 빡세거든요? 그래서 내가 그려봤음.

여기까지만 보고 패턴을 찾는 분도 계실텐데, 일단 소수인 창문은 한 번 닫고 나면 안 열린다. 합성수의 경우 약수가 홀수개면 열리고, 약수가 짝수개면 최종적으로 닫힌다. 그래서 위 그림에서 4는 열고->닫고(2)->열고(4) 해서 최종적으로 열려있는 상태고, 6은 열고->닫고(2)->열고(3)->닫고(6) 해서 최종적으로 닫혀있는 상태. 이렇게 하면 열려있는 창문이 몇 개인지 쉽게 도출 가능하다.

그리고 잘 봐봐요. 1부터 3까지는 1이고, 4부터 8까지는 2고, 9부터 15까지는 3이고, 16부터 얼마까지인지는 모르지만 4잖아요. 숫자가 바뀌는 시발점이 1, 4, 9, 16이다. 이거 보고 뭐 오는 거 없어요? 없으시면 유튜브에 정승제 50일 수학 치고 루트편 보고 오십쇼. 어? 루트? 이거 설마? 그래요! 루트를 때려! 그거야!

자, 봐봐요. 루트는 제곱해서 n이 되는 수잖아요. 1의 제곱근은 1이고 4의 제곱근이 2면 루트 2, 루트 3은 얼마겠음? 아니 자세히는 몰라도 2, 3이 4보다 작으니까 루트 2, 루트 3은 2와 1 사이의 어딘가에 있을 거 아닙니까.

1.0 1.414 1.732 2.0

순서대로 루트 1, 루트 2, 루트 3, 루트 4다. 이제 감이 좀 오십니까? 그럼 5부터 9까지는요?

2.236 2.449 2.646 2.828 3.0

루트 4가 2고 루트 9가 3이니까 루트 5부터 루트 8까지는 다 2와 3 그 어딘가에 있을 거 아닙니까. 근데 쟤는 2잖아요. 아니 그니까 소수점을 떼야죠. ceil 말고 round 말고 floor 줘야지!

import sys
N = int(sys.stdin.readline().strip())

print(int(N ** 0.5))

그래서 이게 답이다. 1/2승 하면 제곱근임.

문제

https://www.acmicpc.net/problem/17103

주어진 짝수의 골드바흐 파티션 개수 출력하기(인데 함정맛...)

Reference

https://ps.dabyeol.com/solutions/boj/17103/python

https://www.acmicpc.net/board/view/82413

https://wikidocs.net/21638#google_vignette

풀이

9020번 이후로 오래간만에 돌아온 골드바흐 추측이다. 참고로 골드바흐 추측은 '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.'이고 9020번과 달리 이번에는 골드바흐 파티션이 몇개인지를 뽑아야 한다. (9020번 문제는 차가 제일 작은거 하나 뽑았음)

import sys

T = int(sys.stdin.readline())

def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

prime = []
for i in range(1,10001):
    if isprime(i):
        prime.append(i)

for i in range(T):
    N = int(sys.stdin.readline())
    goldbach_count = 0
    goldbach_endpoint = N // 2
    for j in range(1,goldbach_endpoint+1):
        if j in prime and N - j in prime:
            goldbach_count += 1
    print(goldbach_count)

어? 9020번 코드 수정해서 내도 돼요?

아뇨 시간초과가 반기니까 내지 마십쇼. 내가 냈다가 시간초과 세번먹음.

뜬금포로 시간초과가 뜨길래 이게 뭐여 했는데, 위에 함수 정의해둔 걸 빼고 아예 에라토스테네스의 체 배열로 만들어야 한단다. 그니까 저것도 로직은 맞는데 일일이 계산해야 해서 시간을 잡아먹는다.

import sys

T = int(sys.stdin.readline())

a = [False, False] + [True] * (T - 1)
primes = []

for i in range(2,T+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i,T+1,i):
            a[j] = False

print(primes)

이게 에라토스테네스의 체인데 문제가 하나 있다. 얘가 맞아요 맞는데 문제 풀 때 이걸로 하면 인덱싱 잘못되니까 이걸로는 하지 말자. 이것도 내가 시행착오 겪어보고 알려주는거니까 새겨들으십시오. 22 입력했는데 숫자 이상해서 출력해보니까 합계 88떴어...

import sys

isprime = [True] * 1000001
isprime[0:2] = [False, False]
for i in range(2, 1001):
    if isprime[i]:
        for j in range(i * 2, len(isprime), i):
            isprime[j] = False

T = int(sys.stdin.readline())

for i in range(T):
    N = int(input())

    count = 0
    for i in range(2, N // 2 + 1):
        if isprime[i] and isprime[N - i]:
            count += 1

    print(count)

찢었다 4트째에 해냄...

일단 내가 위에서 로직 맞는데 인덱싱 망한다고 쓰지 말라고 한 거랑 차이점이 뭐냐면 위 코드는 소수여야 리스트에 넣는다. 그니까 11번째가 11이라는 보장이 없음. 반면 아래 코드는 합성수여도 False로 들어가 있어서 11번째가 11이 된다. 그니까 위쪽 리스트는 소수'만' 있는 리스트라 인덱싱 망하는 것.

문제

https://www.acmicpc.net/problem/4134

주어진 숫자보다 같거나 큰 소수를 출력하시오. (예: 6->7)

풀이

이 문제를 풀기 위해서는 필요한 게 하나 있다.

def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

바로 에라토스테네스의 체를 예전에 백준 푼다고 루트 N 버전으로 코딩한게 그것. 근데 저거 저대로 쓰면 틀리고요… 내 경험담임 님들은 한방에 맞추십셔…

def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 2: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

아무튼 0이랑 1은 애초에 소수고 나바리고 못 매기니까 걍 예외처리 합시다.

K = int(sys.stdin.readline())

for i in range(K):
    T = int(sys.stdin.readline())
    while isprime(T) == False:
        T += 1
    print(T)

우리 늘 그래왔듯이… 입력은 쉽다. 로직이 문제지… 근데 문제를 보면 주어진 수보다 '같거나 큰' 소수를 출력하라고 되어 있다. 그래서 체 갖고왔잖아요? 그리고 같거나 큰 소수를 찾기 위해 저 체를 쓸 거다. 같거나 큰 소수가 나올때까지 뺑뺑이를 돌려야 하니 반복문으로 While이 온 거고. 여기까지 이해 되셨죠?

isprime()에 소수를 넣었을때는 True, 합성수를 넣었을때는 False가 나온다. 그럼 왜 While문에 저런 조건이 붙었는지도 이해할 수 있다. False 떴으면 합성수니까 1을 더해서 소수 나올때까지 반복문 뺑뺑이 돌라는 얘기. 쉽죠?

import sys

def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 2: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True
    
K = int(sys.stdin.readline())

for i in range(K):
    T = int(sys.stdin.readline())
    while isprime(T) == False:
        T += 1
    print(T)

그래서 이거 내고 맞았다. 

문제

https://www.acmicpc.net/problem/2485

간격을 일정하게 심으려면 나무가 최소 몇 개 필요한가?

Reference

https://jyzinn.tistory.com/111

https://blockdmask.tistory.com/525

풀이

일단 지금까지 풀었던 문제에는 다 유클리드 호제법이 들어가 있는데, 이번 문제는 그렇게 할 수가 없다. 왜냐하면 유클리드 호제법 함수는 숫자가 두개 들어가는데 풀다보면 나오는 나무 간격이 세개거든... 아니, 네개 다섯개도 될 수 있는데... 이게 왜 문제냐고? 간격이 세 개면 유클리드 호제법을 세 번 돌아야 하고, 네 개면 6번, 5개면 10번 돌아야 한다. n개면 nC2다. 이거 이거면 진지하게 메모리 초과는 둘째치고

이 소리 듣기 딱 좋습니다.

import sys
import math

K = int(sys.stdin.readline().strip())
tree_list = []

for i in range(K):
    tree_loc = int(sys.stdin.readline().strip())
    tree_list.append(tree_loc)

tree_list.sort()

항상 그렇듯 입력에서 고민할 필요는 없다. sort는 혹시 몰라서 해줬음…

tree_gap = []

for i in range(1, K):
    gap = tree_list[i] - tree_list[i-1]
    tree_gap.append(gap)

tree_gcd = math.gcd(*tree_gap)
# math.gcd는 숫자만 넣을 수 있기 때문에 리스트는 언패킹을 해 줘야 한다

위에서 내가 유클리드 호제법 함수는 두개밖에 안들어가서 나무 간격이 많아질때마다 저거 돌리는 횟수도 늘어난다고 했는데, math에 있는 gcd는 숫자? 다 들어오라고 전해라! 가 된다. 근데 대신에 리스트나 튜플은 언패킹(리스트 안에 있는걸 풀고 요소만 넣는거라고 보면 된다)을 해 줘야 구할 수 있기 때문에 앞에 애스터리스크가 붙은 것. 애스터리스크가 붙어있으면 언패킹하라는 얘기다.

아, 저거 안 틀리냐고? 다른 풀이에도 다 저거 쓴다.

tree_add = 0
for i in tree_gap:
    tree_add += (i // tree_gcd) - 1

print(tree_add)

tree_gap을 통해 tree_gcd를 구했으면 인제 걔가 나무 간격의 공차가 되는거다. 그러면 나무 사이사이 몇 개가 비는지를 추가할건데, 예시에 있는 1, 3, 7, 13을 예로 들면 tree_gap은 2, 4, 6이 된다. 그러면 공차가 2니까(간격들의 최대공약수가 2) 첫번째는 간격을 여기서 더 나누지 않아도 된다. 그리고 4의 경우 둘로 나누려면 가운데에 나무 하나를 심어야 하니까 1, 6은 나무 두 개를 심어야 하니까 2. 1 안 빼면 각각 1, 2, 3 나와서 틀려요.

import sys
import math

K = int(sys.stdin.readline().strip())
tree_list = []

for i in range(K):
    tree_loc = int(sys.stdin.readline().strip())
    tree_list.append(tree_loc)

tree_list.sort()

tree_gap = []

for i in range(1, K):
    gap = tree_list[i] - tree_list[i-1]
    tree_gap.append(gap)

tree_gcd = math.gcd(*tree_gap)
# math.gcd는 숫자만 넣을 수 있기 때문에 리스트는 언패킹을 해 줘야 한다

tree_add = 0
for i in tree_gap:
    tree_add += (i // tree_gcd) - 1

print(tree_add)

근데 그 가로수 설마 은행나무는 아니겠지...

문제

https://www.acmicpc.net/problem/1735

분수 두 개의 합을 '기약분수'로 출력하시오

풀이

이거는 우리가 초등학생때 배웠던 약분과 통분을 활용해 풀어야 하는 문제이다. 통분은 더할라면 필요하고 약분은 기약분수 만들라면 필요하다. 그러면 뭐 갖고와야 하냐고요?

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

유클리드 호제법이요.

이 문제는 투트랙으로 접근할건데 첫번째로 두 줄에 걸쳐 입력되는 두 개의 숫자가 분자, 분모인 분수 두 개라는 걸 컴퓨터에게 인식시킨 다음 통분해서 더하고, 두번째로 만약 통분해서 더했는데 분자분모가 서로소가 아닐 경우 약분해서 기약분수(분자분모가 서로소인 분수)로 만들거다.

n_bunja_1 = bunja_1 * bunmo_2
n_bunmo_1 = bunmo_1 * bunmo_2

n_bunja_2 = bunja_2 * bunmo_1
n_bunmo_2 = bunmo_2 * bunmo_1

sum_bunja = n_bunja_1 + n_bunja_2
sum_bunmo = n_bunmo_1

이거 생각해보니 분모 굳이 두줄로 안 만들어도 될 것 같음. 어차피 통분해서 분모 하나임. 즉, n_bunmo_1과 n_bunmo_2는 같은 수다. 아 메모리 낭비다 그죠... 근데 이걸 내고 글쓰다가 알았음... 아무튼, 분자랑 분모를 계산했다면 통분하고 더하는 절차는 끝난거다. 이제 기약분수 만들자.

GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

유클리드 호제법에서 두 수가 서로소일 경우 출력이 1이다. 즉, 두 수가 서로소가 아닐 경우(최대공약수가 존재할 경우) 출력이 1이 아니다. 그러니까 GCD가 1이 아니면 나눠라 이거임.

import sys

bunja_1, bunmo_1 = map(int, sys.stdin.readline().split()) # 분수 1호
bunja_2, bunmo_2 = map(int, sys.stdin.readline().split()) # 분수 2호

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

# 1. 일단 통분해서 더한다

n_bunja_1 = bunja_1 * bunmo_2
n_bunmo_1 = bunmo_1 * bunmo_2

n_bunja_2 = bunja_2 * bunmo_1
n_bunmo_2 = bunmo_2 * bunmo_1

sum_bunja = n_bunja_1 + n_bunja_2
sum_bunmo = n_bunmo_1

# 2. 분자와 분모가 서로소가 아닐 경우 기약분수로 나타낸다
GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

print(sum_bunja, sum_bunmo)

근데 아직 내지 말고 일단 보십시오. 이 코드, 로직은 이상 없어서 내도 맞는데 문제가 하나 있다. 두 분수의 분모가 같다면 굳이 통분을 할 필요는 없잖음? 물론 약분은 해야겠지만. 1/4+1/4은 2/4니까 약분하면 1/2이잖아요. 그래서 거기에 대해 if문 하나를 추가할거다.

import sys

bunja_1, bunmo_1 = map(int, sys.stdin.readline().split()) # 분수 1호
bunja_2, bunmo_2 = map(int, sys.stdin.readline().split()) # 분수 2호

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

# 1. 일단 통분해서 더한다

if bunmo_1 == bunmo_2: # 근데 두 분수의 분모가 같으면 통분 안해도 되잖아요? 
    sum_bunja = bunja_1 + bunja_2
    sum_bunmo = bunmo_1
else: 
    n_bunja_1 = bunja_1 * bunmo_2
    n_bunmo_1 = bunmo_1 * bunmo_2

    n_bunja_2 = bunja_2 * bunmo_1
    n_bunmo_2 = bunmo_2 * bunmo_1

    sum_bunja = n_bunja_1 + n_bunja_2
    sum_bunmo = n_bunmo_1

# 2. 분자와 분모가 서로소가 아닐 경우 기약분수로 나타낸다
GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

print(sum_bunja, sum_bunmo)

그니까 이게 두 분수의 분모가 같으면 통분따원 생략하고 걍 계산하게 한거다. 근데 4줄 추가했을 뿐인데 4밀리초 느려지네… 이거 한줄당 1밀리초인가요?

문제

https://www.acmicpc.net/problem/13241

1934번이랑 같은 문제다. 두 수의 최소공배수를 출력하면 된다.

풀이

https://koreanraichu.tistory.com/329

일단 이걸 보고 오면 추가적인 설명이 필요 없을 정도로 명확하게 이해가 될 것이다. 왜냐하면 같은 문제거든.

import sys

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

N, M = map(int, sys.stdin.readline().split())

GCD = Euclidean(N,M)
LCM = GCD * (N // GCD) * (M // GCD)

print(LCM)

진짜로 이거 내면 맞는다. LCM은 최소공배수, GCD는 최대공약수. 그럼 이 시점에서 여러분들은 한가지가 궁금할것이다. 아니, 아무리 백준이라지만 똑같은 문제를 두번이나 낸다고요? 왜?

마우스로 그어서 좀 삐뚤게 됐는데 아래를 잘 보자. C/C++과 자바에는 제약이 있는 것을 알 수 있다.

몇 번 풀이였는지는 모르겠는데 아무튼, C언어에서는 숫자 크기에 따른 정수 형태가 정해져 있다고 했었다. 그래서 파이썬이면 걍 풀어도 되는 문제인데 C언어에서는 어유 이게 뭔 괴랄한 풀이인가 싶은 문제가 있었음.. 아마 큰 수 A+B였을건데... 이것도 그거 비슷한 듯 하다.

문제

https://www.acmicpc.net/problem/11478

입력받은 문자열에서 서로 다른 부분 문자열이 몇 개인지 세면 된다.

Reference

https://reo91004.tistory.com/140

설마사카 이중 반복문으로 풀다니...

풀이

일단 부분 문자열이 뭐냐면 문자열의 일부분을 떼어낸 걸 말한다. 문제에 있는 ababc의 경우 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc 이렇게 열다섯개인데 여기서 중복 쳐내서 12개다. 파이썬은 set() 만들고 거기에 넣어두면 중복 알아서 쳐내니까 부분 문자열을 잘 골라내기만 하면 된다.

import sys

S = sys.stdin.readline().rstrip()

input()은 상관 없는데 sys.stdin.readline()으로 입력받을때는 반드시! 공백을 뗍시다... 안그러면 초유의 사태 터진다.

for i in range(len(S)):
    for j in range(i, len(S)):
        alphabet_set.add(S[i:j+1])

시간초과 뜰 줄 알았는데 저걸로 클리어가 될줄이야... 아무튼 이 반복문의 골자는 이렇다. i는 S의 길이만큼이기때문에 0부터 len(S)-1까지 생긴다. 그러면 j는 0부터 len(S)-1, 1부터 len(S)-1 이런 식으로 범위가 줄어들게 된다. 근데 뒤에 j+1은 왜 있냐고? ababa면 len(S)로 범위 잡았을때 길이가 5니까 0부터 4까지가 되는데, 여기서 j+1을 안하고 슬라이싱을 하게 되면 정말 핵 초유의 사태가 터지게 된다. 바로... 마지막 글자가 없어!!! 안잡혀!!! 슬라이싱도 m 이상 n 미만이라j가 4일때 [0:4]로 슬라이싱하면 0부터 3까지 나온다. 그리고 i가 범위인데 j 때려버리면 첫빠따에 공백 나오더라...

import sys

S = sys.stdin.readline().rstrip()
alphabet_set = set()

for i in range(len(S)):
    for j in range(i, len(S)):
        alphabet_set.add(S[i:j+1])

print(len(alphabet_set))

아무튼 set 만들어서 자른거 넣고 set 길이 출력하면 된다. 빈 세트 만든다고 {}쓰면 딕셔너리 되니까 set() 하십쇼.

아, 위에서 내가 sys.stdin.readline()은 반드시 공백인지 줄바꿈인지 아무튼 떼라고 했는데(strip() 혹은 rstrip()을 붙이면 된다) 안떼면 어떻게 되냐고?

이렇게요. 저건 예시에 있는건데

저기서 겹치는거 다 쳐내면 12개가 맞다. 안 떼고 걍 돌리면 위처럼 대참사 터지니까 반드시 strip()이나 rstrip()을 붙이고 그거 까먹음각 보이면 걍 인풋 쓰십쇼.

문제

https://www.acmicpc.net/problem/1269

두 집합의 차집합들의 길이 합을 출력해보자

풀이

이거 풀이가 투트랙인데 둘 다 맞긴 맞았다.

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

일단 기본 골자인 입력 받아서 집합 만드는 건 같다. 대신 입력이 한 줄에 공백으로 나누어져 있기 때문에 map을 쓸 것이다. 그 왜 가끔 풀이에 리스트(맵(뭐시기)) 있는 그런거 말하는거다. 여기서는 리스트 말고 셋.

첫번째 풀이

x_y = set_x - set_y # X-Y
y_x = set_y - set_x # Y-X

일단 집합 X와 집합 Y가 있을 때, 두 집합의 차집합은 뭐에서 뭘 빼느냐에 따라 다르다. X에서 Y 뺀거랑 Y에서 X 뺀거랑은 다른거다. 즉, 차집합에 교환법칙따원 성립하지 않는다. 그니까 정직하게 쌍방 빼서 차집합을 구하면 된다.

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

x_y = set_x - set_y # X-Y
y_x = set_y - set_x # Y-X

symmetry_cha = len(x_y) + len(y_x)

print(symmetry_cha)

그리고 차집합 길이 두개 더해서 정직하게 출력하면 된다. 끝.

두번째 풀이

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

union_xy = set_x | set_y
intersection_xy = set_x & set_y

print(len(union_xy - intersection_xy))

벤 다이어그램 있으면 이해하기 쉬운데...

여기 두 집합이 있으면 이 문제에서 구해야 하는 부분이

여기 빨간색으로 칠한 부분이다. 그리고 

분홍색이 합집합이고 보라색이 교집합이다.

그리고 초록색 선이 우리가 문제에서 구할 부분이니까 합-교하면 되잖음.

둘 다 제출해서 맞긴 맞았는데, 두번째 풀이는 메모리 사용량이랑 소요시간이 첫번째 풀이에 비해 조금 더 길다. (아래가 첫번째 풀이, 위에가 두번째 풀이) 그니까 코드 길이는 두번째 풀이가 좀 더 간소하지만, 메모리 사용량이나 소요시간을 놓고 본다면 첫번째 풀이가 좀 더 효율적이라고 할 수 있다.

문제

https://www.acmicpc.net/problem/1764

두 집합(듣지 못함/보지 못함)의 교집합을 출력하시오

풀이

이 문제는 굉장히 심플한 문제다. 푸는 것 자체는 그런데 출력이 씁...

import sys

N, M = map(int, sys.stdin.readline().split())

not_heard = set() #듣지 못한 사람
not_saw = set() # 보지 못한 사람

for _ in range(N):
    not_heard.add(sys.stdin.readline().rstrip())

for _ in range(M):
    not_saw.add(sys.stdin.readline().rstrip())

일단 집합(set)을 두 개 만들건데, 첫번째는 듣지 못한 사람이고 두번째는 보지 못한 사람이다. 아니 입력 순서가 듣-보임. 아무튼, 빈 집합을 만들고 입력 받자마자 추가하게 해 준다. 혹시나 중복되더라도 set 자료형은 알아서 중복 걸러주니까 걱정 ㄴㄴ.

not_heard_saw = not_heard & not_saw
not_heard_saw = list(not_heard_saw)
not_heard_saw.sort()

print(len(not_heard_saw))
for i in not_heard_saw:
    print(i)

다음은 출력인데... 일단 아래 세 줄은 길이와 요소를 출력하는거니까 설명은 생략한다. 솔직히 이거 풀 짬이면 다들 알잖아요 뭔지...

위의 세 줄은 순서대로 1) 교집합을 구하고 2) 그걸 리스트로 바꿔서 3) 정렬하는 코드이다. 출력 사전순이니까 정렬해야지.

import sys

N, M = map(int, sys.stdin.readline().split())

not_heard = set() #듣지 못한 사람
not_saw = set() # 보지 못한 사람

for _ in range(N):
    not_heard.add(sys.stdin.readline().rstrip())

for _ in range(M):
    not_saw.add(sys.stdin.readline().rstrip())

not_heard_saw = not_heard & not_saw
not_heard_saw = list(not_heard_saw)
not_heard_saw.sort()

print(len(not_heard_saw))
for i in not_heard_saw:
    print(i)

그래서 놀랍게도 이걸로 한방에 맞췄다.

문제

https://www.acmicpc.net/problem/1934

주어진 두 수의 '최소공배수'를 출력하시오

Reference

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

왜 뜬금없이 이게 나오는지는 보다보면 알게 된다.

풀이

자 일단 최소공배수가 뭐냐... 두 수 x, y가 있을 때 x의 배수이면서 y의 배수인 수 중 제일 작은 수가 최소공배수다. 이거 초등학생때 다 배운겁니다 여러분. 자매품으로는 최대공약수가 있는데 이건 x를 나눴을때도 나누어 떨어지고 y를 나누었을때도 나누어 떨어지는 제일 큰 수. 반대되는 개념은 왜 없냐면 최소공약수는 무조건 1이고 최대공배수는 수가 끝이 없어서 없다.

그리고 최대공약수/최소공배수 구할 때 어떻게 하냐...

저기서 왼쪽에 있는 2, 3만 곱하면 최대공약수(6)가 되고, 밑에 있는것(최종적으로 나온 몫)까지 다 곱하면 최소공배수다. 그래서 12와 18의 최대공약수는 6, 최소공배수는 36. 두 수가 서로소(공약수따원 없다네)일 경우 최대공약수가 1이기때문에 걍 깡으로 곱하면 그만이지만, 진짜 깡으로 곱해서 출력한다?

예~ 틀려요~

유클리드 호제법

그럼 여기서 저 유클리드 머시기가 왜 나왔는지를 알려주도록 하겠다. 유클리드 호제법은 자연수나 다항식의 최대공약수를 구하는 방법으로... 다항식에 그걸 써도 되는지는 모르겠으나 아무튼. 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 방식이라고 할 수 있다. 그래서 호제법이지 뭐 호형호제 이딴거 아님.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 아, 글로 보면 모르겠죠?

미안... 이걸 손으로 쓰기엔... 이거 리눅스 놋북인걸... 프레스코따원 안된다규... 아무튼 이런 느낌이다. 그럼 예시를 몇 개 할짝여보고 가도록 하자. 참고로 나무위키에는 서로소의 예시가, 위키피디아에는 최대공약수가 존재하는 예시가 있다.

위키피디아에 있는 예시는 18696과 19332의 최대공약수를 찾는 것이다. 예시에 나온 두 수의 최대공약수는 36이다. 왜? 72를 36으로 나눠서 나머지가 0이 됐으니까. 그럼 두 수가 서로소면 어떻게 해요? 서로소인 13과 6의 예시를 들어보자면 13 = 6 * 2 + 1 -> 6 = 1 * 6 + 0 이기 때문에 둘은 서로소이고, 최대공약수가 1이 된다.

그럼 다시 풀이로 돌아가보자.

다시 풀이로

그러니까 유클리드 호제법으로 두 수의 최대공약수를 구한다는것까지는 알겠는데, 이걸로 뭘 할거냐고? 위 그림을 다시 보자. 18과 12의 최대공약수는 얼마? 6이다. 유클리드 호제법으로 18 12 하면 18 = 12 * 1 + 6, 12 = 6 * 2 + 0 해서 6 나온다. 그리고 어떻게 했어요? 18을 6으로 나눠서 나온 몫 3과 12를 6으로 나눠서 나온 몫 2를 곱했다 그죠?

import sys

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

T = int(sys.stdin.readline())
for i in range(T):
    A, B = map(int, sys.stdin.readline().split())

위에 있는 함수는 위키피디아에 파이썬 예시로 있었던 코드다. 재귀형도 있긴 한데 그거는 공약수 있으면 뺑뺑이 도느라 시간초과 날 수 있으니 걍 함수형을 쓰자. 아무튼, 이 코드는 유클리드 호제법을 이용해 세 가지 단계를 거칠거다. 첫번째, 유클리드 호제법으로 최대공약수를 구한다. 두번째, 그 최대공약수로 A와 B를 각각 나눈다. 세번째, 몫 두 개랑 최대공약수를 곱한다.

import sys

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

T = int(sys.stdin.readline())
for i in range(T):
    A, B = map(int, sys.stdin.readline().split())
    C = Euclidean(A,B) # 유클리드 호제법으로 최대공약수를 도출
    LCM = C * (A // C) * (B // C) # LCM이 최소공배수였다니 
    print(LCM)

그래서 A, B 입력받는 밑에 두 줄이 그거다. C는 유클리드 호제법으로 구한 최대공약수, 그리고 LCM은 최소공배수. 변수 할당하고 줄 늘리기 귀찮아서 걍 한큐에 곱해버였는데 //가 안 들어가면 뭐 된다? 소수점 됩니다. 그니까 // 쓰십셔. 아니면 int 드가야되는데 귀찮기도 하고, 어차피 우리는 몫만 필요하니께(나머지가 없기도 함). 그래서 A // C는 A를 C로 나눈 몫, B // C는 B를 C로 나눈 몫이다. 그리고 C와 몫 두 개를 곱하면 LCM, 최소공배수가 된다.

밑에 있는 print문은 말 그대로 최소공배수 출력하라는 얘기. 변수 할당할 필요 없이 print문에 저 식 때려박아도 되긴 되는데 그렇게 하면 틀렸을때 수정하다가 머리터짐.... 한큐에 맞춰서 망정이지.