본문 바로가기

DP4

LCA2 LCA2 백준 11438번 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 2.1.1 LCA 트리에서 공통의 조상을 찾는 것은 LCA 알고리즘을 통해 해결할 수 있다. LCA 알고리즘은 다음과 같은 과정으로 두 노드 간의 공통 조상을 찾는다. 1. 두 노드의 깊이가 다르면 같아질 때까지 한쪽 노드의 깊이를 올린다. 2. 두 노드가 같아질때까지 깊이를 한칸씩 올린다. 다음과 같은 트리가 주어졌.. 2023. 2. 20.
내리막-길 내리막-길 백준 1520번 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 d(i, j) 를 시작점에서부터 i, j로 갈 수 있는 경우의 수를 의미한다고 하자. 그러면 다음과 같은 점화식이 성립한다. d(i, j) = SUM(d(i - 1, j), d(i, j + 1), d(i + 1, j), d(i, j - 1)) (단, (i,j)의 높이보다 높을 경우만 더해준다.) 따라서 도착점을 (i, j)라고 할 .. 2022. 9. 8.
Word Break Word Break leetcode 139번 문제. https://leetcode.com/problems/word-break/ Word Break - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictiona.. 2022. 6. 19.
Longest Increasing Path in a Matrix Longest Increasing Path in a Matrix LeetCode 329번 문제. https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ Longest Increasing Path in a Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 Given an m x n integers matrix, return the length of the longest incr.. 2022. 6. 13.

티스토리툴바