본문 바로가기

프로그래밍/백준

 (146)
백준 11779 최소비용 구하기 2 - 파이썬 문제. 풀이. 다익스트라를 이용해서 풀면된다. 다익스트라로 최소거리를 구하면서 이동경로를 기록해주고 최소거리와 이동경로를 출력해주면 된다. 소스코드. import sys import heapq def dijkstra(start): dp[start][0] = 0 dp[start][1] = [start] heap = [] heapq.heappush(heap, [0, start]) while heap: now_weigth, now = heapq.heappop(heap) if dp[now][0] < now_weigth: continue for next, weight in graph[now]: next_weight = weight + now_weigth if next_weight < dp[next][0]: dp[..
백준 13913 숨바꼭질 4 - 파이썬 문제. 풀이. 이 문제도 경로를 저장하는 배열을 저장해서 연산마다 경로를 추가했는데 이 방법으로하면 메모리가 초과된다. 이 방법은 이동한 경로를 나타내는 배열을 하나 선언한뒤 어디로 이동했는지 표시하고 목표지에 도착했을때, 해당 위치에서부터 어떻게 이동했는지를 체크하면된다. 소스코드. import sys from collections import deque def path(x): arr = [] temp = x for i in range(matrix[x] + 1): arr.append(temp) temp = move[temp] arr.reverse() print(*arr) def BFS(n): queue = deque() queue.append(n) while queue: x = queue.popleft..
백준 9252 LCS 2 - 파이썬 문제. 풀이. 공통의 부분 수열을 찾고 LCS를 출력하는 문제이다. DP 배열을 선언해서 각 위치마다 최대 몇개의 공통이 되는지 체크를 하고 경로들을 저장해서 출력한다. 소스코드. import sys input = sys.stdin.readline a = input().strip() b = input().strip() dp = [[[0, []] for i in range(len(a) + 1)] for j in range(len(b) + 1 )] for i in range(len(a)): for j in range(len(b)): if a[i] == b[j]: dp[j+1][i+1][0] = dp[j][i][0] + 1 dp[j+1][i+1][1] = dp[j][i][1] + [b[j]] else: dp[..
백준 14003 가장 긴 증가하는 부분 수열 5 - 파이썬 문제. 풀이. O(NlogN)로 문제를 풀어야한다. https://turret1234.tistory.com/151 백준 12015 가장 긴 증가하는 부분 수열2 - 파이썬 문제. 풀이. 이분 탐색을 이용하여 dp배열의 최댓값과 비교하여 큰 값이면 오른쪽에, 낮은 값이면 dp배열의 값에서 이분 탐색을 이용하여 해당 값이 들어갈 위치를 결정하여 dp 배열에 넣고 dp 배 turret1234.tistory.com 기본적인 풀이방법은 위 링크와 같다. 여기서 경로를 저장한 배열을 만들고 연산마다 경로를 추가하여주면된다. 소스코드. import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) numbers = [0] + ..
백준 14002 가장 긴 증가하는 부분 수열 4 - 파이썬 문제. 풀이. https://turret1234.tistory.com/138 백준 11053 - 가장 긴 증가하는 부분 수열 문제. 풀이. 첫번째 위치부터 수열의 길이의 최댓값을 저장하고 자기 자신보다 작은 숫자들 중 가장 큰 길이를 자기 위치에 넣고 +1을 하고 dp의 최댓값을 출력하면 된다. 소스코드. import sys A = int turret1234.tistory.com 기본적으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 위의 링크와 같다. 여기서 추가적으로 경로를 담아야하는데. 경로를 담는 dp배열을 추가하여 연산마다 경로를 담아준다. 소스코드. import sys input = sys.stdin.readline n = int(input()) numbers = list(map(int..
백준 12852 1로 만들기 2 - 파이썬 문제. 풀이. 최솟값과 경로를 담는 dp 배열을 생성해서 연산마다 최솟값과 경로를 배열에 담아준다. 그리고 경로를 뒤집어서 출력하면 된다. 소스코드. import sys input = sys.stdin.readline n = int(input()) dp = [[0, []] for _ in range(n + 1)] dp[1][0] = 0 # 최소값 dp[1][1] = [1] # 경로를 담는 리스트 for i in range(2, n+1): # x -1 dp[i][0] = dp[i-1][0] + 1 dp[i][1] = dp[i-1][1] + [i] # x // 3 if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]: dp[i][0] = dp[i//3][0] + 1 dp[i][..
백준 1644 소수의 연속합 - 파이썬 문제. 풀이. 에라토스테네스의 체를 이용하여 소수를 구하고 부분합 을 이용하여 소스코드를 작성하면 된다. https://turret1234.tistory.com/141 백준 1912 연속합 - 파이썬 문제. 풀이. dp[0]에 arr[0]의 값을 넣어준 뒤 연속으로 더하는게 더 큰 숫자면 더한 값을 dp에 넣어주고 더하지 않고 새로운 숫자를 넣어주는게 값이 더 크다면 그 값을 dp에 넣어주는 방식으로 계속 turret1234.tistory.com https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 수학..
백준 11066 파일 합치기 - 파이썬 문제. 풀이. 정답률이 50퍼가 넘던데 문제가 너무 어려웠다. 크누스 최적화라는 알고리즘을 사용해서 풀었다. 크누스 최적화는 특수한 조건일 때 시간 복잡도를 O(n^3)에 O(n^2)까지 줄일 수 있는 알고리즘이다. 우선 크누스 최적화 알고리즘을 적용할려면 다음과 같은 조건을 만족해야한다. 사각 부등식: C[a][c] + C[b][d]

티스토리툴바