본문 바로가기

백준

 (104)
백준 11066 파일 합치기 - 파이썬 문제. 풀이. 정답률이 50퍼가 넘던데 문제가 너무 어려웠다. 크누스 최적화라는 알고리즘을 사용해서 풀었다. 크누스 최적화는 특수한 조건일 때 시간 복잡도를 O(n^3)에 O(n^2)까지 줄일 수 있는 알고리즘이다. 우선 크누스 최적화 알고리즘을 적용할려면 다음과 같은 조건을 만족해야한다. 사각 부등식: C[a][c] + C[b][d]
백준 9370 미확인 도착지 - 파이썬 문제. 풀이. 출발지 s, 경유지 g, h 도착지 d 라고 한다면 두가지 경우의 수 가존재한다. s -> g -> h -> d s -> h -> g -> d 이 2가지를 체크하여 s -> d의 최단경로 거리랑 같다면 정답지에 추가한다. 소스코드. import sys import heapq def dijkstra(start): dp = [100000000 for i in range(n+1)] dp[start] = 0 heap = [] heapq.heappush(heap, [0, start]) while heap: now_weight, now = heapq.heappop(heap) if dp[now] < now_weight: continue for next, weight in graph[now]: next_..
백준 2407 조합 - 파이썬 문제. 풀이. nCk 를 계산하는 방법은 n! // m! * (n-m)! 이다. 소스코드. import sys from math import factorial input = sys.stdin.readline n, k = map(int, input().split()) result = factorial(n) // (factorial(k) * factorial(n-k)) print(result)
백준 15654 N과 M(5) - 파이썬 문제. 풀이. 파이썬의 내장 라이브러리 itertools의 permutation으로 순열을 구한 뒤 정렬 후 출력하면 된다. 소스코드. import sys from itertools import permutations input = sys.stdin.readline n, m = map(int, input().split()) numbers = list(map(int, input().split())) result = list(permutations(numbers, m)) result.sort() for i in result: for j in i: print(j, end=' ') print()
백준 11725 트리의 부모 찾기 - 파이썬 문제. 풀이. 주어진 입력들을 양방향으로 연결하고 1에서 BFS를 실행하여 각 노드의 부모를 찾으면 된다. 소스코드. import sys from collections import deque def BFS(): answer = [0] * n visited = [False] * (n+1) queue = deque([1]) while queue: parent = queue.popleft() for i in tree[parent]: if not visited[i]: answer[i-1] = parent queue.append(i) visited[i] = True return answer[1:] input = sys.stdin.readline n = int(input()) tree = [[] for i in r..
백준 10217 KCM Travel - 파이썬 문제. 풀이. 우선 처음에는 다익스트라를 이용하여 풀이를 했다. 처음에는 답이 틀렸다. 그 이유는 비용으로 비교했을때 거리와, 거리로 비교했을때 최소거리 2가지 경우를 모두 생각해야 했었다. 그래서 두 가지 경우를 나눠서 제출을 했는데 이번에는 메모리 초과로 틀렸다. 우선 기존 소스코드를 첨부하겠다. 기존 소스코드. import sys import heapq def dijkstra(start): global dp visited = [False for i in range(N+1)] dp_time[start] = [0, 0] dp_cost[start] = [0, 0] heap = [] heapq.heappush(heap, [0, start, 0]) #[비용, 위치, 시간] while heap: now_cos..
백준 1956 운동 - 파이썬 문제. 풀이. 플로이드-와샬 알고리즘을 통해 최단 거리를 구한 뒤 자기 자신에게 돌아오는 값 중 최솟값을 출력한다. 사이클이 없으면 -1 소스코드. import sys input = sys.stdin.readline def floyd_whashall(): # k = 경유지 for k in range(1, V+1): # i = 출발지 for i in range(1, V+1): # j = 목적지 for j in range(1, V+1): if graph[i][j] > graph[i][k] + graph[k][j]: graph[i][j] = graph[i][k] + graph[k][j] V, E = map(int, input().split()) inf = float('inf') graph = [[inf for..
파이썬 2629 양팔저울 - 백준 문제. 풀이. 양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게 차이이다. 예를들어 1,3,7 무게의 추가 있다면 잴 수 있는 경우는 1, 2, 3, 4, 6, 7, 8, 10, 11의 무게를 잴 수 있다. 여기서 2, 4, 6 같은 경우에는 |왼쪽 저울 - 오른쪽 저울|의 값이다. 즉 dp[i][j] = i번쨰 추를 놓으려고 할때 현재의 무게차이 j 이다. 소스코드. import sys def scale(weight, n, now, left, right): new = abs(left - right) # possible에 현재 무게차이가 들어 있지 않다면 추가 if new not in possible: possible.append(new) if now == n: return # 방문하는 dp가 이..

티스토리툴바