목록DP (34)
어흥
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 1. 주의할 점 - DFS가 아닌 점화식을 통해 문제를 해결한다 2. 구현 - DP[][]를 통해 각 지점까지 거쳐간 숫자들의 합의 최대값을 저장한다 - 해당 지점에서 왼쪽 아래와 오른쪽 아래로 갔을 때 각 지점의 최대값을 갱신한다 - 가장 아랫변에 위치한 DP[][]값의 최대값을 반환한다 import java.util.*; import java.io.*; class Solution { static int dp[][]; pu..
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1837?language=java 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr 1. 주의할 점 - BFS/DFS로 시도하면 TLE 혹은 '틀렸습니다'라는 문구가 출력된다 - DP로 접근한다 2. 구현 - 단순하게 그래프 문제라고 생각하고 DFS/BFS로 접근했다가 TLE와 '틀렸습니다'의 연속..(다만 이때, 1개의 채점에 여러개의 TC가 존재하여 1개라도 TLE 또는 메모리초과 발생시 틀렸습니다로 나타난다는 사람들의 의견이 존..
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42898?language=cpp# 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 1. 주의할 점 - 1열과 1행 전부가 도달 가능하지 않을 수 있다 - 연산 이후 값을 저장할 때 MOD를 활용한다 2. 구현 - Arr[M][N] 배열에 (M,N)까지 도착 가능한 방법의 수를 MOD로 나눈 값을 저장한다 - Set을 이용하여 웅덩이의 위치를 저장한다 - [1,1]에 시작하여 1열과 1행에 1을 ..
문제 링크: https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 주의할 점 - 메모아이즈(DP) + 비트마스크를 통해 해결한다 - 순회 만족 조건은? 2. 구현 - 비용에 대한 정보를 Arr[][] 배열에 담는다 - Check[Cur][Val] 배열을 통해 Cur 도시에 도착할 때 방문했던 도시번호들의 합을 Val이라고 한다. 이 때, 비용의 최소값을 저장한다 - 순회가 된다면, 어떤 Node에서 시작해도..
문제 링크: www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 주의할 점 - LCA 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 수행되는 알고리즘을 이해하도록 한다 2. 구현 - 모든 변에 대해 입력받은 후, havePar[] 배열을 통해 트리의 Root를 찾는다 - DFS() 함수를 통해 각 Node의 트리에서 높이를 구한다 - Make_tree() 함수를 통해 N번째 Node의 2^i번째 높..
문제 링크: www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 주의할 점 - 두 포인터 or DP를 이용하여 해결한다 2. 구현 - 모든 수가 3만 이하의 자연수다 → i~j까지의 합이 Target번호라면, j이후의 Arr[] 배열의 원소를 더할 필요가 없다(더하면 초과하므로) 2-1) 두 포인터 - L,R를 모두 인덱스 번호 0부터 시작한다. Sum을 통해 L과 R 사이에 존재하는 모든 원소의 합을 저장한다 - ..
문제 링크: www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 1. 주의할 점 - 최단거리가 지름길을 안탈수도 있는 경우가 있다 2. 구현 - Dist[]를 통해 0부터 각 지점까지의 길이를 미리 저장한다 - 지름길에 대한 정보를 받을 때, 지름길의 도착지점이 목표지점을 넘어가거나, 사실상 지름길이 아닌 경우는 제외한다 - 0부터 도착지점까지 Dist[] 배열을 갱신하며, 만약 해당 지점에 지름길이 있는 경우, 지름길의 반대편까지의 거리를 기존 길이..