본문 바로가기

알고리즘18

[그래프] 백준 1261 알고스팟 최소한의 벽을 뚫고 목적지까지 도달해야한다. >>> 최소한의 벽 2022. 3. 16.
[그래프] 백준 1197 최소 스패닝 트리(kruskal/prim) 최소 스패닝 트리란? 모든 정점을 포함하며/ 사이클이 만들어지지 않고/ 최소한의 가중치 값의 합 을 만족하는 트리이다. 1. kruskal 알고리즘 - 그리디 - 가중치가 가장 작은 값부터 선택하면서 - 사이클이 만들어진다면 버리고 - 반복 import sys V, E = map(int, sys.stdin.readline().split()) root = [i for i in range(V+1)] # root[i]는 i의 루트 정점을 의미 edges=[] for _ in range(E): u, v, w = map(int, sys.stdin.readline().split()) edges.append([w, u, v]) edges.sort() # 오름차순 def find_root(x): if x!=root[x.. 2022. 3. 14.
[그래프] 백준 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net import sys from collections import deque N,M = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)] dy = [-1, 1, 0, 0] dx = [0, 0, 1, -1] def bfs(): v.. 2022. 3. 13.
[dp] 백준 12865 평범한 배낭/ 14728 벼락치기 두 문제 모두 "평범한 배낭" 문제와 같다. 변수명만 다르게 하면 될 뿐, 코드까지 똑같은 문제이다. import sys N, T = map(int, sys.stdin.readline().split()) time_score = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dp = [[0]*(T+1) for _ in range(N+1)] for y in range(1, N+1): time = time_score[y-1][0] score = time_score[y-1][1] for x in range(1, T+1): if time 2022. 3. 13.
[dp/dfs] 백준 15691번 루트가 있는 트리에서 각 노드 이하로 몇 개의 노드가 있는지 카운트해야한다. 처음 문제를 봤을때 쉽게 생각했는데 시간초과/메모리초과 문제로 꽤나 오래 걸렸다. dfs를(재귀를) 이렇게 활용할 수 있구나 깨달아서 좋은 문제 import sys sys.setrecursionlimit(10**5) N, R, Q = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N+1)] dp = [0 for _ in range(N+1)] for _ in range(N-1): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) def dfs(x): dp[x]=.. 2022. 3. 12.
[dp] 17069번 백준 파이프 옮기기2 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 한 지점(y,x)에 가로로 도달했다면 - 가로로 (y, x+1)에 도달할 수 있고, 대각선으로 (y+1, x+1)에 도달할 수 있다. 세로와 대각선도 마찬가지다. (y,x)에 세로로 도달 -> 세로로 (y+1, x)에 도달, 대각선으로 (y+1, x+1)에 도달 (y,x)에 대각선으로 도달 -> 가로로 (y, x+1)에 도달, 세로로 (y+1, x)에 도달, 대각선으로 (.. 2022. 3. 10.

티스토리툴바