say repository

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

import sys
from collections import deque

dx = [1,2,2,1,-1,-2,-2,-1]
dy = [2,1,-1,-2,-2,-1,1,2]
def bfs(sx, sy, ex, ey):
    q = deque()
    q. append((sx, sy))
    chess[sx][sy] = 1
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(chess[x][y]-1)
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and chess[nx][ny] == 0:
                chess[nx][ny] = chess[x][y] + 1
                q.append((nx,ny))

T = int(sys.stdin.readline())
for i in range(T):
    n = int(sys.stdin.readline()) #체스판 한 변
    sx, sy = map(int,sys.stdin.readline().split())
    ex, ey = map(int,sys.stdin.readline().split())
    #체스판 생성
    chess = [[0]*n for _ in range(n)]
    bfs(sx, sy, ex, ey)

풀이

bfs로 처음 좌표부터 시작해서 끝 좌표에 도착할때까지 1을 더해주며 이동 횟수를 체스판에 저장한다.

처음 좌표를 1로 바꾸고 시작하므로 최종 횟수에서 1을 빼준다.

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

#7569
import sys
from collections import deque
m, n, h = map(int,sys.stdin.readline().split())
tomato = [[list(map(int,sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]
# print(tomato)

dx = [-1, 0, 1, 0, 0, 0]
dy = [0, 1, 0, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
q = deque()
# 익은 토마토 좌표 큐에 넣기
for z in range(h):
    for i in range(n):
        for j in range(m):
            if tomato[z][i][j] == 1:
                q.append((z,i,j))
def bfs():
    while q:
        z, x, y = q.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h and tomato[nz][nx][ny] == 0:
                tomato[nz][nx][ny] = tomato[z][x][y] + 1
                q.append((nz,nx,ny))

result = 0 #처음부터 모두 익은 상태
bfs()
for z in range(h):
    for i in range(n):
        for j in range(m):
            if tomato[z][i][j] == 0: #모두 익지 못함
                print(-1)
                sys.exit(0) #종료
            result = max(result,tomato[z][i][j]) #모두 익는 날짜 or 0 중 가장 큰 것 답
print(result-1) #처음에 익은 토마토부터 시작해서 1일 빼줘야함.

풀이

토마토 문제랑 똑같은데 3차원 배열인 부분만 다르다.

3차원 배열 주의하자.

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

#7576
import sys
from collections import deque
m, n = map(int,sys.stdin.readline().split())
tomato = [[]*m for _ in range(n)]
for i in range(n):
    tomato[i] = list(map(int,sys.stdin.readline().split()))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque()
# 익은 토마토 좌표 큐에 넣기
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i,j))
def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[x][y] + 1
                q.append((nx,ny))

result = 0 #처음부터 모두 익은 상태
bfs()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0: #모두 익지 못함
            print(-1)
            sys.exit(0) #종료
        result = max(result,tomato[i][j]) #모두 익는 날짜 or 0 중 가장 큰 것 답
print(result-1) #처음에 익은 토마토부터 시작해서 1일 빼줘야함.

풀이

bfs로 풀이했다.

익은 토마토 (1) 의 좌표를 큐에 넣고 익은 토마토 상하좌우에 안익은 토마토(0)을 찾아서 bfs을 진행한다.

bfs 진행하면서 전의 값에 + 1 을 해준다.

bfs 완료하고 좌표에 안익은 토마토(0) 이 있으면 -1 출력하고 종료한다.

없으면 처음부터 모두 익었거나 (정답 0) 시간이 지나서 익은 것이다.

둘 중 더 큰 값이 답이다.

여기서 마지막에 result-1 을 해주는 이유는 익은 토마토에서 시작해서

처음의 값이 (bfs 함수 내에서 tomato[i][j]가 1)  1부터 시작한다. 

따라서 답을 구할 때 -1을 빼줘야한다.

출처 : 백준

#15711
import sys

# 에라토스테네스의 체
# n = 2*(10**12) +1 # 끈의 길이 메모리 초과 따라서 절반만 에라토스테네스의 체 수행
n = 2*(10**6) + 1
arr = [True for _ in range(n)]
primes = [] # 소수
for i in range(2,n):
    if arr[i]:
        primes.append(i)
        for j in range(2*i, n, i):
            arr[j] = False

# 소수인지 판별
def isPrime(x):
    if x > n: # x 가 n인 2*10**12 보다 크면
        for prime in primes:
            if prime >= x:
                break
            elif x % prime == 0:# 소수로 나뉘는지로 판별
                return False
        return True
    else: # x가 n보다 작으면 바로 소수에서 꺼내기
        return arr[x]

# 테스트케이스
t = int(sys.stdin.readline())
for _ in range(t):
    ab = sum(map(int,sys.stdin.readline().split()))

    # 골드바흐의 추측 : 4보다 큰 짝수는 두 홀수 소수의 합으로 가능하다.
    # 4 보다 작으면 NO
    if ab < 4 :
        print("NO")
    # 4보다 큰 짝수 YES
    elif ab % 2 == 0:
        print("YES")
    else: # 홀수는 2(짝수 소수) + 홀수 소수의 합으로 가능하다. -> 홀수-2 가 소수인지 확인
        if isPrime(ab-2):
            print("YES")
        else:
            print("NO")

풀이

간단하게 에라토스테네스의 체로만 풀면 시간초과 난다.

문제에서 알고 있어야 할 것이 에라토스테네스의 체와 골드바흐의 추측이다.

근데 이렇게 풀어도 python으로는 시간초과가 나서 pypy3로 제출했다.

빠르게 풀 수 있는 방법 아시는분?

1) 체의 범위가 2*10**12나 되기 때문에 그 절반만 에라토스테네스의 체를 우선적으로 만들어주고

소수판별을 원하는 수가 이 범위보다 크면 소수로 나뉘는지로 판별한다.

2) 골드바흐의 추측 :  4보다 큰 짝수는 두 홀수인 소수의 합으로 가능하다.

따라서 4보다 작으면 NO 크면 짝수면 YES

4보다 큰 홀수는 2와 다른 소수 홀수의 합으로 이루어진다. 

따라서 홀수-2가 소수인지만 판별하면 된다.

3) 소수인지 판별은 앞서 말했듯 에라토스테네스의 체 범위보다 크면 소수로 나눈다. 나누어지면 소수가 아니다.

그 범위보다 작으면 바로 에라토스테네스의 체로 구해놓은 소수배열에서 꺼내쓴다.

#11053
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
d = [0]*n

for i in range(n):
    for j in range(i):
        if a[j] < a[i] and d[j] > d[i]:
            d[i] = d[j]
    d[i] += 1
print(max(d))

풀이

A = {10, 20, 10, 30, 20, 50} 로 경우의 수를 나눠서 구해보면 된다.

반복문을 돌면서, 자기 자신보다 작은 수열 중 가장 길이가 긴 수열의 크기 +1

 if a[i]>a[j]  -> 자기 자신보다 작은 수열

and d[j] > d[i] -> 가장 길이가 긴 수열의 크기

#2156
import sys
n = int(sys.stdin.readline())
arr = [0]*10000 #포도주
for i in range(n):
    arr[i] = int(sys.stdin.readline())

#dp테이블
#dp[i] = 0부터 i번째 포도주까지 최대로 마신 양
dp = [0] * 10000
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2], dp[1])

for i in range(3,n):
    dp[i] = max(dp[i-2]+arr[i], arr[i-1]+arr[i]+dp[i-3], dp[i-1])
print(max(dp))

풀이

다이나믹 프로그래밍이다.

dp[i] 는 처음부터 i번째까지 최대한 마신 포도주의 양이다.

dp[0] 부터 계산하면 점화식이 나오고 계산한다.

그 중 가장 큰 값을 출력하면 된다.

출처 : 백준

import sys
import heapq
n = int(sys.stdin.readline())
left_heap = [] #최대힙
right_heap = [] #최소힙
for _ in range(n):
    num = int(sys.stdin.readline())
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap,-num)
    else:
        heapq.heappush(right_heap,num)

    if len(left_heap)>=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]:
        #중간값이 중간값이 아니면
        l_value = -heapq.heappop(left_heap)
        r_value = heapq.heappop(right_heap)

        heapq.heappush(left_heap,-r_value)
        heapq.heappush(right_heap,l_value)
    print(-left_heap[0])

풀이

우선순위 큐를 사용해서 풀어야겠다는 생각까지는 했지만 시간초과가 났다.

다른 사람의 풀이들을 찾아보고 공부했다.

최대힙, 최소힙 모두 사용해야한다.

최대힙 : 중간 값 보다 작은 값들을 삽입한다. (내림차순 정렬)

최소힙 : 중간값보다 큰 값들을 삽입한다. (오름차순 정렬)

이 두가지만 생각하고 풀면 최대힙의 첫번째 원소값이 결국 배열의 중간값이 된다.

최대힙을 left_heap

최소힙을 right_heap으로 뒀다.

1) left_heap에 먼저 삽입

2) 다음, right_heap에 삽입 

3) 둘 다 원소가 있고  중간 값보다 더 큰 값이 left_heap[0]에 있을때.... 

len(left_heap) >=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]: 

-left_heap[0] , right_heap[0] 이 값을 서로 부호와 원소를 바꿔준다.

right_heap에 있는 모든 수는 left_heap에 있는 수보다는 커야한다. (중간값이 left_heap[0]에 있으니까!!!! )

4) 중간값 출력 left_heap[0]