Coding 공부

def dfs(x,y):
    global N,M
    if x == N-1 and y == M-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] < arr[x][y]:
                    dp[x][y] += dfs(nx,ny)
        return dp[x][y]



import sys

input = sys.stdin.readline

N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
print(dfs(0,0))

DP 와 DFS가 결합된 문제였다. 최소로 도달한거리를 DP에 저장해서 얻는것이었다. 마지막 우리가 도달해야하는 위치만 초기값을 1로 주고, 나머지는 전부 0으로 초기화한뒤 역으로 계싼해서 오는것이다.

import sys
input = sys.stdin.readline

def check_sdouk(x,y):
    index_set = set(range(1,10))
    occupy_set = set()
    for checky in range(9):
        if sdoku[x][checky]:
            occupy_set.add(sdoku[x][checky])
    for checkx in range(9):
        if sdoku[checkx][y]:
            occupy_set.add(sdoku[checkx][y])
    squarex = x//3*3
    squarey = y//3*3
    for checkx in range(squarex,squarex+3):
        for checky in range(squarey,squarey+3):
            if sdoku[checkx][checky]:
                occupy_set.add(sdoku[checkx][checky])
    return index_set-occupy_set



def sdoku_input(cnt):
    global check_max,result
    if cnt == check_max:
        result = [row[:] for row in sdoku]
        for row in result:
            print(*row)
        sys.exit()
        return
    else:
        a = check_sdouk(*check_list[cnt])
        if a:
            for number in a:
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = number
                sdoku_input(cnt+1)
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = 0
        else:
            return




sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))

    for y in range(9):
        if not input_list[y]:
            check_list.append((x,y))
    sdoku.append(input_list)
result = []
check_max = len(check_list)
sdoku_input(0)

재귀를 이용해서 풀었다.

sys.exit()를 통해 최초의 결과가 나오면 바로 나오게 해줬다.

import sys
input = sys.stdin.readline



def check(cnt):
    if cnt == len(check_list):
        for row in sdoku:
            print(*row)
        sys.exit()
    else:
        x,y = check_list[cnt]
        square_ind = x//3*3 + y//3
        for number in range(1,10):
            if row_index[x][number] + col_index[y][number] + square_index[square_ind][number] == 0:
                row_index[x][number] = 1
                col_index[y][number] = 1
                square_index[square_ind][number] = 1
                sdoku[x][y] = number
                check(cnt+1)
                row_index[x][number] = 0
                col_index[y][number] = 0
                square_index[square_ind][number] = 0
                sdoku[x][y] = 0


row_index = [[0]*10 for _ in range(9)]
col_index = [[0]*10 for _ in range(9)]
square_index = [[0]*10 for _ in range(9)]


sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))

    for y in range(9):
        if input_list[y]:
            row_index[x][input_list[y]] = 1
            col_index[y][input_list[y]] = 1
            square_ind = x//3*3 + y//3
            square_index[square_ind][input_list[y]] = 1
        else:
            check_list.append((x,y))
    sdoku.append(input_list)


check(0)

  위는 시간이 오래걸려서 개선된 버전이다. 이 방법은 col,row,square 마다 1~9까지의 list를 만들어놓고 거기서 바로 판단이 가능하게 바꿨다.

import sys
from collections import deque

input = sys.stdin.readline
def bfs():
    global INF,result
    stack = deque()
    stack.append((0,0,1,0))
    visited = [[[INF for z in range(2)] for _ in range(M)] for _ in range(N)]
    visited[0][0][0] = 1
    visited[0][0][1] = 1
    while stack:
        x,y,dis,wall_cnt = stack.popleft()
        if x== N-1 and y == M-1:
            if result > dis:
                result = dis
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx< N and 0<= ny < M:
                if visited[nx][ny][wall_cnt] > dis + 1 and wall_cnt <=1:
                    if arr[nx][ny] == '1' and not wall_cnt:
                        visited[nx][ny][wall_cnt] = dis + 1
                        stack.append((nx,ny,dis+1,wall_cnt+1))
                    elif arr[nx][ny] == '0':
                        visited[nx][ny][wall_cnt] = dis +1
                        stack.append((nx,ny,dis+1,wall_cnt))


N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(N)]
wall = []
INF = float('inf')


result = INF
bfs()
if result == INF:
    print(-1)
else:
    print(result)

처음 풀었던 방식은 BFS를 하면서 방문을 했는지 안했는지를 하나의 축으로 추가해서 visited에 표시를 해주는 거였다.

import sys
from collections import deque


input = sys.stdin.readline


N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
INF = float('inf')
distance_front = [[INF]*M for _ in range(N)]
distance_back = [[INF]*M for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
stack1 = deque()
stack2 = deque()
distance_front[0][0] = 1
distance_back[N-1][M-1] = 0

stack1.append((0,0))
stack2.append((N-1,M-1))

while stack1:
    x,y = stack1.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<= ny <M:
            if distance_front[nx][ny] == INF:
                distance_front[nx][ny] = distance_front[x][y] +1
                if arr[nx][ny] == '0':
                    stack1.append((nx,ny))

while stack2:
    x,y = stack2.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny <M:
            if distance_back[nx][ny] == INF:
                distance_back[nx][ny] = distance_back[x][y] + 1
                if arr[nx][ny] == '0':
                    stack2.append((nx,ny))

result = distance_front[N-1][M-1]

for x in range(N):
    for y in range(M):
        if arr[x][y] == '1':
            result = min(result,distance_front[x][y]+distance_back[x][y])

if result != INF:
    print(result)
else:
    print(-1)

개선된 방식은 0,0에서 BFS를 돌리고, 목표지점인 (N-1,M-1)에서 BFS를 돌린다. 그리고 BFS를 돌리면서 최단거리를 저장해놓는다.

그리고 첫번째 돌린 BFS의 최단거리에서 목표지점까지의 최단거리를 구하고,

벽을 부셨을때 최단거리는 두개의 BFS의 합을 통해 구한다.

벽인 지점 (A,B)가 있으면, 첫번째 돌린 BFS의 (A,B)의 값과 두번째 돌린 BFS의 (A,B)을 합쳐주면 그 벽을 부셨을때의 최단 이동거리가 된다.

위와 같이 할려면 초기값을 주의해야하는데, 첫번째 BFS의 초기값은 1이고, 두번째 BFS는 0이다.

import heapq
import sys
input = sys.stdin.readline
N = int(input())

times = []
for _ in range(N):
    input_tuple = tuple(map(int,input().split()))
    heapq.heappush(times,input_tuple)

end_time_list = []
answer = 0
while times:
    start_time,end_time = heapq.heappop(times)
    if not end_time_list:
        answer += 1
        heapq.heappush(end_time_list,end_time)
    else:
        if end_time_list[0] > start_time:
            heapq.heappush(end_time_list,end_time)
            answer += 1
        else:
            heapq.heappop(end_time_list)
            heapq.heappush(end_time_list,end_time)
            
        
print(answer)

우선순위 힙을 응용한 문제이다. 먼저 (시작시간,종료시간)이 입력을 들어왔을때, 하나의 리스트에 저장을 해준다.

그리고 그것을 시작시간을 기준으로 정렬을 해준다.

그리고 하나씩 꺼내면서 판단을 해주면 된다.

end_time_list가 비워져있으면, 종료시간을 그냥 넣어준다.

end_time_list의 첫번째 값 즉. 가장 먼저 강의가 종료되는 시간보다, 현재 강의의 시작시간이 더 빠르면(작으면) 강의실을 여러개 구해야한다.

그러므로 answer를 +1 해주고, end_time_list에 현재 강의의 종료시간을 넣어준다.

그렇지 않을시에는, 강의실을 추가로 빌린필요가 없으므로, 가장 첫번째 값을 없애고, 현재 강의 종료시간을 end_time_list에 저장을 시켜준다.

end_time_list의 가장 첫번째 값은 가장 작은 값으로 유지되어야하므로, 우선순위 큐인 heapq를 사용했다.

import heapq
import sys
input = sys.stdin.readline

N = int(input())
class_list = []
for _ in range(N):
    start_time,end_time = map(int,input().split())
    class_list.append((start_time,end_time))

class_list.sort()
end_time_list = []
for start_time,end_time in class_list:
    if end_time_list:
        if end_time_list[0] <= start_time:
            heapq.heappop(end_time_list)
        heapq.heappush(end_time_list,end_time)
    else:
        heapq.heappush(end_time_list,end_time)

print(len(end_time_list))

좀 더 깔끔한 방식으로 푼 코드이다. 강의의 전체 정보를 저장하는 리스트는 굳이, 우선순위 힙을 쓸필요가 없으므로, 일반리스트로 쓰면서 정렬을 해줬다.

그리고 다른 변수로 answer를 저장하던걸 어차피, end_time_list의 길이와 답이 일치하므로, end_time_list의 길이로 답을 출력해주었다.

import heapq
import sys
input = sys.stdin.readline
def dijkstra(start_list,flag):
    global V,mac,star,INF,limit_x,limit_y,home_info
    distance = [INF]*(V+1)
    node_list = []
    limited = limit_x
    if flag:
        limited = limit_y
    for ind in start_list:
        distance[ind] = 0 
        heapq.heappush(node_list,(0,ind))

    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > limited:
            break
        if current_distance > distance[node]:
            continue
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    for ind in home:
        if limited >= distance[ind]:
            home_info[ind][int(flag)] = distance[ind]
    

V,E = map(int,input().split())
INF = float('inf')
graph = [{} for _ in range(V+1)]

for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u][v] = w
    graph[v][u] = w
mac_cnt,limit_x = map(int,input().split())
mac = set(map(int,input().split())) 
star_cnt,limit_y = map(int,input().split())
star = set(map(int,input().split()))

home = set(range(1,V+1))- mac - star
home_info = [[INF,INF] for _ in range(V+1)]

dijkstra(mac,False)
dijkstra(star,True)
min_sum = INF
for home_ind in home:
    if sum(home_info[home_ind]) < min_sum:
        min_sum = sum(home_info[home_ind]) 

if min_sum != INF:
    print(min_sum)
else:
    print(-1)

  다익스트라를 응용한문제이다. 처음에 집을 기준으로 하니 시간초과가 떴다.

그래서 역으로 맥도날드와 스타벅스를 각각을 기준으로 해서 다익스트라를 했다.

맥도날드를 각각의 시작점으로해서 집들하고 가장 짧은 거리를 갱신을 해주면된다. 그리고 이걸 저장할 때 x를 넘지 않는 경우에만 home_info 라는 리스트에 저장을 해줬다.

스타벅스도 동일하게 해주었다.

그리고 난뒤 마지막에 최저합을 구해서 출력을 해주었다.

N = int(input())


arr = list(map(int,input().split()))

start = 0
end = N-1
index_list = (arr[start],arr[end])
result = arr[end]+arr[start]

while start<end:
    temp = arr[end]+arr[start]
    if abs(result) > abs(temp):
        result = temp
        index_list = (arr[start],arr[end])
        if result == 0:
            break
    if temp >= 0:
        end -= 1
    else:
        start += 1


print(*index_list)

두 용액 문제하고 동일하다. 투 포인터를 이용해서 풀어주면 된다.

def dfs(W,H):
    if W == 0:
        return 1
    if dp[W][H]:
        return dp[W][H]
    dp[W][H] = dfs(W-1,H+1)
    if H>0:
        dp[W][H] += dfs(W,H-1)
    return dp[W][H]



while True:
    N = int(input())

    if not N:
        break
    dp = [[0]*31 for _ in range(N+1)]

    print(dfs(N,0))

재귀적으로 푸는 방식이다.

한알로 먹는 먹을수 있는 개수를 W, 반알로 먹을 수 있는 개수를 H로 두고 재귀적으로 풀면 된다.

원래 들어온 W,H에서 기본적으로 W가 남아있으면, 한알을 꺼내먹을수 있기에 W-1,H+1로 함수를 실행시켜준다.

그리고 만약 H가 있다면, 반알을 먹을수도 있으므로, W,H-1로 함수를 실행시켜준다.

그러다가 한알짜리 알약이 전부 떨어지면, 남은경우는 반알을 전부 먹는것이므로 return 1을 해주며, 중단해준다.

이렇게 해서 전체 날짜에서 먹을수 있는 날짜를 구하면 된다.

dp = 31*[0]
dp[1] = 1
dp[0] = 1


for n in range(2,31):
    for i in range(n):
        dp[n] += dp[i]*dp[n-i-1]

while True:
    N = int(input())
    if not N:
        break
    print(dp[N])

 위와 같은 형태의 문제를 카탈란 수라고 한다. 자세한 설명은 아래의 사이트에서 읽어보면 된다.

   카탈란 수 설명 출처 : suhak.tistory.com/77

카탈란 수의 점화식을 이용해서 쉽게 푸는 방법도 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))
    visited = set()
    visited.add((N,M))
    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                if nodes not in visited:
                    visited.add(nodes)
                    stack.append(nodes)
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

 처음으로 풀어본 영어로 된 문제이다. 영어로 되어있는 것을 제외하고는 그렇게 어렵지 않은 문제이고, python으로 통과한 사람들이 적다보니 통과시간에 걸릴까 걱정했는데 처음에는 아슬아슬하게 통과했다.

제한시간 2초인데 1.9초가 떴었다.

문제를 봐보면 일반적인 방탈출 게임 같아보인다. 하지만 여기서는 상하좌우로 움직이던 일반적인 bfs가 아닌 현재 내가 밟은 위치에 있는 값에 따라 움직일 수 있는 위치가 달라진다.

그 방법은 현재 내가 밟고있는 index에 위치한 값의 약수 쌍의 좌표로만 옮겨갈수 있다

예를 들면 

3 10 8 14

1 11 12 12

6 2 3 9

문제에 있는 3*4 배열을 봐보면

처음 시작 위치는 (1,1)이다. 그 위치에 있는 값은 3이므로, 3의 약수는 (1,3) (3,1)로 갈 수 있다.

그러면 다음 위치는 (1,3) 이나 (3,1)이 될수 있는데

만약 (1,3)이라한다면 (1,3)에 있는 값은 8 이다. 8의 약수는 (1,8) (2,4),(4,2),(8,1)이 존재할 수 있는데,

(4,2),(8,1),(1,8)은 범위를 넘어가므로, 갈 수 없다.

그러므로 (2,4)로 갈 수 있다.

이런식으로 jump를 해서 우측 최하단에 도착하는 게임이다.

도착이 가능하면 yes 불가능하면 no를 출력해주면 된다.

처음에는 약수를 구하는 생각을 해봤는데, 주어진 행렬의 최대가 1000*1000이다. 거기에 주어지는 최대값은 100만이다.

100만에 대한 모든 약수를 구하다보면  10억번 정도의 연산이 필요로 할 것 같아서, 폐기했다.

그 다음으로 생각한 방법이 위의 풀이이다.

역으로 올라가보자는 것이다.

우리가 (N,M)에 도착하기 위해서 무조건 배열 내에 N*M인 값이 존재해야한다.

1. N*M을 가지고 있는 위치를 찾아간다.

2. 그 위치에 도달할 수 있는 값을 찾아서 또 이동한다.

위와 같은 로직을 생각했다.

즉, 위의 예제로 설명하면

(3,4)에 도착하기 위해서는 12의 값이 필요한데, 이 12를 가진 발판의 위치는 (2,3),(2,4)이다.

(2,3)에 도착하기 위해서는 6의 값이 필요한데 6이 존재하는 위치는 (3,1)이다.

(2,4)에 도착하기 위해서는 8의 값이 필요한데 8이 존재하는 위치는 (1,3)이다.

(3,1),(1,3)에 도착하기 위해서는 3의 값이 필요한데 3이 존재하는 위치는 (1,1) 아니면 (3,3)이다.

이렇게 해서 풀 수 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))

    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                stack.append(nodes)
            del dict_array[x*y]
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

이 코드는 위의걸 개선한 코드이다. 방문표시를 하기위해서 visited를 쓰는대신 한번 방문한 곳은 전부 지워버렸다.