'DP' 태그의 글 목록

[BOJ] 2169 로봇 조종하기 - Java

2024.04.16

✨ DP https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 📍 고려해야할 사항 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만 위쪽으로는 이동 X 한 번 탐사한 지역은 재탐사 X (1, 1)에서 (N, M)까지 갈 때 탐사한 지역들의 가치의 최댓값 구하기 🕹️ 풀이 방법 우선 0번째 행에 있는 값들은 왼쪽에서부터 이동하면서 합쳐진 값을 기록한다. 이미 탐색한 길은 다시 방문할 수 없으므로 경로가 왼쪽으로부터 이동..

알고리즘/🗂️ 정리

DP - Knapsack (배낭문제)

2024.02.05

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🕹️ Knapsack 알고리즘 과정 DP 문제 중 하나로, 배낭의 크기 k와 n개의 물건의 무게(w)와 가치(v)가 주어졌을 때, 가방에 물건을 k에 넘지 않도록 넣고 최대 가치의 합을 구하는 문제이다. ex) 배낭의 크기는 k이고, 5개의 물건의 무게와 가치가 다음과 같이 주어졌을 때, 최대 가치의 합을 구하기 물건 1 : w =..

알고리즘/🗂️ 정리

LIS (최장증가부분수열)

2023.12.07

LIS(Longest Increasing Subsequence)는 원소가 n개인 배열에서 일부 원소를 골라내어 만든 부분 수열 중에서 모든 원소들이 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열이다. 예시를 들어보자. A = {10, 20, 10, 30, 20, 50}인 수열에서 원소가 증가하는 부분 수열은 {10, 20}, {20, 30, 50}, {10, 30, 50} 등이 있는데, 그 중 길이가 최대인 부분 수열은 길이가 4인 {10, 20, 30, 50}이다. 대표 문제는 아래와 같다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오..

[BOJ] 2169 로봇 조종하기 - Java

DP - Knapsack (배낭문제)

LIS (최장증가부분수열)

티스토리툴바