Coding 공부

import sys

def find_agent(agent,task):
    if agent == N:
        return 1
    
    if dp[task] != -1:
        return dp[task]

    for i in range(N):
        if not (task & 1<<i):

            temp = find_agent(agent+1,task|1<<i)*arr[agent][i]/100
            if temp > dp[task]:
                dp[task] = temp
    
    return dp[task]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]


dp = [-1 for _ in range(2**N+1)]




find_agent(0,0)

print(dp[0]*100)

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

각 task를 비트로 구분을 하게 한다.

이 문제에서 최대 20개의 임무가 있으므로, 2^20으로 비트를 구분해낼수 있다.

이러한 점을 이용해, 각자리의 비트는 그와 대응되는 일을 맡는것으로 가늠할 수 있다.

그래서 우리는 재귀를 이용해, 현재까지 선택된 task에서 선택되지 않은 task를 선택해 재귀를 한뒤,

그 결과값들을 최대값으로 갱신을 해주면 되는 문제이다.

또한 중복되는 일을 방지하고자, task별로 값을 저장한뒤에 그 값이 초기값이 아니면 되돌려주는 작업을 해주었다.

import sys
import heapq
input = sys.stdin.readline
def dijkstra_fox():
    distance = [INF for _ in range(N+1)]

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

    while node_list:
        dis,cur_node = heapq.heappop(node_list)
        if distance[cur_node] < dis:
            continue

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


def dijkstra_wolf():
    distance = [[INF for _ in range(N+1)] for _ in range(2)]
    distance[1][1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1,1))

    while node_list:
        dis,cur_node,turn = heapq.heappop(node_list)
        turn = turn%2
        next_turn = (turn+1)%2
        if distance[turn][cur_node] < dis:
            continue
        for next_node in graph[cur_node]:
            if turn:
                next_distance = dis + graph[cur_node][next_node]//2
            else:
                next_distance = dis + graph[cur_node][next_node]*2
            
            if distance[next_turn][next_node] > next_distance:
                distance[next_turn][next_node] = next_distance
                heapq.heappush(node_list,(next_distance,next_node,next_turn))
    return distance
N,M = map(int,input().split())

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

for _ in range(M):
    x,y,d = map(int,input().split())
    graph[x][y] = d*2
    graph[y][x] = d*2

INF= float('inf')




distance_fox = dijkstra_fox()
distance_wolf = dijkstra_wolf()
result = 0
for i in range(2,N+1):
    if distance_fox[i] < distance_wolf[0][i] and distance_fox[i] < distance_wolf[1][i]:
        result += 1

print(result)

어려웠던 문제였다.

 이 문제는 다음과 같이 풀면된다. wolf일때 2개의 turn으로 나누어서 distance에 저장을 시켜준다.

현재 turn의 distance에 저장하는 것이 아닌 next_turn에 저장을 하고 그 값을 비교하는 것에 조심해주면 된다.

그리고 제일 주의해야할 것은 가장 처음 시작하는 노드를 0으로 초기화할때 가장 첫턴 1턴 1번 노드만 0으로

초기화 시켜야 한다

이를 지키지 않고 둘다 초기화 시키면,, 틀렸습닏를 볼 수 있을 것이다.

def dfs(cnt,goal,res):
    if cnt == goal:
        print(*res)
        return
    else:
        for i in range(N):
            if visited[i]:
                temp = res + [arr[i]]
                if tuple(temp) not in record:
                    visited[i] = False
                    record.add(tuple(temp))
                    dfs(cnt+1,goal,temp)
                    visited[i] = True


N,M = map(int,input().split())
visited = [True]*N
record = set()
arr = list(map(int,input().split()))

arr.sort()


dfs(0,M,[])

문제 자체는 어렵지 않은 문제이다. 조합을 이용해서 문제를 풀어주면 된다.

그리고 RECORD를 이용해서 중복되는 경우를 배제해줬다.

import sys
import heapq
input = sys.stdin.readline


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



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


conquer = -1
pay_list = [[INF for _ in range(N+1)] for _ in range(2)]
pay_list[0][1] = 0
visted = [False]*(N+1)
cur_pay,cur_node = 0,1
result = 0
total_city = set(range(1,N+1))
while conquer<N-1:
    if visted[cur_node]:
        continue
    visted[cur_node] = True
    result += cur_pay
    total_city.remove(cur_node)
    conquer += 1
    idx = conquer%2
    if conquer > 0:
        prev_idx = (conquer+1)%2
        for city_num in total_city:
            pay_list[idx][city_num] = pay_list[prev_idx][city_num]+T
    
    min_idx = -1
    min_pay = INF
    for next_node in graph[cur_node]:
        temp_pay = graph[cur_node][next_node] + conquer*T
        if pay_list[idx][next_node] > temp_pay:
            pay_list[idx][next_node] = temp_pay

    for city_num in total_city:
        if min_pay > pay_list[idx][city_num]:
            min_pay = pay_list[idx][city_num]
            min_idx = city_num
    cur_pay,cur_node = min_pay,min_idx


print(result)

 이 문제는 어렵게 생각해서 오래 걸렸던 문제였다. 이 문제를 쉽게 생각해보면, conquer 비용은 고정적이다.

이 conquer 비용을 생각지 않고, 가장 마지막까지 구하고 난뒤에 conquer 비용만 더해주면 되는 문제이긴했다.

하지만 풀때에는 이 방식에 대해 잘 몰랐고, 그걸 적용시키지 않고, conquer 비용을 바로바로 구해주었다.

이 풀이의 방식은 다음과 같다 pay_list를 2*(N+1)로 해주었다.

즉 우리가 프림알고리즘에서 pay를 저장하는걸 1차원 배열 하나로 했던 거에 비해 2차원 배열을 이용해서 문제를 풀었다.

각각의 의미는 다음과 같다. 현재의 conquer 수치를 같이 저장을 해주면서

현재 conquer가 짝수이면, 0이고, 그때의 이전 pay_list 비용은 1번 인덱스에 있다.

현재 conquer가 홀수이면 1이고, 그때의 이전 pay_list 비용은 0번 인덱스에 있다.

즉 슬라이딩 윈도우처럼 각 전단계의 pay_list를 가져와서 현재 우리가 구하고자 하는

pay_list에 덮어씌워주는 방식으로 했다.

그 뒤에는 일반적인 프림알고리즘과 비슷하다.

현재 노드에서 갱신될수 있는것들을 전부 갱신을 한뒤에

모든 도시들을 찾아다니면서 가장 작은 값을 구해주면 되는 것이다.

import sys
import heapq
input = sys.stdin.readline


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



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



pay_list =[INF for _ in range(N+1)]
node_list = []
visited = [False]*(N+1)
heapq.heappush(node_list,(0,1))
pay_list[1] = 0
result = 0
while node_list:
    cur_pay,cur_node = heapq.heappop(node_list)
    if pay_list[cur_node] < cur_pay or visited[cur_node]:
        continue
    visited[cur_node] = True
    result += cur_pay
    for next_node in graph[cur_node]:
        if pay_list[next_node] > graph[cur_node][next_node] and not visited[next_node]:
            pay_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(pay_list[next_node],next_node))


conquer_pay = (N-2)*(T+(N-2)*T)//2
result += conquer_pay
print(result)

이 풀이는 위에서 말한것처럼 어차피 conquer는 등차수열로 균등하게 증가하기 때문에, conquer를 배제하고,

우리가 일반적으로 구하는 프림알고리즘을 이용해서 문제를 해결한다.

그리고 난뒤에 등차수열의 합의 공식을 이용해서, conquer_pay를 구한뒤 결과값에 더해주면 된다.

import sys


class Node():
    def __init__(self,key=None,data=None):
        self.key = key
        self.data = data
        self.depth = 0
        self.child_node = {}
class Trie():
    def __init__(self):
        self.rootnode = Node()
    
    def insert(self,arr):
        cur_node = self.rootnode

        for node in arr:
            if node not in cur_node.child_node.keys():
                cur_node.child_node[node] = Node(node)
            cur_node.child_node[node].depth = cur_node.depth+1
            cur_node = cur_node.child_node[node]
        cur_node.data = 'END'
    def print(self):
        cur_node = self.rootnode
        stack = sorted(cur_node.child_node.values(),key= lambda x : (x.key),reverse=True)
        result = ''
        while stack:
            node = stack.pop()

            current_depth = node.depth
            result = '--'*(current_depth-1)+node.key
            print(result)
            if node.data == None:
                child_node = sorted(node.child_node.values(),key= lambda x : (x.key),reverse=True)
                stack.extend(child_node)

input = sys.stdin.readline
N = int(input())
trie = Trie()
for _ in range(N):
    N,*arr = input().split()
    N = int(N)
    trie.insert(arr)

trie.print()

트라이 알고리즘 문제를  처음 풀어본 유형이었다.

그래서 풀기 어려웠고, trie를 공부한 뒤에 풀 수 있었다.

이 문제는 전형적인 트라이 알고리즘으로, 현재 노드의 자식노드들을 저장하고,

자식노드에 해당 값이 있으면, 넘어가고, 없는 새로운 값이면 child_node에 Node를 추가시켜주면 된다.

그리고 print 또한 반복문적으로 끝까지 반복해서 들어가면 된다.

그런 방식으로 풀어주면 되는 문제였고, 좀 더 간단하게 풀어주기 위해, 해당 depth를 저장시켜주었다.

from collections import deque

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    dp_dict = {N:-1}
    stack = [N]
    cnt = 0
    while stack:
        new_stack = []
        for num in stack:
            if not (num%3 or dp_dict.get(num//3)):
                dp_dict[num//3] = num
                new_stack.append(num//3)
            if not (num%2 or dp_dict.get(num//2)):
                dp_dict[num//2] = num
                new_stack.append(num//2)
            
            if not dp_dict.get(num-1) and num>1:
                dp_dict[num-1] = num
                new_stack.append(num-1)
        cnt += 1
        if 1 in new_stack:
            break
        stack = new_stack[:]
    result = []

    find_num = 1
    print(cnt)
    while True:
        result.append(find_num)
        find_num = dp_dict[find_num]
        if find_num == -1:
            break
    result.reverse()
    print(*result)

방식은 간단하다. 나눠지고, 해당 값이 최초로 방문했을때에만 new_stack에 넣어주고,

그때의 위치정보를 dictionary에 저장시켜준다.

그리고 1에 도착하면 역으로 추적해가면서 최초의 숫자가 나올때까지 반복을 해주면 되는 문제이다.

import sys
import heapq
input = sys.stdin.readline

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

init_list.sort()
result = [0 for _ in range(100001)]
INF = float('inf')
for start_time,end_time in init_list:
    if heap:
        if heap[0] <= start_time:
            heapq.heappop(heap)
        heapq.heappush(heap,end_time)
    else:
        heapq.heappush(heap,end_time)
total_cnt = len(heap)
print(total_cnt)

check_number = []
min_chair_number = []
for start_time,end_time in init_list:
    if check_number:
        while check_number and check_number[0][0] <= start_time:
            _,pop_idx = heapq.heappop(check_number)
            heapq.heappush(min_chair_number,pop_idx)
        if not min_chair_number:
            idx = len(check_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
        else:
            idx = heapq.heappop(min_chair_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
    else:
        result[0] += 1
        heapq.heappush(check_number,(end_time,0))
print(*result[:total_cnt])

첫번째 풀이는 다음과 같다.

먼저 전체 컴퓨터의 개수를 구해준다.

check_number에는 끝시간과 사용하고 있는 사람이 있는 컴퓨터의 index를 넣어준다.

그리고 시작시간보다. 끝나는시간이 먼저 끝났을때에는 그걸 min_chair_number에 빈 컴퓨터의 index를 넣어준다.

만약 이미 들어차있는 check_number에 현재 시작시간보다 작은것이 하나도 없다하면,

먼저 min_chair_number가 있으면 min_chair_number에서 빈자리를 꺼내서 check_number에 넣어준다.

그리고 min_chair_number가 없으면 현재 주어진 컴퓨터에서 전부 자리가 꽉찬거이므로, 새 컴퓨터를 발급해주고,

그 값을 check_number에 넣어주면 된다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
time_list = []
for i in range(N):
    start_time,end_time = map(int,input().split())
    heapq.heappush(time_list,(start_time,i))
    heapq.heappush(time_list,(end_time,i))
isSeatperson = [-1]*N
seat_info = []
com_idx = 0
min_com_list = []

while time_list:
    _,person_number = heapq.heappop(time_list)

    if isSeatperson[person_number] == -1:
        if min_com_list:
            isSeatperson[person_number] = heapq.heappop(min_com_list)
        else:
            isSeatperson[person_number] = com_idx
            com_idx += 1
    else:
        heapq.heappush(min_com_list,isSeatperson[person_number])
        seat_info.append(isSeatperson[person_number])


max_com = max(seat_info)+1

result = [0]*max_com

for com_number in seat_info:
    result[com_number] += 1

print(max_com)
print(*result)

좀 더 깔끔한 풀이는 다음과 같다.

시작시간과 끝시간을 두개로 나눠서 time_list에 넣어준다.

그리고 난뒤에 하나씩 꺼내주면서, 만약에 이 사람이 앉을때 즉 start_time일때에는 min_com_list에 남은게 있으면,

하나를 출력해서 배정을 시켜준다.

그리고 그게 아니면 새로운 컴을 발급시켜주고, 그때의 idx를 증가시켜준다.

그리고 퇴실할때 나간 사람의 자리를 넣어준다.

그리고 마지막으로 그 사람이 앉았던 자리 정보를 seat_info에 저장시켜준다.

이렇게 전체 자리수를 구하고, seat_info를 통해 각 자리마다 앉았던 사람들의 정보를 저장시켜준다.

import heapq
import sys
input = sys.stdin.readline
def find_parents(X):
    if make_set[X] ==X:
        return X
    else:
        make_set[X] = find_parents(make_set[X])
        return make_set[X]


def union(a,b):
    X = find_parents(a)
    Y = find_parents(b)
    if X == Y:
        return False
    if rank[X]< rank[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if rank[X] == rank[Y]:
        rank[X] += 1
    return True


P,W = map(int,input().split())

c,v = map(int,input().split())

weight_list = [list(map(int,input().split())) for _ in range(W)]
make_set = [i for i in range(P)]
weight_list.sort(key=lambda x : x[2])
rank = [1 for _ in range(P)]
result = float('inf')
while find_parents(c) != find_parents(v):
    node_a,node_b,pay = weight_list.pop()
    if union(node_a,node_b):
        result = pay


print(result)

  이 문제를 푸는 방식은 다음과 같다. 최대 길이를 구하고, 그때의 최소 너비를 구하면 되는 것이다.

그러므로 크루스칼 알고리즘대로 푸는 대신 가장 앞에서부터 pop을 하던것에서 가장 뒤에서부터 pop을 하면서

그 두 노드가 같은 집합이 아닐때 합쳐주면서 그때의 pay를 result에 저장해주면 되는 방식으로 풀면 된다.

import sys
import heapq


input = sys.stdin.readline

P,W = map(int,input().split())

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

graph = [{} for i in range(P)]

for _ in range(W):
    x,y,pay = map(int,input().split())
    graph[x][y] = max(graph[x].get(y,0),pay)
    graph[y][x] = max(graph[y].get(x,0),pay)


max_width_list = [0]*P
max_width_list[start_city] = float('inf')

node_list = []

heapq.heappush(node_list,(-float('inf'),start_city))


while node_list:
    maximun_width,cur_node  = heapq.heappop(node_list)
    maximun_width = -maximun_width
    for next_node in graph[cur_node]:
        
        cur_maximun_width = min(graph[cur_node][next_node],maximun_width)

        if cur_maximun_width > max_width_list[next_node]:
            max_width_list[next_node] = cur_maximun_width
            heapq.heappush(node_list,(-max_width_list[next_node],next_node))


print(max_width_list[end_city])

프림 알고리즘으로 푸는 방식은 거의 동일하다. 대신 cur_maximun_width가 다른데, 현재의 간선의 너비와 지금까지 최대 간선의 너비와 비교해서

그 중 더 큰 값을 비교에 쓴다.

이 점만 주의하고, 최소힙이 아니라 최대힙을 사용하면 해당 문제를 풀 수 있다.