Algorithm/Baekjoon52 [백준] 알고스팟 / 1261번 / 파이썬 / Python / Dijkstra 알고리즘 💡solutions ) 💬 단순 다익스트라(Dijkstra) 알고리즘으로 해결한 문제, 해당 문제에서 노드의 비용에 해당하는 것은 벽을 부순 횟수(cnt) 💬 BFS로도 방문 중복으로 하여 해결할 수 있는 문제 🎫code ) import sys import heapq def dijkstra(): heap = [] heapq.heappush(heap, [0, 0, 0]) # 시작점 visit[0][0] = 1 while heap: cnt, x, y = heapq.heappop(heap) # 벽 부순 횟수가 최소인 경우가 나옴 for k in range(4): nx, ny = x + dx[k], y + dy[k] if x == n - 1 and y == m - 1: # 종료조건 print(cnt) break.. 2020. 12. 6. [백준] 최소비용 구하기 / 1916번 / 파이썬 / python 💡solutions ) 💬 dijkstra(다익스트라) 알고리즘 유형의 기본 문제 🎫code ) import sys import heapq def dijkstra(n, s, e): dist = [INF] * (n + 1) dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c heapq.heappush(heap, [c, n]) return dist[e] input = sys.stdin.readline n = int(input()) m = int(input()) adj = [[] fo.. 2020. 12. 5. [백준] 숨바꼭질 / 1697번 / 파이썬 / python 🎫code ) from collections import deque # 너비 우선 탐색 n, k = map(int, input().split(' ')) arr = [0] * (k + 1) max_v = 100001 visit = [0] * max_v q = deque([n]) da = [-1, 1, 2] while q: a = q.popleft() if a == k: print(visit[a]) break for i in range(3): if i == 2: na = a * da[i] else: na = a + da[i] # a가 기존, na는 다시 돌아왔을 때 비교 if (0 2020. 12. 4. [백준] 1로 만들기 / 1463번 / 파이썬 / Python 🎫code ) n = int(input()) dp = [0 for _ in range(n + 1)] for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 print(dp, '0') if i % 2 == 0 and dp[i] > dp[i // 2] + 1: dp[i] = dp[i // 2] + 1 print(dp, '1') if i % 3 == 0 and dp[i] > dp[i // 3] + 1: dp[i] = dp[i // 3] + 1 print(dp, '2') print(dp[n]) 📌 description ) 문제출처 : www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진.. 2020. 12. 3. [백준] 효율적인 해킹 / 1325번 / 파이썬 / Python 🎫code ) import sys from collections import deque input = sys.stdin.readline def bfs(lst): q = deque(lst) while q: x = q.popleft() visit[x] = 1 for i in adj[x]: if not visit[i]: q.append(i) visit[i] = 1 return visit.count(1) n, m = map(int, input().split(' ')) adj = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split(' ')) adj[b].append(a) res = [] max_v = 0 for i in range.. 2020. 12. 1. [백준] 차이를 최대로 / 10819번 / 파이썬 / Python 💡solutions ) 💬 n값이 크지 않으니까, permutations 써서 모든 경우를 찾는 브루트포스 알고리즘 구현 🎫code ) import sys from itertools import permutations as permu input = sys.stdin.readline n = int(input()) arr = list(map(int, input().rstrip().split(' '))) max_v = 0 for p in permu(arr, n): sum = 0 n_list = list(p) for i in range(1, len(n_list)): tmp = abs(n_list[i - 1] - n_list[i]) sum += tmp max_v = max(max_v, sum) print(max_.. 2020. 11. 30. 이전 1 2 3 4 5 6 7 ··· 9 다음
