from collections import deque
n, m = map(int, input().split()) # 세로, 가로
board = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
answer = [] # 넓이를 저장할 리스트
# 그림의 개수, 가장 큰 넓이 출력
# 그림 = 1로 연결된 것,
def bfs(x, y): # 탐색 위치, 넓이
# 그림이 시작 하는 위치에서 큐 시작
board[x][y] = 0 # 현재 위치 방문 체크
queue = deque() # 큐 생성
queue.append([x, y]) # 큐에 해당 칸 넣기
cnt = 1 # 그림 칸 개수
while queue: # 큐가 빌때까지
a, b = queue.popleft() # 현재 탐색 위치 제거(탐색 완료)
for d in range(4): # 상하좌우 확인
nx = a + dx[d]
ny = b + dy[d]
# 2차원 배열에서 벗어나지 않고, 다음 위치가 1(그림이 있는)인 경우
if -1 < nx < n and -1 < ny < m and board[nx][ny] == 1:
board[nx][ny] = 0 # 다음 위치 방문 체크
queue.append([nx, ny]) # 큐에 탐색할 위치 넣기
cnt += 1 # 그림 칸 개수
return cnt
# 그림의 시작점 찾기
for i in range(n):
for j in range(m):
if board[i][j] == 1: # 그림이 있는 위치
answer.append(bfs(i, j))
if len(answer) == 0: # 그림이 하나도 없는 경우
print(len(answer))
print(0)
else:
print(len(answer))
print(max(answer))
from collections import deque
n = int(input())
board = [list(map(int, input())) for _ in range(n)]
answer = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 1 집이 있는곳, 0 집이 없는 곳
# 단지 개수, 단지에 속하는 집 개수 출력
def bfs(x, y):
queue = deque()
queue.append([x, y])
board[x][y] = 0 # 방문체크
cnt = 1
while queue:
px, py = queue.popleft()
for d in range(4):
nx = px + dx[d]
ny = py + dy[d]
# 방문 가능한 곳인지 확인
if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
board[nx][ny] = 0 # 다음 방문 체크
queue.append([nx, ny]) # 큐 입력
cnt += 1
return cnt # 집 개수 출력
for i in range(n):
for j in range(n):
if board[i][j] == 1:
answer.append(bfs(i, j))
answer.sort()
print(len(answer))
for x in answer:
print(x)
from collections import deque
n, m = map(int, input().split()) # 가로, 세로
board = [list(map(int, input())) for _ in range(n)]
# 1: 이동할 수 있는 칸, 0: 이동 불가능
# (1,1)에서 출발 (N,M) 위치로 이동할 때 지나야 하는 최소 칸 수 출력
def bfs(x, y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque() # 큐 생성
queue.append([x, y]) # 시작점 체크
while queue:
a, b = queue.popleft()
for d in range(4):
nx = a + dx[d]
ny = b + dy[d]
# 방문 가능한 곳
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
queue.append([nx, ny]) # 큐 삽입
board[nx][ny] = board[a][b] + 1
return board[n - 1][m - 1]
print(bfs(0,0))
from collections import deque
m, n = map(int, input().split()) # 가로, 세로
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
day = 0
# 토마토는 하루가 지날 때 마다 안익은 토마토는 인접한 익은 토마토의 영향을 받아 익게 된다.
# 모든 토마토가 익게 되는 일수 출력, 모두 익지 못하는 상황에는 -1 출력
# 익은 토마토 1, 안익은 토마토 0, 토마토가 없는 경우 -1
# 시작 위치 큐에 넣기
for i in range(n):
for j in range(m):
if board[i][j] == 1:
queue.append([i, j])
def bfs():
while queue:
px, py = queue.popleft()
for d in range(4):
nx = px + dx[d]
ny = py + dy[d]
# 토마토가 익지 않았을 경우
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
board[nx][ny] = board[px][py] + 1
queue.append([nx, ny])
bfs()
# 익지 않은 토마토가 있으면 -1 출력, 모두 다 익은 경우 가장 큰 날짜를 찾아서 출력
for i in range(n):
for j in range(m):
if board[i][j] == 0:
print(-1)
exit(0)
maxValue = max(board[i])
day = max(maxValue, day)
# 처음 시작을 1로 했기 때문에 -1
print(day-1)
from collections import deque
#n, k = 5, 17 # 수빈이가 있는 위치, 동생이 있는 위치
n, k = map(int, input().split())
MAX = 10 ** 5
visited = [0]*(MAX+1)
# 걷기 : 1초 후 x-1, x+1로이동
# 순간이동 : 1초 후 2*x 으로 이동
# 가장 빠른 시간 찾기
def bfs():
queue = deque()
queue.append(n)
while queue:
x = queue.popleft()
if x == k:
print(visited[x])
break
for nx in (x-1, x+1, x*2):
if 0 <= nx <= MAX and not visited[nx]:
visited[nx] = visited[x] + 1
queue.append(nx)
bfs()
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘
어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용한다.
ex. 피보나치 수열에서 중복된 연산을 미리 배열을 만들어두고 값을 저장해두면(메모이제이션) 시간 복잡도 O(N)으로 개선 가능
상향식 접근법 : for으로 구현, 작은 문제를 모아 큰 문제 해결, 메모제이션 사용X
하향식 접근법 : 재귀함수 구현, 큰 문제를 해결하기 위해 작은 재귀 함수 호출, 메모제이션 사용
보통 동적 계획법은 상향식 접근법을 사용
DP를 푸는 과정
테이블 정의하기
점화식 찾기
초기값 정하기
DP 문제 - 1463번 1로 만들기
정수 N이 주어질 때, 세 개의 연산을 적절히 사용해서 1을 만드려고 한다. 연산 사용 횟수의 최소값 구하기
1. 테이블 정의하기
D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
2. 점화식 찾기
D[12] = ?
3으로 나누거나 D[12] = D[4] + 1
2으로 나누거나 D[12] = D[6] + 1
1을 빼거나 D[12] = D[11] + 1
D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)
3. 초기값 정의하기
D[1] = 0
n = int(input()) # 정수 N
dp = [0]*(n+1) # dp에 계산된 값을 저장해두고
dp[1] = 0
for i in range(2, n+1):
dp[i] = dp[i-1] + 1
if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1)
if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1)
print(dp[n])
n = int(input()) # 계단의 개수
S = [0]*(n+1)
for i in range(1, n+1):
S[i] = int(input())
if n == 1:
print(S[1])
elif n == 2:
print(S[1]+S[2])
else:
dp = [[0 for col in range(3)] for row in range(n+1)]
dp[1][1], dp[1][2] = S[1], 0
dp[2][1], dp[2][2] = S[2], S[1]+S[2]
# 계단 오르기 규칙
# 1. 한 계단 또는 두 계단 오르기 가능
# 2. 연속 세개 계단 불가능(시작점은 포함X)
# 3. 마지막 계단 무조건 밟기
for i in range(3,n+1):
dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + S[i]
dp[i][2] = dp[i-1][1] + S[i]
print(max(dp[n][1], dp[n][2]))
DP 문제 - 1149번 RGB거리
집의 색상은 빨강, 초록, 파랑 중 하나의 색상
집을 빨강, 초록, 파랑으로 칠하는 비용이 주어질 때, 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값 구하기
1. 테이블 정의하기
D[i][0] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 빨강
D[i][1] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 초록
D[i][2] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 파랑
2. 점화식 찾기
D[k][0] = min(D[k-1][1], D[k-1][2]) + R[k] // 빨강으로 칠할 때 k-1 집은 초록 or 파랑 + R[k] 빨강 비용
n = int(input()) # 집 개수
R = [0] * (n + 1)
G = [0] * (n + 1)
B = [0] * (n + 1)
dp = [[0 for col in range(3)] for row in range(n + 1)]
for i in range(1, n + 1):
color = list(input().split())
R[i] = int(color[0])
G[i] = int(color[1])
B[i] = int(color[2])
if n == 1:
print(min(R[1], G[1], B[1]))
else:
# 초기값 설정
dp[1][0] = R[1]
dp[1][1] = G[1]
dp[1][2] = B[1]
# 집 색칠 규칙
# 1. 1번의 집 색상은 2번의 집 색상과 같지 않아야 한다.
# 2. N번 집의 색상은 N-1번의 집 색상과 같지 않아야 한다.
# 3. 2(<= i <= N-1)번의 집 색상은 i-1번, i+1번 집의 색상과 같지 않아야 한다.
for k in range(2, n + 1):
dp[k][0] = min(dp[k - 1][1], dp[k - 1][2]) + R[k] # 이전색상 초록 or 파랑 + 현재 빨강
dp[k][1] = min(dp[k - 1][0], dp[k - 1][2]) + G[k] # 이전색상 파랑 or 빨강 + 현재 초록
dp[k][2] = min(dp[k - 1][0], dp[k - 1][1]) + B[k] # 이전색상 빨강 or 파랑 + 현재 파랑
print(min(dp[n][0], dp[n][1], dp[n][2]))
DP 문제 - 11726번 2xn 타일링
2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하기
1. 테이블 정의하기
D[i] = 2xi 크기의 직사각형을 채우는 방법의 수
2. 점화식 찾기
D[i] = D[n-1] + D[n-2]
2 x 1 타일로 1개씩 채우면 남는 방법의 수 n-1
1 X 2 타일로 2개 채우면 남는 방법의 수 n-2
3. 초기값 정하기
D[1] = 1
D[2] = 2
n = int(input())
dp = [0]*1001
dp[1] = 1
dp[2] = 2
for i in range(3, 1001):
dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[n])
DP 문제 - 11659번 구간 합 구하기 4
dp[i] = arr[1] + arr[2] + arr[3] + .. + arr[i]
dp[i] = dp[i-1] + arr[i]
import sys
n, m = map(int, sys.stdin.readline().split()) # 수의 개수, 합을 구해야하는 횟수
arr = list(map(int, sys.stdin.readline().split()))
dp = [0]*(n+1)
# D[i] = A[1] + A[2] + .. + A[i]
# D[i] = D[i-1] + A[i]
for i in range(1, n+1):
dp[i] = dp[i-1] + arr[i-1]
for _ in range(m):
i, j = map(int, sys.stdin.readline().split())
print(dp[j]-dp[i-1])
#n = 8 # 정수의 개수, 최대 정수값
#arr = [4,3,6,8,7,5,2,1]
n = int(input())
stack = []
maxIdx = 1
answer = []
flag = False
# push 오름차순
for i in range(n):
x = int(input())
while maxIdx <= x:
stack.append(maxIdx)
answer.append('+')
maxIdx += 1
if stack[-1] == x:
stack.pop()
answer.append('-')
else: #stack[-1] != x:
flag = True
break
if flag:
print('NO')
else:
for x in answer:
print(x)
from collections import deque
# n, k = 7, 3 # 사람 수, 제거하는 사람 위치
n, k = map(int,input().split())
queue = deque() # 덱으로 큐 생성
answer = '<'
# 요소 삽입
for x in range(1, n+1):
queue.append(x)
while queue:
for x in range(k-1):
element = queue.popleft() # 맨 왼쪽에 있는 값 꺼내서
queue.append(element) # 맨 뒤로 삽입
answer += str(queue.popleft()) + ', '
print(answer[:-2]+'>')
from collections import deque
tc = int(input()) # 테스트 케이스 수
for _ in range(tc):
n, m = map(int, input().split()) # 문서 개수, 찾을 위치
arr = list(map(int, input().split())) # 문서 중요도 배열
pq = deque() # 덱으로 큐 생성
# (인덱스, 중요도) 값으로 덱 요소 삽입
for x in range(len(arr)):
pq.append((x, arr[x]))
importList = sorted(arr, reverse=True) # 중요도 순서
importIdx = 0
cnt = 0
while pq:
element = pq.popleft()
if importList[importIdx] == element[1]: # 중요도 순서가 맞는 경우
importIdx += 1
cnt += 1
if element[0] == m: # 찾는 인덱스와 일치할 경우
print(cnt)
break
else:
pq.append(element) # 맨 왼쪽 오른쪽에 삽입
import heapq
import sys
n = int(input()) # 연산의 개수 18
# arr = [1, -1, 0, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0, 0, 0, 0, 0, 0] # 연산에 대한 정보
# 0 x : 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
# 1 x : 값을 넣는 연산
heap = []
for i in range(n):
x = int(sys.stdin.readline())
if x != 0: # 값 넣기
heapq.heappush(heap, (abs(x), x))
else:
# 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
# 같은 값이 여러개면 가장 작은 수 출력
# 배열이 비어있으면 0 출력
if len(heap) == 0:
print(0)
else:
element = heapq.heappop(heap) # heappop : 가장 작은 값 제거 + return
print(element[1])
import heapq
n = int(input()) # 숫자 카드 묶음 개수
heap = []
answer = 0
for _ in range(n):
x = int(input())
heapq.heappush(heap, x)
while len(heap)!=1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
answer += a + b
heapq.heappush(heap, a+b)
print(answer)
from collections import defaultdict
#n = 4 # 출입 기록 수
# arr = ['Baha enter', 'Askar enter', 'Baha leave', 'Artem enter']
# enter 출근, leave 퇴근
# 대소문자 구분
# 현재 회사에 있는 모든 사람을 구하는 프로그램 작성
n = int(input())
dict = defaultdict(str)
for x in range(n):
name, opt = input().split()
if dict[name] == 'enter' and opt == 'leave':
del dict[name]
else:
dict[name] = opt
for x in sorted(dict.keys(),reverse=True):
print(x)
from collections import defaultdict
n, m = map(int, input().split())
answer = 0
S = defaultdict(int)
for x in range(n):
key = input()
S[key] = 1
for x in range(m):
key = input()
if S[key]:
answer += 1
print(answer)
n, m = 5, 3 # 정수 개수, 두 개의 정수 차이 최소 기준
arr = [1, 2, 3, 4, 5]
#n, m = map(int, input().split())
#arr = [int(input()) for _ in range(n)]
arr.sort()
lt = 0
rt = 0
minValue = float('inf')
# print(arr)
while rt != n and lt <= rt:
value = arr[rt] - arr[lt]
if value >= m: # m 이상일 때
minValue = min(minValue, value)
lt += 1
else: # m 이상이 아닐 때
rt += 1
print(minValue)
import sys
# n, m = 4, 3 # 표의 크기, 연산 횟수
n, m = map(int, input().split())
arr = [[0]*(n+1)] + list([0]+list(map(int, input().split())) for _ in range(n))
sumArr = [[0]*(n+1) for _ in range(n+1)]
# 누적합 배열 만들기
for i in range(1, n+1):
for j in range(1, n+1):
sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] - sumArr[i-1][j-1] + arr[i][j]
# 계산 하기 - (x1, y1) 부터 (x2, y2) 합 구하기
# 전체 - 영역1 - 영역2 + (영역1과 영역2에서 두번 빼줬기 때문에 더해줘야 하는 영역)
for _ in range(m):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
res = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1]
print(res)
# n, k = 10, 4200 # 동전 종류, 구하려는 값 - 동전의 최소 개수 구하기
# arr = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
n, k = map(int, input().split())
arr = []
for _ in range(n):
arr.append(int(input()))
arr = sorted(arr, reverse=True)
cnt = res = 0
for x in arr:
if k >= x:
cnt = k // x
res += cnt
k = k - (x * cnt)
if k <= 0:
break
print(res)
n = int(input()) # 회의 수 - 회의가 겹치지 않게 진행할 수 있는 회의 최대 개수 구하기
arr = [[0] * 2 for _ in range(n)]
for i in range(n):
a, b = map(int, input().split())
arr[i][0] = a # 회의 시작 시간
arr[i][1] = b # 회의 끝나는 시간
#n = 11
#arr = [[1, 1], [1, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
#n = 3
#arr = [[1,1],[1,1],[0,1]]
arr.sort(key=lambda x: (x[1], x[0])) # 두번째 값이 같은 경우, 첫번째 값으로 오름차순
time = cnt = start = end = 0
for element in arr:
start = element[0]
end = element[1]
if time <= start:
time = end
cnt += 1
print(cnt)
# 최소 강의실 개수 구하기
import heapq
import sys
input = sys.stdin.readline
N = int(input()) # 수업의 개수
class_list = []
for _ in range(N):
x, y = map(int, input().split())
class_list.append([x, y])
class_list.sort()
heap = []
heapq.heappush(heap, class_list[0][1]) # 첫 번째 강의 끝나는 시간
# heap 최소 힙 유지 = 0 번째 인덱스는 가장 작은 값
for idx in range(1, N):
start, end = class_list[idx]
if start < heap[0]: # 빠른 시작 시간 < 앞에서 가장 빨리 끝나는 값
heapq.heappush(heap, end) # 새 강의실 추가
else: # 강의실 유지, 강의 시간 갱신
heapq.heappop(heap)
heapq.heappush(heap, end)
print(len(heap))
# n = 2 # 로프의 개수
# arr = [10, 15] # 로프가 버틸 수 있는 최대 중량
n = int(input())
arr = []
for _ in range(n):
arr.append(int(input()))
arr = sorted(arr, reverse=True)
maxRes = 0
# 내림차순으로 들을 수 있는 로프 개수 * 현재 무게를 계산해서 최대값을 구해준다.
for k in range(n):
maxRes = max(arr[k]*(k+1), maxRes)
print(maxRes)
# n = 5 # 정수의 개수
# arrA = [1, 1, 1, 6, 0] # A 정수 배열
# arrB = [2, 7, 8, 3, 1] # B 정수 배열
n = int(input())
arrA = list(map(int, input().split()))
arrB = list(map(int, input().split()))
# S = A[0] * B[0] + A[1] * B[1] + ...+ A[N-1] * B[N-1]
# 계산 값을 가장 작게 만들기 위해서는 각 배열을 오름차순, 내림차순 해준다.
arrA.sort()
arrB.sort(reverse=True)
res = 0
for x in range(n):
res += arrA[x]*arrB[x]
print(res)
# 트럭 한 대로 배송할 수 있는 최대 박스 수 출력
N, C = map(int, input().split()) # 마을의 수, 트럭 용량
M = int(input()) # 박스 정보 개수
info = []
res = 0
for _ in range(M):
# 박스를 보내는 마을, 박스를 받는 마을, 보내는 박스의 개수
from_box, to_box, num_box = map(int, input().split())
info.append((from_box, to_box, num_box))
sort_info = sorted(info, key=lambda x: x[1]) # 가장 빨리 받는 순서대로 정렬
remain = [0] * (N+1) # 남은 상자
for item in sort_info:
start, end, box = item[0], item[1], item[2]
max_box = box
for i in range(start, end): # 시작점부터 도착지까지 보낼 수 있는 박스 개수
max_box = min(max_box, C - remain[i])
# print(max_box, C-remain[i])
for j in range(start, end):
remain[j] += max_box
res += max_box
print(res)
# k, n = 4, 11 # 이미 가지고 있는 랜선 개수, 필요한 랜선 개수 n
# kArr = [802, 743, 457, 539] # 랜선은 길이가 모두 다르다.
k, n = map(int, input().split())
kArr = []
for i in range(k):
kArr.append(int(input()))
kArr = sorted(kArr) # 이분 탐색을 위한 정렬
lt = 0
rt = kArr[-1]
maxLen = 0
while lt <= rt:
mid = (lt+rt)//2
total = 0
for size in kArr: # 구할 수 있는 랜선 개수 구하기
total += (size//mid)
if total >= n: # 랜선의 개수가 더 많을 경우
maxLen = max(maxLen, mid) # 최대값 갱신
lt = mid +1
else:
rt = mid -1 # 랜선의 개수가 부족할 경우
print(maxLen)
import sys
n, c = map(int, sys.stdin.readline().split()) # 집의 개수, 공유기 개수
x_arr = []
for _ in range(n):
x = int(sys.stdin.readline()) # 집의 좌표
x_arr.append(x)
x_arr.sort()
res = 0
start = 1 # 최소 거리 1
end = x_arr[-1] - x_arr[0] # 최대 거리 = 가장 먼거리
while start <= end:
mid = (start + end) // 2 # 중간값 = 현재 가능한 공유기 사이의 거리
temp = x_arr[0] # 이전 집의 좌표
cnt = 1
for i in range(1, n):
if x_arr[i] - temp >= mid: # 가능한 거리(mid) 이상으로 공유기를 설치할 수 있는 집에 공유기 설치
cnt += 1
temp = x_arr[i]
if cnt >= c: # c개 이상의 공유기를 설치할 수 있는지 확인
start = mid + 1 # 가능하면 mid 증가
res = mid
else:
end = mid - 1 # 불가능하면 mid 감소
print(res)
