알고리즘 마라톤 4일차

21번

나무 자르기

전형적인 이진 검색 문제다. 시간 초과...😭

• 시간 초과 코드

  N, M = map(int, input().split())
  tree = list(map(int, input().split()))
  start, end = 1, max(tree)
  
  while start <= end:
      mid = (start + end) // 2
  
      total = 0
      for i in tree:
          if i >= mid:
              total += i - mid
  
      if total >= M:
          start = mid + 1
      else:
          end = mid - 1
  print(end)

별도의 함수로 분리한 것과 톱날의 높이가 크거나 같을 때 정답이 될 수 있기 때문에 ans 변수에 저장해둔 것 밖에 없는데 왜 되는거지? 대체 위의 코드와 무슨 차이지...❓

N, M = map(int, input().split())
tree = list(map(int, input().split()))

def sum_tree(height):
    sum = 0
    for i in tree:
        if i - height > 0:
            sum += (i - height)
    return sum

def binarySearch(target):
    start, end = 0, max(tree)
    ans = 0
    while start <= end:
        mid = (start + end) // 2
        sum = sum_tree(mid)
        if sum < target:
            end = mid - 1
        if sum >= target:
            ans = mid
            start = mid + 1

    return ans

print(binarySearch(M))

22번

스택

input() 함수보다 sys.stdin.readline()이 속도가 더 빠르다. 시간 단축이 가능해진다.

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

stack = []
for i in range(cmd_cnt):
    cmd = sys.stdin.readline().split()
    if cmd[0] == 'push':
        stack.append(int(cmd[1]))
    elif cmd[0] == 'pop':
        if not stack:
            print(-1)
        else:
            print(stack.pop())
    elif cmd[0] == 'size':
        print(len(stack))
    elif cmd[0] == 'empty':
        if not stack:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'top':
        if not stack:
            print(-1)
        else:
            print(stack[-1])

23번

제로

쉽다.

cnt = int(input())
stack = []
for i in range(cnt):
    num = int(input())
    if num == 0:
        stack.pop()
    else:
        stack.append(num)
print(sum(stack))

24번

괄호

역시 쉽다. 단, 열린 괄호보다 닫힌 괄호가 많아지는 시점에는 뒤에 어떤 경우가 와도 괄호가 완성되지 않으므로 바로 NO라고 판단해준다.

case_cnt = int(input())
for i in range(case_cnt):
    case = input()
    case_list = list(case)
    sum = 0
    for i in case_list:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            print('NO')
            break
    if sum > 0:
        print('NO')
    elif sum == 0:
        print('YES')

25번

최소공배수

알고리즘 마라톤 3일차 16번 문제를 복습했다면 무조건 맞추는 문제다.

유클리드 호제법을 알면 간단해진다.
두 수의 최대공약수는 두 수 중 작은 수와 두 수 중 큰 수에서 작은 수를 나눈 나머지의 최대공약수와 같다.
gcd(24, 18) = gcd(18, 6) = gcd(6, 0) 에서 작은 수가 0이 되는 순간의 큰 수가 바로 최대공약수다.
최대공약수를 구하면 최소공배수는 두 수를 곱한 값을 최대공약수로 나누어주면 끝이다.

def gcd(x, y):
    mod = x % y
    while mod > 0:
        x = y
        y = mod
        mod = x % y
    return y

def lcm(x, y):
    return x * y // gcd(x, y)

cnt = int(input())
for i in range(cnt):
    a, b = map(int, input().split())
    print(lcm(a, b))

26번

이항 계수 1

순열과 조합에 대한 개념을 이해해야 한다. 순열은 순서가 상관 있는 나열(Permutation), 조합은 순서 상관 없는 조합(Combination)
따라서 순열은 n!/n-r!, 조합은 n!/r!(n-r)!

from math import factorial

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