Coding 공부

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())

graph = [[0 for _ in range(N+1)] for i in range(N+1)]
visited = [[True for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1



for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if start == end:
                continue
            if graph[start][mid] and graph[mid][end]:
                graph[start][end] = 1

result = []
for start in range(1,N+1):
    cnt = 0
    for end in range(1,N+1):
        if start == end:
            continue
        else:
            if not (graph[start][end] or graph[end][start]):
                cnt += 1
    result.append(cnt)
for row in result:
    sys.stdout.write(str(row)+'\n')

많이 해맸던 문제였다. 대소관계가 있는데 그걸 통해, 서로 비교가 불가능한 경우를 찾는 것을 어떻게 할지 고민을 많이했다.

플로이드 와샬을 통해 만들었다. 

대소 관계가 가능하다는 것은 

(1,2) (2,3) 이렇게 주어진다하면

그래프에서 graph[1][2],graph[2][3]에 1이 들어갈것이다.

그러면 플로이드 와샬을 통해, 두개의 그래프가 graph[start][mid], graph[mid][end] 가 전부 1이라고 했을때에만

start 가 end보다 크다는것을 알 수 있다.

이렇게 플로이드 와샬을 돌리고 난뒤에, 전체 N에 대해서 N번 돌려주면서, 서로 다른 두점의 그래프의 값이 전부 0이면, 

대소비교가 불가능한 경우이다. 이 경우를 전부 세어주면 문제를 풀 수 있다.

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = True
    result = []

    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    
    return result


N = int(input())

prime_list = get_prim_number(N)
prefix_sum = prime_list[:]
for i in range(len(prime_list)-1):
    prefix_sum[i+1] += prefix_sum[i]

prefix_sum = [0] + prefix_sum


cnt = 0
left = 0
right = 0
while right <len(prefix_sum):
    temp = prefix_sum[right] - prefix_sum[left]

    if temp == N:
        cnt += 1
        right += 1
    elif temp < N:
        right += 1
    else:
        left += 1
        if temp == 0:
            left = right

print(cnt)

먼저 주어진 N까지의 소수들을 전부 구해준다.

그리고 구한 소수들을 prefix_sum으로 구간합을 구해준다.

두 포인터를 해주면 된다.

import math
import sys

input = sys.stdin.readline

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = False
    result = []

    for num in range(2,int(math.sqrt(N))+1):
        if prime_check[num]:
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
    return result


N = int(input().strip())

prime_list = get_prim_number(N)
interval_sum = 0
left = 0
cnt = 0
for right in range(len(prime_list)):
    interval_sum += prime_list[right]

    while interval_sum > N:
        interval_sum -= prime_list[left]
        left += 1

    if interval_sum == N:
        cnt += 1

print(cnt)

위와 다른점은 소수를 구할때, 루트(N)까지만 반복을 해주는것과,

누적합을 미리 안 구하고, 앞에서부터 하나씩 더해가면서 right를 옮겨주고, N을 넘어가면 left를 늘려가면서 N인 경우를 찾아 주는 것이었다.

import sys
import math
def init():
    global tree_size

    for i in range(tree_size-1,0,-1):
        segement_tree[i] = segement_tree[i*2] + segement_tree[i*2+1]


def update(index,diff):
    while index >= 1:
        segement_tree[index] += diff
        index//=2

def sum_range(node_number,start,end,left,right):
    if left > end or start > right:
        return 0
    if (left <= start) and (end <= right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)
input = sys.stdin.readline

N,M = map(int,input().split())

height = math.ceil(math.log2(N))
tree_size = 2**height
total_size = 2**(height+1)

segement_tree = [0]*total_size

for i in range(N):
    segement_tree[tree_size + i] = 0
init()
for i in range(M):
    command = list(map(int,input().split()))
    if command[0] == 1:
        diff = command[2] - segement_tree[tree_size + command[1] - 1]
        update(command[1]+tree_size-1,diff)
    else:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]
        print(sum_range(1,0,tree_size-1,command[1]-1,command[2]-1))

세그먼트 트리를 이용해서 풀어야했던 문제이다.

여전히 세그먼트 트리는 정확히 잘 모르겠다는게 함정이지만, 예전에 만들어뒀던 세그먼트 트리에서 일부분만 고쳤다.

구간의 값을 특정위치에 미리 저장을 해놓고, 어떤 위치의 값이 변했을때, 그 값이 포함된 구간들을 갱신하는 것인데,

아직 세그먼트 트리는 어려운 것같다.

세그먼트 트리를 짜놓은 코드를 이용해서, 풀라면 풀수 있을것 같지만, 실전에서 노베이스부터 설계를 하라고 하면

너무 어려울 것 같다.

import sys

input = sys.stdin.readline


def init(N):
    for i in range(N-1,0,-1):
        tree[i] = tree[i<<1] + tree[i<<1|1]

def query(left,right,N):
    ans = 0
    left = left +N
    right = right +N
    while left<right:
        if (left&1):
            ans += tree[left]
            left += 1
        if (right&1):
            right -= 1
            ans += tree[right]
        
        left >>= 1
        right>>= 1
    return ans


def update(pos,val,N):
    tree[pos+N] = val
    pos = pos +N
    while pos > 1:
        tree[pos>>1] = tree[pos] + tree[pos^1]
        pos >>= 1
N,M = map(int,input().split())


tree = [0]*(3*N)


for _ in range(M):
    command = list(map(int,input().split()))
    if command[0] == 1:
        update(command[1],command[2],N)
    else:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]

        sys.stdout.write(str(query(command[1],command[2]+1,N))+'\n')

 이 코드는 https://blog.joonas.io/129 에 있는 비재귀 세그먼트 트리를 설명한 글을 이용해서 푼 문제이다.

여전히 어렵다. 

업데이트가 빈번하고, 특정값을 구할때, 트리를 이용한 풀이들이 많은데, 아직 트리에 대해 정확히 알지 못해서

그런지 많이 어렵다.

import sys
import heapq
input = sys.stdin.readline



N = int(input())
node_list = []
pay_list = []

for i in range(N):
    pay = int(input())
    heapq.heappush(node_list,(pay,i))
    pay_list.append(pay)


connect_list = [list(map(int,input().split())) for _ in range(N)]

result = 0
visited = [False]*N
while node_list:
    pay,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += pay

    for next_node in range(N):
        if next_node != node:
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list,(pay_list[next_node],next_node))


print(result)

이 문제는 MST 문제로 기존의 MST와 다르게 여러개의 출발점을 동시에 가지는 MST라고 생각을 했다.

각 출발지점에 따라, 다른거이기 때문에 프림 알고리즘을 크루스칼 알고리즘보다 먼저 생각했다.

그래서 각 출발지점을 전부 입력으로 주어진 우물 개설비용으로 초기화 시켜준 점이 기존의 프림알고리즘하고

다른 방식이었다.

그리고 우물을 파는 비용,논의 위치를 heapq에 넣은듯 프림알고리즘을 해주었다.

그리고 방문 표시를 해서, 한번 들린곳은 다시 들리지 않도록 예외 처리를 해줬다.

기존의 MST에서 1곳의 출발지점을 정했던것과 달리, 모든 곳을 출발지점으로 생각하고, 비용을 갱신하면 되는 문제였다.

import sys

input = sys.stdin.readline

N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]


def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)

    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)

arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))



make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

크루스칼을 활용한 풀이이다.

여기서도 기존의 MST와 비슷하지만, 다른점은 물이 생성을 하는곳을 0이라는 인덱스를 부모로 가지도록

설정을 해주었다. 우물을 파서, 공급을 받는 곳은, 위치가 다를지라도, 물을 공급받고 있는 것이기 때문에

하나의 집합이라고 볼수 있기 때문이다. 이와 같은 작업을 N개가 이어질때까지 반복해주면 된다.

이 문제는 사실 https://boj.kr/10423 의 문제와 거의 동일하다고 볼 수 있다.

import sys
input = sys.stdin.readline


G = int(input())
P = int(input())
result = 0
plane = [int(input()) for _ in range(P)]


parents_number = [i for i in range(G+1)]

visited = [False]*(G+1)
cur_idx = 0
planing = True

while cur_idx<P and planing:

    cur_plane_number = plane[cur_idx]
    check = [cur_plane_number]
    while visited[cur_plane_number] and cur_plane_number>0:
        cur_plane_number = parents_number[cur_plane_number]
        check.append(cur_plane_number)
    
    
    
    if cur_plane_number == 0:
        break
    else:
        visited[cur_plane_number] = True
        for num in check:
            parents_number[num] = cur_plane_number-1

    cur_idx += 1

print(cur_idx)

이 문제는 프로그래머스의 호텔 방 배정하기하고 동일한 문제라고 볼수 있다.

주어진 위치가 있고, 1~위치 사이에 비행기를 도킹할 수 없으면, 멈추면 되는것이다.

호텔 방 배정하기하고 동일하게, 자신의 다음 도킹 위치를 저장시켜놓으면 된다. 

그러면서 최악의 경우를 방지하기 위해, 그 다음 도킹위치를 새로 갱신해주는 작업을 해주면 된다.

import sys

input = sys.stdin.readline

def find_parent(idx):
    if idx == make_set[idx]:
        return idx
    else:
        make_set[idx] = find_parent(make_set[idx])
        return make_set[idx]

G = int(input())
P = int(input())

make_set = [i for i in range(G+1)]


result = 0
for k in range(P):
    plane_num = int(input())
    gate_num = find_parent(plane_num)

    if gate_num < 1:
        break
    else:
        make_set[gate_num] = make_set[gate_num-1]
        result += 1
        

print(result)

이거는 좀 더 함수로 만들어놓은 것이다.

위와 똑같은 로직이지만, find_parent 라는 재귀함수를 통해, 자동적으로 갱신이 되게 해주었다.

호텔 방 배정하기 문제를 수월하게 풀었으면 이 문제도 수월하게 풀 수 있을거라 생각한다.

import sys
import heapq
input = sys.stdin.readline

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

graph = [{} for _ in range(N+1)]

parent_node = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')),pay)
    parent_node[y][x] = min(graph[y].get(x,float('inf')),pay)

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)

    if distance[cur_node] < cur_dis:
        continue
    for next_node in graph[cur_node]:
        if distance[next_node] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


print(distance[end_city])
result = [end_city]
stack = [(distance[end_city],end_city)]
while stack:
    dis,cur_node = stack.pop()
    if cur_node == start_city:
        break
    for prev_node in parent_node[cur_node]:
        if graph[prev_node][cur_node] + distance[prev_node] == dis:
            stack.append((distance[prev_node],prev_node))
            result.append(prev_node)
            break

print(len(result))
result.reverse()
print(*result)
    

다익스트라를 이용해 푸는 문제이고, 경로를 추적해주면 되는 문제였다.

백준 5719번 문제 거의 최단경로에서 다익스트라 경로를 추적을 해본적이 있어서, 쉽게 풀수 있었다.

처음에 틀렸습니다를 받았는데, 경로를 추적하면서 출발점에 도착했을때, 반복문을 종료를 안시켜줘서 그렇다.

그 이유는 문제 조건 중에 pay가 0인경우가 있기때문에, 출발점을 넘어서 다른경로를 더 추적한 것 같다.

import sys
import heapq
input = sys.stdin.readline

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

graph = [{} for _ in range(N+1)]

path = [-1 for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')),pay)

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)

    if distance[cur_node] < cur_dis:
        continue
    for next_node in graph[cur_node]:
        if distance[next_node] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))
            path[next_node] = cur_node


print(distance[end_city])
result = []
city = end_city

while True:
    if city == start_city:
        result.append(city)
        break
    result.append(city)
    city = path[city]
print(len(result))
result.reverse()
print(*result)
    

 두번째 풀이는 위의 풀이보다 좀 더 깔끔한 풀이이다.  그 방식은 다익스트라를 하면서, 부모노드를 기록해주는 것이다.

최저 경로를 갱신해준 부모노드를 기록해주면, 최저의 비용으로 움직이는 하나의 경로를 저장할 수 있을것이다.

이걸 이용해서, start_city가 올때까지 반복문을 돌리는 방식으로 구현할 수 있다.

첫번째 풀이는, 모든 이동경로를 찾을때 쓰면 괜찮을 방법인것 같다.

def dfs(cnt):
    if cnt == 81:
        for row in sdoku:
            print(''.join(list(map(str,row))))
        exit()
    else:
        x = cnt//9
        y = cnt%9
        square = (x//3)*3 + y//3
        if sdoku[x][y] == 0:
            for num in range(1,10):
                if not (column_check[y][num] or row_check[x][num] or square_check[square][num]):
                    column_check[y][num] = True
                    row_check[x][num] = True
                    square_check[square][num] = True
                    sdoku[x][y] = num
                    dfs(cnt+1)
                    sdoku[x][y] = 0
                    column_check[y][num] = False
                    row_check[x][num] = False
                    square_check[square][num] = False


        else:
            dfs(cnt+1)



sdoku = []

column_check = [[False for _ in range(10)] for _ in range(9)]
row_check = [[False for _ in range(10)] for _ in range(9)]
square_check =[[False for _ in range(10)] for _ in range(9)]
for x in range(9):
    temp = list(map(int,list(input())))
    for y in range(9):
        if temp[y] != 0:
            square = (x//3)*3 + y//3
            column_check[y][temp[y]] = True
            row_check[x][temp[y]] = True
            square_check[square][temp[y]] = True
    sdoku.append(temp)


dfs(0)

스도쿠의 특성을 활용해서 하면 된다.

먼저 각 열, 각 행, 3*3 사각형의 숫자를 얼만큼 사용했는지를 CHECK 해주는 리스트를 만들어준다.

여기서 square 넘버를 부여하는 방식은 (x//3)*3 + (y//3)으로 해서, 가장 위에서 부터 

0 1 2

3 4 5

6 7 8

로 구분이 가능하게 해줬다.

그리고 dfs를 활용해서, cnt는 전체 칸의 갯수를 뜻하면서, 좌표를 뜻하도록 했다. 해당 좌표에서 비어있으면,

숫자를 하나씩 넣어가면서 백트래킹을 해줬다.

그리고 마지막에 도착하면, 현재 스도쿠를 출력해주고, 함수를 종료시켜줬다.

가장 앞에서부터 하나하나씩 채워나가는 것이기때문에, 가장 먼저 완료되는것이 사전순으로 가장 빠른 스도쿠가 된다.

N = int(input())
arr = [int(input()) for _ in range(N)]
stack = []
result = []
idx = 0
for i in range(1,N+1):
    stack.append(i)
    result.append('+')
    while stack and stack[-1] == arr[idx]:
        stack.pop()
        result.append('-')
        idx += 1

if stack:
    print('NO')
else:
    for i in result:
        print(i)

문제에 주어진대로 1부터 차근차근 숫자가 들어온다. 그리고 문제에 주어진 수열을 만드는 것인데,

스택에 들어간 수 중의 끝부분이 주어진 수열과 동일하면 하나씩 pop을 하면서 수열을 맞춰준다.

이 작업을 전부 했는데도, stack에 수가 남아있는것은 주어진 수열을 못 만드는것이기 때문에,

NO를 출력하고,

stack이 다 비어있으면 만든것이기때문에 push pop을 출력해주면 된다.