졍's 기술 블로그

이항 계수 1

티어 : Bronze 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 조합론

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)

출력

\(\binom{N}{K}\)를 출력한다.

예제 입출력

이항 계수(Binomial Coefficient)
조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 가짓수

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔

Code

# Factorial 계산하는 함수
def factorial(K):
    if K < 2:
        return 1
    else:
        return K * factorial(K-1)
    
# 입력
N, K = map(int, input().split())

# N * N-1 * ...
num1 = 1
for i in range(K):
    num1 *= N-i

# K!
num2 = factorial(K)

# N * N-1 * ... // K!
print(num1 // num2)

메모리: 30864 KB
시간: 72 ms

링

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

예제 입출력

Algorithm

1. 첫 번째 숫자로 각 숫자의 최대공약수 구하기
2. 첫 번째 숫자 // 최대공약수, 두 번째 숫자 // 최대공약수 출력

Code

import sys
input = sys.stdin.readline

# 최대 공약수 구하는 함수
def euclid(A, B):
    # 나머지
    R = A % B
    
    # 두 수가 나누어 떨어지면 B Return
    if R == 0:
        return B
    else: # 나누어 떨어지지 않으면 재귀
        return euclid(B, R)

# 입력
N = int(input())
nums = list(map(int, input().split()))

for  i in range(1, len(nums)):
    answer = ''
    num = euclid(max(nums[0], nums[i]), min(nums[0], nums[i]))
    answer += str(nums[0]//num) + '/' + str(nums[i] // num)
    print(answer)

메모리: 30860 KB
시간: 72 ms

최대공약수와 최소공배수

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입출력

Algorithm

1. 유클리드 호제법 이용
    1.1. 유클리드 호제법 함수 생성 - 재귀
    1.2. A와 B의 최대 공약수는 B와 A%B의 최대공약수와 같다.
2. 최소공배수 = A*B%최대공약수

Code

import sys
input = sys.stdin.readline

def euclid(A, B):
    R = A % B
    # A가 B의 배수이면 Return
    if R == 0:
        return B
    return euclid(B, R)

A, B = map(int, input().split())
answer = euclid(max(A, B), min(A, B))
print(answer)
print(A * B // answer)

메모리: 30864 KB
시간: 72 ms

A/B

티어 : Bronze 4
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

첫째 줄에 A/B를 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다.

예제 입출력

Code

A, B = map(int, input().split())
print(A/B)

메모리: 29200 KB
시간: 72 ms

배수와 약수

티어 : Bronze 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 사칙연산

문제

4 × 3 = 12이다.

이 식을 통해 다음과 같은 사실을 알 수 있다.

3은 12의 약수이고, 12는 3의 배수이다.

4도 12의 약수이고, 12는 4의 배수이다.

두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.

1. 첫 번째 숫자가 두 번째 숫자의 약수이다.
2. 첫 번째 숫자가 두 번째 숫자의 배수이다.
3. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 10,000이 넘지않는 두 자연수로 이루어져 있다. 마지막 줄에는 0이 2개 주어진다. 두 수가 같은 경우는 없다.

출력

각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다.

예제 입출력

Algorithm

1. A % B == 0 이면 factor 반환
2. B % A == 0 이면 multiple 반환
3. else의 경우 neither 반환

Code

import sys
input = sys.stdin.readline

while True:
    A, B = map(int, input().split())
    
    # 0 0을 입력받으면 break
    if A == 0:
        break
    
    if A % B == 0:
        print('multiple')
    elif B % A == 0:
        print('factor')
    else:
        print('neither')

메모리: 30860 KB
시간: 76 ms

A-B

티어 : Bronze 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

첫째 줄에 A-B를 출력한다.

예제 입출력

Code

A, B = map(int, input().split())
print(A-B)

메모리: 29200 KB
시간: 72 ms

A+B

티어 : Bronze 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

예제 입출력

Code

A, B = map(int, input().split())
print(A+B)

메모리: 29200 KB
시간: 72 ms

잃어버린 괄호

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 문자열, 그리디 알고리즘, 파싱

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입출력

Algorithm

1. 숫자는 숫자끼리, 연산자는 연산자끼리 각각 다른 List에 저장
    1.1. 숫자를 저장할 때 자릿수 생각해서 정수로 담기
2. A - B + C의 경우 - 연산자 뒤의 값 모두 계산하기
    2.1. - 연산자가 여러 개 있는 경우 A - B + C - D에서 A - (B+C) - D 로 계산

Code

# 입력
data = input()

operator_ = []
nums = []
temp = []
index = 0
for i in range(len(data)):
    if data[i] in ['+', '-']:
        operator_.append(data[i])
        # 숫자 자릿수에 맞춰서 하나의 숫자로 만들기
        nums.append(0)
        for j in range(len(temp)):
            nums[index] += temp[-1] * (10**j)
            del temp[-1]
        index += 1
    else:
        temp.append(int(data[i]))
# 마지막 숫자 추가
nums.append(0)
for j in range(len(temp)):
    nums[index] += temp[-1] * (10**j)
    del temp[-1]

# - 연산자 나오면 그 다음 - 연산자 전까지 + 모두 계산
i = 0
while True:

    # operator가 비어있으면 while문 돌지 않고 바로 출력
    if not operator_:
        break
    
    # - 연산자가 있으면 -연산자와 -연산자 사이의 값 모두 계산
    if operator_[i] == '-':
        
        index = 0
        flag = False # - 연산자 못찾으면 True
        
        if len(operator_) == 1 or i == len(operator_)-1:
            flag = True
            
        # 다음 - 연산자 찾기
        for j in range(i+2, len(operator_)+1):
            if operator_[j-1] == '-':
                index = j-1
                flag = False
                break
            else:
                flag = True
        
        # 그 뒤에 - 연산자가 없었다면
        if flag == True:
            nums[i+1] = sum(nums[i+1:])
            index = len(nums) - 1
        else: # - 연산자 있으면
            nums[i+1] = sum(nums[i+1:index+1])
        
        # 다음 - 연산자 전까지 모두 계산
        if '+' in  operator_[i+1:index]:
            temp = i + 2
            end = index + 1
            while True:
                nums[i + 2] = 0
                del operator_[i + 1]
                if nums[i + 2] == 0:
                    del nums[i + 2]
                    end -= 1
            
                if i + 2 == end:
                    break

    if i == len(operator_) - 1:
        break
    
    i += 1
    
for i in range(len(operator_)):
    if operator_[i] == '-':
        index = operator_.index('-')
        nums[index] -= nums[index+1]
        del nums[index+1]
print(sum(nums))

메모리: 30864 KB
시간: 76 ms