Coding 공부

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
def path(s,e):
    if next_node[s][e] == None:
        return [0]
    else:
        result = [s]
        while s != e:
            s = next_node[s][e]
            result.append(s)
        return result
N = int(input())
M = int(input())
INF = float('inf')
distance_list = [[0 if i==j else INF for j in range(N+1)] for i in range(N+1)]

next_node = [[None for _ in range(N+1)] for _ in range(N+1)]
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    if distance_list[x][y] > pay:
        distance_list[x][y] = pay
        next_node[x][y] = y


for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance_list[start][end] > distance_list[start][mid] + distance_list[mid][end]:
                distance_list[start][end] = distance_list[start][mid] + distance_list[mid][end]
                next_node[start][end] = next_node[start][mid]


for i in range(1,N+1):
    print(*[val if val != INF else 0 for val in distance_list[i][1:]])


for start in range(1,N+1):
    for ends in range(1,N+1):
        if distance_list[start][ends] == INF:
            print(0)
        else:
            answer = path(start,ends)
            if len(answer) == 1:
                print(0)
            else:
                print(len(answer),*answer)

플로이드 와샬을 이용해서 풀어야하는데

여기서 중요한 점은 이동지점을 추적해야한다.

그 방법은 start-> end까지 갈때 들리는 노드를 갱신을 해주는 것이다.

a->b로 갈때 b로 간다고 저장을 해놨을때

중간에 값을 갱신한 mid가 있으면

a->b에 b가 아닌 mid를 저장해준다.

이렇게 함으로서

end_node가 동일한 것이 나올때까지 계속 반복을 해주면 되는 것이다.

플로이드 와샬은 자주 사용했지만, 경로를 구해본적은 처음이여서 힘들었다.

이 부분은 외우고 나중에 사용할 수 있도록 노력해야겠다.

import sys


def input():
    return sys.stdin.readline().rstrip()


def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False


T = int(input())


for tc in range(1,T+1):
    N = int(input())
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]

    for _ in range(int(input())):
        x,y = map(int,input().split())
        union(x,y)
    print(f'Scenario {tc}:')
    for _ in range(int(input())):
        x,y = map(int,input().split())
        if find_parents(x) != find_parents(y):
            print(0)
        else:
            print(1)

    if tc != T:
        print()

전형적인 분리집합 문제였다.

들어오는 입력대로 union을 해주었고, 서로의 부모가 다를시에는 0 같을 시에는 1이 출력되게 했다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def pop(queue,flag):
    if flag:
        return queue.pop()
    else:
        return queue.popleft()
T = int(input())

for _ in range(T):
    commands = list(input())
    N = int(input())
    if N:
        arr = deque(input().replace('[','').replace(']','').split(','))
    else:
        input()
        arr = deque()
    # 0 정방향 1 역방향
    flow = 0
    flag = True
    for command in commands:
        if command == 'R':
            flow = (flow+1)%2
        else:
            if arr:
                pop(arr,flow)
            else:
                flag = False
                break
    if flag:
        if flow:
            arr.reverse()
        print(f'[{",".join(arr)}]')
    else:
        print('error')

이 문제는 deque를 통해, 역방향인지 정방향인지에 따라 나눠서 결정을 지으면 되는 문제였다.

정방향인지 역방향인지에 따라 pop을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.

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를 쓰면 풀리는 문제라,

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