카테고리: boj

• push X: deque.append(X)로 큐의 뒤에 원소를 추가
• pop: deque.popleft()로 큐의 앞에서 원소를 제거하고 반환
• size: len(deque)로 큐의 크기 반환
• empty: 큐가 비어있는지 확인
• front: deque[0]로 큐의 첫 번째 원소 접근
• back: deque[-1]로 큐의 마지막 원소 접근

모든 연산에서 큐가 비어있을 때의 예외 처리를 해주어야 한다.

from collections import deque
import sys

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

q = deque()

for i in range(N):
  cmd = sys.stdin.readline().strip().split()
  if cmd[0] == 'push':
    q.append(cmd[1])

  elif cmd[0] == 'pop':
    if len(q) != 0:
      print(q.popleft())
    else:
      print(-1)

  elif cmd[0] == 'size':
    print(len(q))

  elif cmd[0] == 'empty':
    if len(q) == 0:
      print(1)
    else:
      print(0)

  elif cmd[0] == 'front':
    if len(q) != 0:
      print(q[0])
    else:
      print(-1)
      
  elif cmd[0] == 'back':
    if len(q) != 0:
      print(q[-1])
    else:
      print(-1)

• len_limit = min(N - 1, M - 1): 가능한 최대 정사각형의 한 변 길이 (인덱스 차이)
• for k in range(len_limit, -1, -1): 큰 정사각형부터 확인
• for x in range(M - k): 정사각형의 시작 x 좌표 (x + k가 범위를 벗어나지 않도록)
• for y in range(N - k): 정사각형의 시작 y 좌표 (y + k가 범위를 벗어나지 않도록)
• 네 꼭짓점 비교: rectangle[y][x] (좌상), rectangle[y + k][x] (좌하), rectangle[y][x + k] (우상), rectangle[y + k][x + k] (우하)
• break-else 패턴: 조건을 만족하는 정사각형을 찾으면 모든 반복문을 빠져나감

최악의 경우 모든 가능한 정사각형을 확인해야 하므로 시간 복잡도는 O(N × M × min(N, M))이다.

N, M ≤ 50이므로 최악의 경우에도 50 × 50 × 50 = 125,000번의 연산으로 충분히 시간 내에 해결할 수 있다.

max_h = 0
pillar_list = [0] * 1001

max_loc = 0
for _ in range(N):
    loc, h = map(int, input().split())
    max_h = max(max_h, h)
    max_loc = max(max_loc, loc)
    pillar_list[loc] = h

# 왼쪽에서 시작
i_l = -1
cur = 0
ans = 0
while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

# 오른쪽에서 시작
i_r = max_loc + 1
cur = 0
while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

print(ans)

import heapq
T = int(input())

for _ in range(T):
    K = int(input())

    res = 0
    files = list(map(int, input().split()))
    
    dp = [[0] * K for _ in range(K)]
    sum_list = [0] * (K + 1)

    # 누적합
    for i in range(K):
        sum_list[i + 1] = sum_list[i] + files[i]
    
    for i in range(1, K):
        for j in range(i, K):
            dp[j - i][j] = float('inf')
            for k in range(j - i, j):
                dp[j - i][j] = min(dp[j - i][j], dp[j - i][k] + dp[k + 1][j])
            dp[j - i][j] += sum_list[j + 1] - sum_list[j - i]
    
    print(dp[0][K - 1])

def fill_nemo(d=0):
    global cnt
    if N*M == d:
        cnt += 1
        return
    
    y = d // M + 1
    x = d  % M + 1

    # 사각형이 완성 안되는 경우(넴모를 놓을 수 있는 경우)
    if matrix[y-1][x] == 0 or matrix[y-1][x-1] == 0 or matrix[y][x-1] == 0:
        # 다음 위치에 네모 생성
        matrix[y][x] = 1
        fill_nemo(d+1)
        matrix[y][x] = 0

    # 다음 위치에 네모 생성 X
    fill_nemo(d+1)
    

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

matrix = [[0]*(M+1) for _ in range(N+1)]

cnt = 0
fill_nemo()

print(cnt)

word = input().upper()

counter = defaultdict(int)

max_cnt = 0
max_alpha = ''
same_chk = False

for a in word:
    counter[a] += 1
    if counter[a] > max_cnt:
        max_cnt = counter[a]
        max_alpha = a
        same_chk = False
    elif counter[a] == max_cnt:
        same_chk = True

if same_chk:
    print('?')
else:
    print(max_alpha)

탐색 완료: 1, 2, 3

이렇게 목표 건물이 4번이 queue에 들어와 탐색을 마치면 4번 건물을 지었다는 것이므로 탐색을 멈추고 저장해두었던 시간을 출력하면 된다.

이 문제의 입력으로 주어지는 건물들로 만들어진 그래프는 항상 방향성을 가지며, 항상 모든 건물이 건축 가능하도록 주어진다고 했기 때문에 acyclic이다. 즉 이 문제의 그래프는 DAG(Directed Acyclic Graph)이다. DAG에서 어떤 노드로 들어오는 간선의 개수를 indegree라고 하는데 이 indegree의 개수에 따라 정렬하는 것을 위상 정렬(topologicla sort)이라고 한다.

따라서 우리가 위에서 필요 건물(indegree)에 따라 정렬하여 시간을 계산한 것은 위상 정렬을 이용한 알고리즘인 것이다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

rope = []
for i in range(0, n):
    rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0
for cnt, r in enumerate(rope):
    if max_w <= r * (cnt + 1):
        max_w = r * (cnt + 1)

print(max_w)

반복문을 돌면서 (로프의 개수) * (지금 확인한 로프의 무게)의 값이 저장해 놨던 무게 max_w 보다 크면 max_w를 바꿔준다.