728x90 알고리즘/[python] 백준 BOJ328 [python] 백준 11438 LCA 2 https://www.acmicpc.net/problem/11438 문제 해결최소 공통 조상을 찾는 알고리즘을 LCA (Lowest common ancestor)이라 한다.트리 구조에서 level을 가지고 층의 차이를 좁힌 다음 하나씩 동시에 level을 올려 parent를 확인한 다음 동시에 같은 parent가 될 때 까지 학인하는 알고리즘 코드이다. CODE import sysinput = sys.stdin.readlinemax_depth = 10000log = 21n = int(input())graph = [[] for _ in range(n+1)]for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) gra.. 2024. 6. 6. [python] 백준 4811 알약 https://www.acmicpc.net/problem/4811 문제 해결DP를 이용해야하는 문제라는 것은 쉽게 알 수 있다.그런데 DP를 어떻게 활용할지는 생각보다 어렵다.힌트는 알약이 $n$개가 있으면 H가 $n$번 W가 $n$번 써진다는 사실이다.그래서 dp[i][j]를 H가 $i$번, W가 $j$번 썼다는 것으로 정의한다.j가 1~n일 때 dp[0][j]는 1이다.그리고 dp[i][j] += dp[i-1][j] + dp[i][j-1]이다. CODEimport sysinput = sys.stdin.readlinedef DP(n): dp = [[0 for _ in range(n+1)] for _ in range(n+1)] for i in range(1,n+1): dp[0][i.. 2024. 6. 2. [python] 백준 16565 N 포커 https://www.acmicpc.net/problem/16565 문제 해결DP를 이용해 n개중 m개를 뽑았는데 그중 k개 종류가 나올 경우의 수를 dp[m][k]라고 정의한다.dp[0][0]은 1로 정의그러면 $ dp[i][j] = \sum_{k=0}^{3} \binom{4}{k} \times dp[i-k][j-1]$ 이후 포카드가 나올 수 있는 경우의 수를 계산하기 위해idx (포카드 나오는 개수)$ ans += \binom{13}{idx} * dp[n-4*idx][13-idx]$ CODEimport sysinput = sys.stdin.readlineimport mathmod = 10007def combination(n, r): return math.factorial(n)//(math... 2024. 5. 23. [python] 20188 등산 마니아 https://www.acmicpc.net/problem/20188 문제 해결트리와 DFS를 사용해야한다는 것은 쉽게 알 수 있지만 어떻게 활용할지 매우 어려운 문제https://youtu.be/AQzKDzQqIRE다음 동영상을 봐도 어렵다... CODEimport sysinput = sys.stdin.readlinefrom collections import deque, defaultdictsys.setrecursionlimit(10**8)def dfs(cur, parent): global ans for child in graph[cur]: if child != parent: dfs(child, cur) dp[cur] += dp[ch.. 2024. 5. 22. 이전 1 2 3 4 5 6 ··· 82 다음 728x90
