one Book a Day

벽을 뚫는다 = 이동시 비용이 든다. = 가중치 있는 그래프 가중치가 0 과 1로 이루어진 그래프 탐색으로 맨앞 요소에 가중치 누적요소 cnt를 넣어 가중치가 낮은 길로 target을 찾아가는 bfs를 그리면 된다. heap을 이용해 낮은가중치탐색을 하는방법과 deque을 이용해 가중치가0인 노드이동에 대해 appendleft를 해주는 방법도 있다. 여튼 먼저 탐색해준다는게 핵심. import sys input = sys.stdin.readline from heapq import heappush, heappop m, n = map(int, input().split()) dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] maze = [] visited = [[0] * m for i in ..

다익스트라의 정석.(단방향) import sys input = sys.stdin.readline from collections import defaultdict from heapq import heappush,heappop def dijkstra(start): global min_dists heap = [] min_dists = [float('INF')]*(V+1) min_dists[start] = 0 heappush(heap,[min_dists[start],start]) while heap: cur_dists,cur_node = heappop(heap) if cur_dists > min_dists[cur_node]: continue for next_dists,next_node in graph[cur_n..

골드2여서 시간 메모리 빡빡할까봐 쫄았는데 그냥 무지성 코드로 통과.. 슬라이스 정렬,중앙값찾기.,count로 출력숫자 제어. import sys input = sys.stdin.readline for test in range(int(input())): M = int(input()) seqs = [] for i in range(M//10+1): seqs.extend(list(map(int,input().split()))) print(M//2+1) print(seqs[0], end=" ") if M !=1: cnt=1 for i in range(2,M,2): print(sorted(seqs[:i+1])[(i+1)//2], end=" ") cnt+=1 if cnt==10: print() cnt=0 else:..

최소거리 배열 다 구해서 전부 더해준 다음 합 미니멈인 방번호 출력 다익스트라로 간단하게 풀었다. import sys input = sys.stdin.readline from heapq import heappop, heappush from collections import defaultdict # 각 친구들 위치에서 모든 방에 대해 최소거리 배열 출력. def dijkstra(start): global dp_dists dp_dists = [float('inf')] * (N + 1) heap = [] dp_dists[start] = 0 heappush(heap, [dp_dists[start], start]) while heap: cur_dist, cur_node = heappop(heap) if dp_di..

출발지, 도착지에 따라. BFS로 거리구하면 끝. import sys input = sys.stdin.readline from collections import defaultdict,deque def Distance(a,b): queue = deque() queue.append(a) visited = [False]*(N+1) visited[a] = True target_dist = [0]*(N+1) while queue: v = queue.popleft() if v==b: print(target_dist[v]) return for next,dist in graph[v]: if not visited[next]: queue.append(next) visited[next] = True target_dist[n..

문자열 뒤집은 key찾아서 key길이와 중앙값 출력. import sys input = sys.stdin.readline N = int(input()) files = [input().rstrip() for _ in range(N)] for i in range(N-1): for j in range(i,N): if files[i][::-1] == files[j]: print(len(files[i]), files[i][len(files[i])//2]) exit()

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다. 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달. 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다. 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다. 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다. 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 ..

실질적으로 별찍기(프렉탈 분할정복) 을 접한건 두번째다 첫번째는 감이 잘 안왔는데 이제는 슬슬 감이온다. 1. 입력값 2. 최소단위로 분할 3. 최소문제 해결 4. 더 큰문제 정복 5. 조합 정복시 그림이 잘 안그려질때는 실질적으로 뭐가 몇개 늘어났는지. 최소단위가 몇개 늘어나는지 잘 살펴보면 된다. 그리고 최소단위를 반복, 순회하면서 반복 덧셈, 곱셈을통해 확장시켜나가면 된다. 이 문제같은 경우 가장 작은 삼각형이 다음 차수에 밑에 2개 더 붙고 그다음은 그 큰 3개의 삼각형이 밑에 2개씩 더붙는다. 즉 이전 그림의 두배씩 아래쪽 배열에 추가된다고 생각하면 된다. 또 처음 들어갔던 배열도 " " 빈칸을 추가해줘야하는데 얼마나 추가해주냐면 실질적으로 늘어나는 3칸을 세어 3칸 -> 6칸 -> 12칸 즉 ..

최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..

처음에 그냥 matrix에 넣었다가 시간초과나고 합연산은 한번에 하는걸로 코드 수정. 통과 import sys input = sys.stdin.readline for test in range(int(input())): N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] ans = [[] for _ in range(2)] for i in range(N): ans[0].append(sum(matrix[i])) for i in range(N): ans[1].append(sum(matrix[m][i] for m in range(N))) for _ in range(M): r1,c1,r2,c2,v = ma..