최대점수 구하기(Dynamic Programing)

HTML 삽입 미리보기할 수 없는 소스 코드 package dynamic; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /** * 최대점수 구하기(냅색 알고리즘) */ public class Dynamic5 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.r..

• format_list_bulleted 알고리즘
• · 2024. 4. 23.
• textsms

동전교환(Dynamic Programing)

HTML 삽입 미리보기할 수 없는 소스 코드 package dynamic; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /** * 동전교환(냅색 알고리즘) * N 제한이 적으면 DFS로 풀이 가능하지만 N제한이 커지면 동적계획법으로 풀이하여야 함 */ public class Dynamic4 { static int[] dy; // 최소 개수를 계속해서 기록 static int solution(int[] coin, int totalMoney) { Arrays.fill(dy, Integ..

• format_list_bulleted 알고리즘
• · 2024. 4. 23.
• textsms

가장 높은 탑 쌓기(Dynamic Programing)

HTML 삽입 미리보기할 수 없는 소스 코드 package dynamic; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; /** * 가장 높은 탑 쌓기(LIS 응용) */ public class Dynamic3 { // 벽돌 클래스 static class Brick implements Comparable { int area; // 넓이 int height; // 높이 int weigh..

• format_list_bulleted 알고리즘
• · 2024. 4. 23.
• textsms

최대 부분 증가수열(Dynamic Programing)

HTML 삽입 미리보기할 수 없는 소스 코드 package dynamic; import javax.imageio.metadata.IIOMetadataFormatImpl; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 최대 부분 증가 수열 */ public class Dynamic2 { static int[] dy; static int solution(int[] arr) { int answer = 0; dy = new int[arr.length]; dy[0] = 1; for (int i = 1; i < arr.leng..

• format_list_bulleted 알고리즘
• · 2024. 4. 23.
• textsms

계단 오르기(Dynamic Programing)

HTML 삽입 미리보기할 수 없는 소스 동적계획법이란? 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 동적 프로그래밍 방법 큰 문제를 작은 문제로 쪼개어 푼다. 정답을 구한 작은 문제를 어딘가에 메모해 놓고 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결괏값을 이용한다. (메모이제이션 사용) 메모이제이션이란? 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에..

• format_list_bulleted 알고리즘
• · 2024. 4. 23.
• textsms