For Programmer

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모르면 한없이 어렵고 알고나면 한없이 쉬운 문제이다. 그냥 간단하다 1. 리스트안에 x,y,z 좌표와 현재의 점 번호를 함께 튜플로 저장한다. 2. 각각의 점을 기준으로 정렬한 후 3. 바로 붙어있는 점이 가장 짧은 거리이므로 그 거리를 계산해서 4. 다시 리스트 하나에 해당 두점과 거리를 모두 넣어준다. 5. 그 후 거리를 기준으로 오름차순 정렬 후 크루스칼 해주..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 간단히 크루스칼 코드만 알고 있다면 쉽게 해결할 수 있다. 조건 2가지 ( 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. , 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.) 가 있는데 그 중 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 의 조건을 생각하기가 까다로울 수 있다. 문제를 잘보..

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 간단한 유니온 파인드 문제이다. 풀이 방식은 유니온 파인드 돌린 후 1. 만약 두 노드가 이미 연결되어 있다면 연산횟수 + 1 2. 모든 연산이 끝난 후 연결되지 않은 연결요소 집합이 몇개 존재하는지 set함수를 통해 체킹 import sys input = sys.stdin.readline def find(x): if x != parent[x]: parent[x] = find(parent[x])..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 보통의 유니온파인드 문제와 비슷하게 크게 어려운 문제는 아니다. 하지만 파이썬 사용자라면 1. 경로 압축 2. 유니온 바이 랭크 두가지 모두 최적화 해주어야 통과할 수 있다. import sys input = sys.stdin.readline # 1. 경로 압축 def find(x): if x != parent[x]: parent[x] = find(parent[x]) # 재귀를 돌며 해당 부..

해당 문제는 풀이가 많이 존재할 수 있으나 크게 생각나는 2가지 방법으로 구현했다. 1. 최대힙을 이용한 다익스트라 2. 중량을 내림차순 정렬 후 유니온 파인드 1. 최대힙을 이용한 다익스트라 import heapq import sys input = sys.stdin.readline def dijkstra(v1, v2): global ans q = [] heapq.heappush(q, (-(1

해당 문제는 BFS로 풀 수도 있고 모든 거리를 1로 두고 다익스트라를 돌려도 된다. 1. BFS 풀이 import sys from collections import deque input = sys.stdin.readline N, M, K, X = map(int, input().split()) # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호 graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) ans = [] visited = [False] * (N + 1) def bfs(start): queue = deque([[start, 0]]) visited[star..

무지성 다익 돌리면 된다. 단, 다익을 구하기 위해 아주 큰값으로 초기화를 해줄텐데 다익스트라를 시작하기 전 0,0의 거리 비용을 초기에 입력받은 배열의 0,0에 있는 좌표의 값으로 시작하는 것이 아주 중요하다. import heapq import sys input = sys.stdin.readline def dijkstra(): q = [] heapq.heappush(q, (arr[0][0], 0, 0)) distance[0][0] = arr[0][0] while q: cost, r, c = heapq.heappop(q) if r == N - 1 and c == N - 1: return cost if cost > distance[r][c]: continue for i in range(4): nr = r..

간단한 DP문제이다. 약간 웰노운이라 쉽게 풀 수 있었다. 최대 2개만 고를 수 있기 때문에 실버이지 않나 생각해본다. 이 중반복문을 돌면서 한개 뽑았을때 2개뽑았을 때 나눠서 생각하면 쉽게 풀 수 있다. import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N, M = map(int, input().split()) w_size = list(map(int, input().split())) dp = [1