Coding 공부

import sys
 
def input():
    return sys.stdin.readline().rstrip()
while True:
    N,M = map(int,input().split())
    if not N+M:
        break
    dp = [[0 for _ in range(M+1)]]
 
    for _ in range(N):
        temp = [0]+list(map(int,input().split()))
        dp.append(temp)
    result = 0
    
    for x in range(1,N+1):
        for y in range(1,M+1):
            dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1 if dp[x][y] else 0
 
            if result<dp[x][y]:
                result = dp[x][y]
    print(result)

이 문제는 유명한 문제이다. 원래 행렬에서 최상단과 좌측에 0인 배열을 넣어주고, 탐색을 해주면 된다.

그리고 (x-1,y), (x,y-1), (x-1,y-1) 의 최소값에 + 1을 해준다. 만약 dp[x][y]에 1이 있을 경우에만

그렇지 않을때에는 0을 넣어주면 된다.

그리고 탐색을 하면서 최대값을 갱신해주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
T = int(input())
 
for _ in range(T):
    d,n = map(int,input().split())
 
    mod = [ 0 for _ in range(d)]
    arr = list(map(int,input().split()))
    prefix_sum = [0] + arr[:]
    mod[0] += 1
    for i in range(n):
        prefix_sum[i+1] += prefix_sum[i]
        prefix_sum[i+1] %= d
        mod[prefix_sum[i+1]] += 1
    result = 0
 
    for i in range(d):
        result += (mod[i] * (mod[i]-1))//2
 
    print(result)

이 문제는 누적합을 활용한 문제이다. 

먼저 누적합을 구하면서 해당 누적합을 d로 나눈 나머지를 mod에 개수로 세어준다.

그러면 우리는 좌측부터 누적했을 때의 d로 나눴을 때  나오는 나머지의 값들이 언제 나오는지 알 수 있다.

그러면 우리는 d로 나눠지는 모든 경우의 수는

같은 나머지를 가지는 구간에서 2개를 뽑아서 그 두 구간을 빼주면 나머지가 0이 됨을 알 수 있다.

그러므로, 우리는 0부터 d-1까지 nC2를 해주면 된다.

그리고 우리는 0부터 하기 위해서, 0일때에 기본값으로 다른 나머지와 달리 1을 넣어주었다.

N = int(input())
def makePrimeNumber(num,idx):
    if idx == N:
        result.append(num)
    else:
        for last_num in range(1,10,2):
            new_num = num*10 + last_num
            if isPrime(new_num):
                makePrimeNumber(new_num,idx+1)
 
def isPrime(num):
    if num in prime_numbers:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i == 0:
            return False
    prime_numbers.add(num)
    return True
 
 
prime_numbers = set([2,3,5,7])
result = []
 
 
for num in [2,3,5,7]:
    makePrimeNumber(num,1)
result.sort()
 
for row in result:
    print(row)

이 문제는 처음에 모든 N자리의 숫자를 primnumber 인지를 구했더니 메모리초과가 났던 문제이다.

이 문제를 푸는 방법은 다음과 같다.

이 문제를 보면 우리는 제일 왼쪽부터 한자리숫자씩 늘리면서 모든 경우에 소수인 것을 구하는 것이다.

그러면 우리가 한자리숫자에서 소수인 것은 2,3,5,7 임을 알 수 있다.

그러면 제일 왼쪽은 무조건 2,3,5,7로 시작되게 해준다.

그리고 N자리를 dfs로 구해주면 된다.

현재 num에 10을 곱하고 끝자리를 바꿔가면서 그 값이 소수인지 판별해주면 된다.

그리고 우리는 한자리숫자를 제외한 두자리숫자부터는 끝 숫자부분이 홀수여야지만 소수가 될 가능성임을 알 수 있다.

그러므로 끝자리는 홀수들만 들어가게 해준다.

소수를 판별하는 방법은 이 수의 제곱근까지의 숫자까지 나눠가면서 나눠지는 경우가 있는지 확인해주면 된다.

그리고 한번 소수로 판별된 경우에는 두번 탐색할 수고를 덜기 위해, set에 저장해준다.

위와 같은 방식으로 N자리 숫자를 만들고

정렬 한뒤에 출력하면 된다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N,M = map(int,input().split())
 
 
graph = [[] for _ in range(N+1)]
 
 
 
for ind in range(M):
    arr = list(map(int,input().split()))
    lens = len(arr)
 
    for arr_ind in range(lens-1):
        cur_node = arr[arr_ind]
        if arr_ind == 0:
            graph[cur_node].append([-1,arr[arr_ind+1],ind])
        else:
            graph[cur_node].append([arr[arr_ind-1],arr[arr_ind+1],ind])
 
start_node, end_node = map(int,input().split())
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
visited_node = [True for _ in range(N+1)]
distance_list[start_node] = 0
queue = deque()
 
queue.append((start_node,0,-1))
 
while queue:
    node,cnt,prev_ind = queue.popleft()
    for left_node,right_node,position in graph[node]:
        if left_node != -1:
            if prev_ind == -1:
                distance_list[left_node] = cnt
                queue.append((left_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[left_node] > cnt + temp:
                    distance_list[left_node] = cnt + temp
                    queue.append((left_node,cnt+temp,position))
        if right_node != -1:
            if prev_ind == -1:
                distance_list[right_node] = cnt
                queue.append((right_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[right_node] > cnt + temp:
                    distance_list[right_node] = cnt + temp
                    queue.append((right_node,cnt+temp,position))
 
 
 
 
if distance_list[end_node] == INF:
    print(-1)
else:
    print(distance_list[end_node])

처음 풀었던 풀이는 좋은 풀이는 아닌것처럼 보인다.

처음 풀었던 방식은 다음과 같다. 현재 노드에 좌우 노드와 현재 노선을 집어넣어준다.

그리고 bfs를 하면서 노선이 바뀔때 그 값이 현재 있는 값보다 적으면 바꿔서 queue에 넣어주는 방식대로 했다.

이 방식의 문제점은 한 노선이 엄청 길면 모든 노선들을 전부 하나하나씩 다 탐색을 하는 것이다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
graph = []
 
subway_routelist = [[] for _ in range(N+1)]
 
 
for route_ind in range(M):
    arr = set(map(int,input().split()))
    arr.remove(-1)
    for subway_num in arr:
        subway_routelist[subway_num].append(route_ind)
 
    graph.append(list(arr))
 
start_node, end_node = map(int,input().split())
visited = [-1 for _ in range(N+1)]
visited_subway = [-1 for _ in range(M)]
end_subway = []
 
for route_ind in range(M):
    if end_node in graph[route_ind]:
        end_subway.append(route_ind)
 
 
queue = deque()
route_cnt = 0
visited[end_node] = 0
for end_route in end_subway:
    visited_subway[end_route] = route_cnt
    for subway_num in graph[end_route]:
        if visited[subway_num] == -1:
            visited[subway_num] = route_cnt
            queue.append(subway_num)
 
if visited[start_node] != -1:
    print(0)
else:
        
    while queue:
        N = len(queue)
        for _ in range(N):
            node = queue.popleft()
            for route in subway_routelist[node]:
                if visited_subway[route] == -1:
                    visited_subway[route] = route_cnt + 1
                    for subway_num in graph[route]:
                        if visited[subway_num] == -1:
                            visited[subway_num] = route_cnt + 1
                            queue.append(subway_num)
        route_cnt += 1
        if visited[start_node] != -1:
            break
 
 
    print(visited[start_node])

이 풀이는 노선을 기준으로 bfs를 하는 방식이다.

먼저 사전 작업으로, subway_route_list에 현재 노선번호를 넣어준다.

graph에는 각 노선의 역정보를 넣어준다.

먼저 우리는 도착지점이 있는 route(노선)들을 전부 구한다. 그 노선이 있는 목록을 end_subway라고 하겠다.

그러면 우리는 이 route들의 모든 노선들은 환승이 없이 도착지점에 도착하는 것을 알 수 있다.

그러므로 우리는 visited_subway라는 노선의 방문을 체크하는 곳에 방문의 여부를 체크를 해준다.

그리고 난뒤에 우리는 이 노선(route)에 있는 역들도 전부 환승없이 방문 할 수 있는 것을 알 수 있다.

그러므로 역의 방문을 나타내는 visited에 방문을 체크해주고, 그때의 역번호를 queue에 넣어준다.

위와 같은 일련의 작업을 한뒤에는 우리가 구할 수 있는 것은 도착지점에서 한번의 환승도 없이 다닐 수 있는

모든 역들을 체크해준것이다.

그러면 우리는 현재 상태에서 start_node가 방문이 표시되었다 하면, 환승없이 start_node에서 end_node까지 갈수 있음을 알 수 있고,

그때는 0을 출력해준다.

만약 그렇지 않을때에는 bfs를 해주면 된다.

이 bfs는 하나의 queue 단위로 bfs를 돌려주면 되므로,

최초의 queue의 크기인 N만큼 popleft를 해주면서, 해당 역에서 갈 수 있는 노선을 갱신해주고,

이 노선에서 갈 수 있는 역 중에 가보지 않은 역들을 queue에 추가해주면된다.

이러한 방식을 통해 최소 환승 횟수를 알 수 있게 된다.

이 문제에서 주요한 점은 역을 중점으로 bfs를 돌리는 것이 아닌 노선을 중심으로 해서 bfs를 돌린다는 점을 주의해주면 된다.

import sys
import heapq
 
def input():
    return sys.stdin.readline().rstrip()
 
def solution():
    priority_que = []
    for num in range(1,N+1):
        if not indegree[num]:
            priority_que.append(num)
    heapq.heapify(priority_que)
 
    result = []
    while priority_que:
        num = heapq.heappop(priority_que)
        result.append(num)
        for next_num in graph[num]:
            indegree[next_num] -= 1
            if not indegree[next_num]:
                heapq.heappush(priority_que,next_num)
    return result
 
N,M = map(int,input().split())
 
graph = [ [] for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    indegree[y] += 1
 
print(*solution())

문제를 읽어보면 순서가 정해져있고, 앞선 문제를 풀어야지 뒤의 문제를 풀 수 있다고 되어 있다.

이 문구를 보고 위상정렬임을 알 수 있고, 위상정렬 해주면 된다.

문제 난이도가 골드2 이지만, 골드2 수준은 아닌 듯한 문제였다. queue 대신 heapq를 쓰면 풀리는 문제라,

위상 정렬에 대해 알고 있으면 쉽게 풀릴 수 있는 문제라 생각한다.

M,N = map(int,input().split())
def string_fun(num):
    temp = []
    for st in num:
        temp.append(num_st[int(st)])
    return ''.join(temp)
arr = []
for num in range(M,N+1):
    arr.append(str(num))
 
num_st = ['zero','one','two','three','four','five','six','seven','eight','nine']
arr.sort(key=string_fun)
 
 
for i in range(len(arr)//10):
    print(*arr[i*10:(i+1)*10])
 
if len(arr)%10:
    for i in range(len(arr)-len(arr)%10,len(arr)):
        print(arr[i],end=' ')

sort에 key를 줘서 정렬을 했다.

import sys
import math
def input():
    return sys.stdin.readline().rstrip()
def check(mid):
    cnt = 0
    for time in arr:
        temp = math.ceil(mid/time)
        cnt += temp
    return cnt
 
N, M = map(int,input().split())
 
arr = list(map(int,input().split()))
 
 
left = 0
right = (N//M+1)*30+1
 
result = 0
while left+1<right:
    mid = (left+right)//2
    if check(mid)>=N:
        right = mid
    else:
        left = mid
 
result = 0
prev_person = check(right-1)
remain_cnt = N - prev_person
for i in range(M):
    temp = math.ceil(right/arr[i]) - math.ceil((right-1)/arr[i])
    if temp>0:
        remain_cnt -= temp
        if not remain_cnt:
            result = i
print(result+1)

 이분탐색을 활용한 문제이다. 이 문제를 푸는 방법은 다음과 같다.

모든 인원이 탈수 잇는 시간을 구하고, 그 시간을 가지고 마지막 탑승할 놀이기구를 찾는것이다. 

먼저 모든인원이 탈수 있는 시간을 이분탐색으로 먼저 찾는 것이다.

이분탐색으로 특정시간을 구하고, 그 특정시간에 놀이기구에 탑승할 수 있는 인원을 구한다.

그리고 인원이 전부 탈수 있는 최소한의 시간을 구하면 되는 것이다.

그러면 우리가 구한 right는 N명의 어린아이들을 모두 태울수 있는 시간인것이다.

그러면 right-1은 N명의 어린아이를 태우지 못하는 직전의 시간이다.

그래서 우리는 전체 N명에서 right-1에서 태울수 있는 어린아이의 수를 구하고,

남은 수를 가지고 마지막 아이가 탈 놀이기구의 번호를 찾을 수 있다.

찾는 방법은 현재 시간에서 직전시간의 인원을 빼서 0이 아니라면 right라는 시간에서 인원이 탑승을 하게 된것이다.

그 점을 이용해서 하나씩 빼가면서 remain_cnt가 0이 되었을때의 값을 구하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def check(mid):
    if mid<0:return 0
    cnt = 0
    for t in range(1,31):
        cnt += (mid//t*time_list[t])
    return cnt + M
N,M = map(int,input().split())
 
time_list = [0 for _ in range(31)]
arr = list(map(int,input().split()))
for t in arr:
    time_list[t] += 1
left = -1
right = (N//M+1)*30+1
 
while left+1<right:
    mid = (left+right)//2
 
    if check(mid)>=N:
        right = mid
    else:
        left = mid
 
 
remain_cnt = N - check(right-1)
for i in range(M):
    if not right%arr[i]:
        remain_cnt -= 1
        if not remain_cnt:
            print(i+1)
            break

위 풀이는 동일한데 math.ceil을 쓰지않는 풀이이다.

최초 0초에 탑승하는걸 별도로 M으로 빼주고 그 이후의 시간대에서 탑승한 것을 세준 것이다.

풀이 방법 자체는 동일하다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
 
 
INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]
 
arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]
 
 
arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
 
for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            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] == '.':
                        arround_trash_can[nx][ny] = 1
 
node_list = []
 
heapq.heappush(node_list,(0,0,start[0],start[1]))
 
step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]
 
while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)
 
    if not visited[x][y]:
        continue
    visited[x][y] = False
 
 
    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] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
 
 
 
 
 
 
x,y = flower
 
print(step_trash[x][y] , arround_trash[x][y])

이 문제를 지문을 이해하는데 어려움을 겪었던 문제였다. 

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

것이 아니였던 점이다.