Coding 공부

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
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을 출력해주면 된다.

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

def union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0

    else:
        if child_cnt[X]< child_cnt[Y]:
            make_set[X] = Y
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[Y] += child_cnt[X]
        else:
            make_set[Y] = X
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[X] += child_cnt[Y]

        return return_value
            
        

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


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

make_set = [i for i in range(N+1)]
child_cnt = [1 for i in range(N+1)]
connect_input = [[],]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    connect_input.append((x,y))

result = 0
disconnet_list = []

for _ in range(Q):
    ind = int(input())
    x,y = connect_input[ind]
    graph[x][y] = 0
    graph[y][x] = 0
    disconnet_list.append(ind)


for i in range(1,M+1):
    if i not in disconnet_list:
        x,y = connect_input[i]
        union(x,y)


while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

이 문제는 역으로 생각하는 편이 제대로 푸는 방식이었다 윗 코드는 첫 풀이이다.

문제를 푸는 방식은 다음과 같다. 문제에서 주어진 끊어진 조건들을 전부 끊어졌다고 가정을 하고

끝에서부터 하나씩 연결을 해가면서 반대로 추적을 하는것이다.

그러므로, 먼저 전체 연결리스트를 들어온 순서에 맞게 index에 알맞게 저장을 해준다.

그리고 난뒤에 끊어진 목록들을 따로 저장을 해두고, 끊어지지 않은 연결들끼리 서로 union find를 해준다.

union_find를 하면서, 각자의 노드 개수를 저장해주는 리스트를 따로 만들어두고,

서로 다른 집합이 합쳐질때 그 두 개의 노드의 개수를 합쳐주는 로직을 해주면 된다.

이렇게 연결이 된 간선들로 union find를 1차적으로 진행을 한다.

그리고 끝에서부터 끊어진 간선들끼리 연결을 해준다. 그러면 그 간선을 끊기전 모습으로 돌아갈 수 있다.

이렇게 하면서 서로의 집합이 같으면 0을 반환하고, 그게 아니면 서로의 집합의 개수를 곱한 수를 반환하도록 했다.

import sys

input = sys.stdin.readline


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

def union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0

    else:
        if rank[X] < rank[Y]:
            X,Y = Y,X

        size_a,size_b = rank[X],rank[Y]
        rank[X] += rank[Y]
        make_set[Y] = X
        return size_a*size_b
            
        

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



make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
connect_input = [[],]
check = [True]*(M+1)
for _ in range(M):
    x,y = map(int,input().split())
    connect_input.append((x,y))

result = 0
disconnet_list = []

for _ in range(Q):
    ind = int(input())
    disconnet_list.append(ind)
    check[ind] = False


for i in range(1,M+1):
    if check[i]:
        x,y = connect_input[i]
        union(x,y)


while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

좀 더 깔끔하고 빠른 풀이 방식이다. 첫 풀이 코드같은경우엔 느렸는데

그 이유는 간선이 연결됬는지 안됬는지를 구분하는데 not in 으로 했기 때문에, O(N)의 시간이 걸려서 느려진 문제가 있었다.

그래서 간선들이 연결이 됬는지 안됬는지를 구분하는 리스트를 만들어두고 바로 확인이 가능하도록 했다.

https://www.secmem.org/blog/2021/03/21/Disjoint-Set-Union-find/

설명은 잘 못하므로 위의 링크에 있는 Union_find를 보면 알겠지만, rank compression을 활용해서 시간을 좀 더 줄였다.

Union find는 크루스칼알고리즘에서 처음으로 알게 되었는데, 크루스칼에서만 쓰이는줄 알았는데,

생각외로 단독으로 쓰이는 곳이 많았다. 이걸 짜는데 어색해서 크루스칼 알고리즘을 잘 안쓰는데,

좀 더 숙달되도록 노력해야겠다.

import sys

sys.setrecursionlimit(100000)


def dfs(x,y):
    if visited[x][y]:
        return INF
    elif dp[x][y] >0:
        return dp[x][y]
    else:
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]*int(arr[x][y])
            ny = y + dy[i]*int(arr[x][y])
            if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
                dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
                if dp[x][y] == INF:
                    return INF
        visited[x][y] = False
    return dp[x][y]

            





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



result = dfs(0,0)

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

 DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.

여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던 

장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.

그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서

탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.

기본적이 풀이 방식은 다음과 같다.

왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,

방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.

그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.

이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.

그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.

그리고 현재 DP 값을 돌려주면 된다.

이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.