20210618 알고리즘 문제 풀이

백준 10828번 스택

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

풀이

import sys
def push(x):
    stack.append(x)
def pop():
    if(not stack):
        return -1
    else:
        return stack.pop()
def size():
    return len(stack)
def empty():
    return 0 if stack else 1
def top():
    return stack[-1] if stack else -1
N = int(sys.stdin.readline())
stack = []
for _ in range(N):
    input_split = sys.stdin.readline().split()
    order = input_split[0]
    if order == "push":
        push(input_split[1])
    elif order == "pop":
        print(pop())
    elif order == "size":
        print(size())
    elif order == "empty":
        print(empty())
    elif order == "top":
        print(top())

• 정수 X를 스택에 넣는 연산(push)
• 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.(pop)
• 스택에 들어있는 정수의 개수를 출력(size)
• 스택이 비어있으면 1, 아니면 0을 출력한다(empty)
• 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.(top)
• stack이라는 빈 리스트를 생성하고 반복문과 위에서 만든 함수들을 사용하면 문제에서 원하는 프로그램이 만들어진다.

백준 10773번 제로

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

풀이

import sys
n = int(sys.stdin.readline()) 
z = []
for i in range(n):
    num = int(sys.stdin.readline())
    if num == 0: 
        z.pop()
    else: 
        z.append(num)
print(sum(z))

• 입력받을 스택 리스트 안의 총 숫자의 수를 n으로 입력받는다.
• z라는 빈 리스트를 생성한다.
• num이라는 값으로 n개의 정수를 입력받는다.
• num이 0이면 z에서 가장 위에 있는 정수를 빼고 그렇지 않으면 z에 입력받은 값을 추가해준다.
• 그리고 나서 z의 원소들을 모두 더해주면 '모든 수들의 합'을 알 수 있다.

백준 9012번 괄호

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

풀이

import sys
a = int(sys.stdin.readline())
for i in range(a):
    b = input()
    s = list(b)
    sum = 0
    for i in s:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            print('NO')
            break
    if sum > 0:
        print('NO')
    elif sum == 0:
        print('YES')

• 입력받을 데이터의 수를 변수 a로 선언해주고 입력받을 데이터들을 변수 b로 선언해준다. 그리고 변수 s에 b값들을 리스트로 만들어서 선언한다.
• 반복문을 실행하면서 입력받은 데이터가 ')'라면 sum이라는 변수에 1을 더해준다.
• 입력받은 데이터가 '('라면 sum이라는 변수에 1을 빼준다
• 만약 sum이 0보다 작아진다면 NO를 출력하고 함수를 종료한고 sum이 0인 경우에는 YES를 출력한다.

백준 1934번 최소공배수

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

풀이

import sys
import math
a = int(sys.stdin.readline())
for i in range(a):
    x, y = map(int, input().split())
    print(math.lcm(x, y))

• 내장함수 math의 lcm모듈을 이용해서 최소공배수를 구한다.

백준 11050번 이항계수

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

풀이1

from math import factorial
n, k = map(int, input().split())
b = factorial(n) // (factorial(k) * factorial(n - k))
print(b)

• n과 k가 주어졌을 때 nCk 즉, n! / k!(n-k)!를 해주면 된다.(math.factorial 사용)

풀이 2

N,K = map(int,input().split())
def fact(N):
    if N <= 1:
        return 1
    return N * fact(N-1)
print(fact(N) // (fact(K) * fact(N-K)))

• factorial 함수를 직접 만들어서 nCk 값을 구한다.

백준 1010번 다리놓기

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

풀이

def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)

• m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 개수는 n개이고
  m개의 지역에 n개의 다리를 놓을 수 있는 경우의 수를 구하는 것이기 때문에
  mCn으로 표현할 수 있고 이는 m!을 (m-n)!n!으로 나눈 값이 된다.