DP12

• 

  백준 알고리즘 2157번: 여행 문제 정보https://www.acmicpc.net/problem/2157  문제 파악문제 조건1 2 1 (N: 도시의 수, M: 방문할 최대 도시의 수, K: 개설된 항공로의 개수) 문제 내용1번 도시부터 N번 도시까지 최대 M개의 도시를 방문하고, 가중치(기내식의 점수)의 합의 최대를 출력해야 한다  풀이생각했던 내용처음에 DFS로 문제를 풀이해 보았다 (시간 초과)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { private static int M.. 알고리즘/Java 2024. 6. 8.

• 

  백준 알고리즘 2410번: 2의 멱수의 합 문제 정보https://www.acmicpc.net/problem/2410  문제 파악문제 조건1 답이 커질 수 있으므로 1,000,000,000 으로 나눈 나머지를 출력할 것 문제 내용어떤 자연수 N을 입력했을 때, N을 2의 멱수의 합으로 나타내는 경우의 수를 구하여라여기서 2의 멱수란 2^k 로 표현되는 자연수를 의미 (1, 2, 4, 8, 16 ...)  풀이생각했던 내용 /** * n=1 * 1 * * n=2 * 1 1 * 2 * * n=3 * 1 1 1 * 2 1 * * n=4 * 1 1 1 1 .. 알고리즘/Java 2024. 6. 7.

• 

  백준 알고리즘 2631번: 줄 세우기 문제 정보https://www.acmicpc.net/problem/2631  문제 파악문제 조건2  문제 내용번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수 구하기  풀이생각했던 내용어떤 식으로 이 문제를 풀어가야 할까 고민을 많이 했지만, 생각이 쉽게 떠오르지 않아 다른 분들의 풀이를 참고하게 되었다문제의 설명에 직접 수를 정렬하는 것처럼 되어 있어서 헷갈릴 가능성이 매우 높지만, 막상 풀고 나니 설명 안에 뜻이 담겨있다고 느꼈다 예제 )3 7 5 2 6 1 4예제에서는 해당 수들 가운데 4명의 아이들을 골라 정렬시킨다첫번째로 4번, 두번째로 7번, 세번째로 1번, 네번째로 2번 공통점은 다음과 같은데, 위 4명의 아이들을 제외하고 아이들의 줄을 확인해 보면3 7 5 2 6 1 4 3, 5, 6.. 알고리즘/Java 2024. 5. 30.

• 

  백준 알고리즘 12865번: 평범한 배낭 / 배낭 문제(Knapsack Problem) 문제 정보 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 핵심 문제 이해 총 N개의 물건 각 물건은 무게(W), 가치(V)를 가짐 -> 해당 물건을 가지고 가면, V만큼 즐길 수 있음 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고다닐 수 있음 이를 통해 배낭에 넣을 수 있는 물건들의 가치 합의 최대를 구하는 문제 조건 물품 수(N) 0 Question 여기서 왜 남은 가방으로 담을 수 있는 최대 가치가 dp[i-1][~~] 인 것일까? 그건.. 알고리즘/Java 2024. 4. 19.

• 

  백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열 문제 정보 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 핵심 DP 배열의 정의를 어떻게 내리느냐가 중요했다고 생각한다 매번 DP 관련 문제를 풀면서 느끼는 것이지만, 코드는 비슷한데 생각을 만들어 내느냐가 가장 중요한 것 같다 이 문제같은 경우에는 dp 배열을 다음과 같이 정의하였다 dp[i] : i번째 수를 선택했을 때, 가질 수 있는 최대의 길이 현재 위치를 무조건 택한다는 가정이 있기때문에, 1. 이전 dp 배열을 보면서 해.. 알고리즘/Java 2024. 3. 20.