졍's 기술 블로그

수 찾기

티어 : Silver 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 이분 탐색, 트리를 사용한 집합과 맵

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 \(-2^31\) 보다 크거나 같고 \(2^31\)보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입출력

Algorithm

1. bisect 사용
2. A List sort
3. bisect_left와 bisect_right의 값을 비교해 같으면 0, 다르면 1 출력

Code

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

# 입력
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

# A 정렬
A.sort()
for i in B:
    left = bisect_left(A, i)
    right = bisect_right(A, i)
    
    # left와 right의 값이 다르면 존재한다는 의미 -> 1 출력
    if left != right:
        print(1)
    else: # 값이 같으면 존재하지 않는다는 의미 -> 0 출력
        print(0)

메모리: 48360 KB
시간: 308 ms

스택

티어 : Silver 4
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 256 MB
알고리즘 분류 : 자료 구조, 스택

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입출력

Algorithm

1. push: list.append()
2. pop: list.pop()
3. size: print(len(list))
4. empty: if list: -> true, else: -> print(-1)
5. top: if list: -> print(list[-1]), else: -> print(-1)

[readline을 사용해 입력받으면 입력받은 명령어 뒤에 개행문자가 붙으므로 명령어를 비교할 때 order[:-1]와 비교해야함!]

Code

import sys
input = sys.stdin.readline

# 입력
N = int(input())
stack = []
for _ in range(N):
    order = input()
    
    if order[:4] == 'push':
        _, num = order.split()
        stack.append(int(num))
        
    elif order[:-1] == 'pop':
        if stack:
            print(stack[-1])
            stack.pop()
        else:
            print(-1)
        
    elif order[:-1] == 'size':
        print(len(stack))
    
    elif order[:-1] == 'empty':
        if stack:
            print(0)
        else:
            print(1)
            
    else:
        if stack:
            print(stack[-1])
        else:
            print(-1)

메모리: 30864 KB
시간: 80 ms

다리 놓기

티어 : Silver 5
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예제 입출력

Algorithm

1. nCk 조합 계산 :  n! // (k! * (n-k)!)   
    ☞ M 개 중에 N개를 골라서 다리를 놔야하기 때문

Code

def factorial(num):
    if num < 2:
        return 1
    else:
        return num * factorial(num-1)

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    print(factorial(M) // (factorial(N) * factorial(M - N)))

메모리: 30860 KB
시간: 112 ms

약수

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

예제 입출력

Code

import sys
input = sys.stdin.readline

N = int(input())
aliquot = list(map(int, input().split()))

print(min(aliquot) * max(aliquot))

메모리: 30864 KB
시간: 68 ms

이항 계수 2

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

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

입력

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

출력

\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

예제 입출력

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔
4. 3번의 결과를 10007로 나눈 나머지 출력

Code

import sys
sys.setrecursionlimit(10 ** 6)

# 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!) % 10007
print((num1 // num2) % 10007)

메모리: 31324 KB
시간: 72 ms

이항 계수 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