코생코사

https://www.acmicpc.net/problem/1309 DP를 사용 맨 위의 두 칸을 세 가지 경우로 나눈다- 공백: 두 칸에 아무도 없음- 좌: 왼쪽 칸에 사자 있음- 우: 오른쪽 칸에 사자 있음 만약 n이 1이라면위처럼 세 가지 경우가 있습니다  n이 2인 경우를 보겠습니다 그런데 아래 칸(파란색)의 경우의 수는n=1일 때의 경우의 수와 같습니다  즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다. dp 점화식으로 풀게 된다면# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른..

https://www.acmicpc.net/problem/5639 입력, 재귀를 위한 limit 제한import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**9) 1. 트리 만들어서 postorder 하기2. 트리 없이 리스트로 postorder 하기 3. 인덱스를 이용해서 postorder하기   1. 트리 만들어서 postorder 하기 트리 클래스 생성class Node: def __init__(self, node): self.node = node self.left = None self.right = None # 추가 함수 def plus(self, res): # res: 들어오는 값 ..

전위 순회(preorder): A -> B -> C중위 순회(inorder): B -> A -> C후위 순회(postorder): B -> C -> A  https://www.acmicpc.net/problem/1991 재귀 함수를 이용  입력 및 트리 만들기import sysinput = sys.stdin.readlinen = int(input())tree = {}for _ in range(n): a, b, c = input().split() tree[a] = [b,c] # 0번 인덱스는 왼쪽 1번 인덱스는 오른쪽 print(tree){'A': ['B', 'C'], 'B': ['D', '.'], 'C': ['E', 'F'], 'E': ['.', '.'], 'F': ['.', 'G'], ..

https://www.acmicpc.net/problem/11725 각 노드마다 연결되어있는 노드를 저장하는 이차원 리스트를 만든다각 노드가 방문 여부를 저장하는 리스트를 만든다부모 노드를 저장하기 위한 parents라는 리스트를 만든다 -> DFS import sysinput= sys.stdin.readlinedef dfs(node): st = [node] while st: v = st.pop() for n in graph[v]: if visited[n] == False: parents[n] = v visited[n] = True st.append(n)n = i..

https://www.acmicpc.net/problem/1504 방법은노드 1 -> 노드 v1 -> 노드 v2 -> 노드 n노드 1 -> 노드 v2 -> 노드 v1 -> 노드 n두 가지 중 최소 경로를 구하고, 만약 INF 보다 크거나 같다면 -1을 출력하면 되는 문제였습니다.  일단 이 문제를 플로이드 워셜로 푸려고 했습니다(이유는.. 800 ** 3을 1억번보다 더 적게 나온다고 잘못 계산해서..)import sysinput = sys.stdin.readlineINF = int(1e9)n, e = map(int, input().split())graph = [[INF]*(n+1) for _ in range(n+1)]for i in range(1, n+1): graph[i][i] = 0 fo..

https://www.acmicpc.net/problem/1956 저는 노드가 400개이기 때문에400 ^ 3이 1억번보다 적어 플로이드 워셜 알고리즘을 사용해야겠다고 생각했습니다 import sysinput = sys.stdin.readlineINF = int(1e9)v, e = map(int, input().split())graph = [[INF]*(v+1) for _ in range(v+1)]for i in range(1, v+1): graph[i][i] = 0 for _ in range(e): a, b, c = map(int, input().split()) graph[a][b] = c # 단방향 for k in range(1, v+1): for i in range(..

https://www.acmicpc.net/problem/11660처음에 dp의 누적합을 두고 풀어야 겠다는 생각을 했습니다.2024.09.28 - [분류 전체보기] - [Python] 누적합 알고리즘 [Python] 누적합 알고리즘[1,2,3,4,5,6,7,8,9,10] 리스트가 있다고 했을 때3번 인덱스부터 마지막 인덱스의 합을 구한다고 하자(인덱스는 1부터 시작)arr = [1,2,3,4,5,6,7,8,9,10]start = 3end = len(arr)print(sum(arr[start-1:end]))   그렇다면 이dogfoot1.tistory.com  1. 첫 번째 방법각 행마다 누적합을 구하고, x1행부터 x2행까지 반복문을 돌면서 값을 더한다.  누적합 리스트 sum_graph를 구하게 되면..

https://www.acmicpc.net/problem/1149 참고https://m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료)문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문제 중 ...blog.naver.com dp를 사용하기 위해 점화식을 만든다현재 집의 R, G, B를 선택했을 때의 최솟값을 선택한다R이 0번 인덱스, G가 1번 인덱스, B가 2번 인덱스일 때현재 -1 집의 인덱스가 겹치지 않도록 점화식을 만든다 현재집에 R을 선택했을 때 -> R 선택 비용 + 현재-1집의 G, B 중 최소 비용dp[i][0] = lists[i][..

https://www.acmicpc.net/problem/9205저는 dfs를 사용하였습니다.DFS를 사용하는 이유: 거리가 되는 모든 방향을 탐색해야 하기 때문https://www.acmicpc.net/board/view/86660 x와 y의 값이 1000(20X50) 이하이면 갈 수 있다1000보다 크면 갈 수 없다  입력 받기from sys import stdint = int(stdin.readline())result = []for _ in range(t): n = int(stdin.readline()) # 편의점 개수 home_x, home_y = map(int, stdin.readline().split()) store = [] for _ in range(n): ..

+https://www.acmicpc.net/problem/1351 먼저 저는 다이나믹 프로그래밍을 사용해야겠다고 생각했습니다예를 들어 n=7, p=2, q=3이 나왔을 때 다이나믹 프로그래밍- 재귀 함수 + 메모제이션을 이용(탑다운 방식)- 반복문을 이용(보텀업 방식) 먼저 반복문을 이용하여 코드를 구현했습니다.from sys import stdinn, p, q = map(int, stdin.readline().split())dp = [0] * (n+1)dp[0] = 1for i in range(1, n+1): dp[i] = dp[i//p] + dp[i//q] print(dp[n])하지만 n이 최대 10의 12승이기 때문에 메모리 초과가 났습니다. 그래서 저는 메모리를 줄이기 위해 n//p와..