다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 복잡한 문제를 여러 하위 문제로 나누어 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방법입니다. DP는 주로 중복된 하위 문제가 존재하는 경우에 사용됩니다. 같은 하위 문제를 여러 번 계산하지 않고, 이미 계산된 결과를 저장해두고 필요할 때 재사용하는 것이 핵심입니다.다이나믹 프로그래밍의 특징최적 부분 구조: 문제의 최적 해가 그 하위 문제들의 최적 해로 구성됩니다.중복된 하위 문제: 동일한 하위 문제를 반복해서 계산하지 않고, 한 번 계산한 값을 저장해서 재사용합니다. 다이나믹 프로그래밍의 접근 방식 - Java 구현 상향식 접근 (Bottom-Up) public class FibonacciDP { public static int fibona..

문제https://www.acmicpc.net/problem/14501문제풀이이 문제는 주어진 기간 동안 여러 상담 일정을 조정하여 얻을 수 있는 최대 수익을 계산하는 문제입니다. 각 상담은 특정 기간이 소요되며, 그 기간 동안 다른 상담을 진행할 수 없습니다. 목표는 상담 일정을 최적화하여 가능한 최대 수익을 얻는 것입니다. 동적 프로그래밍(DP)을 사용하여 각 날에 얻을 수 있는 최대 수익을 이전 날의 최대 수익과 비교하여 점진적으로 계산합니다.특정 날 i 에 상담을 수행할 수 있는 경우 상담을 진행하여 얻는 수익을 고려하여 해당 상담이 끝나는 날(i + t[i])에 최대 수익을 갱신소스코드import java.io.BufferedReader;import java.io.InputStreamReader..

카데인 알고리즘이란?카데인 알고리즘은 연속 부분 배열의 최대 합을 구하는 효율적인 방법으로, 컴퓨터 과학과 알고리즘 문제 해결에서 자주 사용됩니다. 이 알고리즘은 O(n) 시간 복잡도를 가지며, 동적 계획법(Dynamic Programming) 접근법을 사용합니다.카데인 알고리즘의 원리카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색합니다. 알고리즘은 두 가지 값을 유지합니다.현재까지의 최대 합 (max_so_far) : 지금까지 발견한 최대 부분 배열의 합현재 위치에서 끝나는 최대 합 (max_ending_here) : 현재 위치에서 끝나는 부분 배열 중 최대 합알고리즘 단계1. max_so_far와 max_ending_here를 배열의 첫 번째 요소로 초기화합..

문제https://www.acmicpc.net/problem/1912문제풀이nowMax : 현재 위치까지의 최대 부분 배열 합을 저장overMax : 지금까지 발견된 전체 최대 부분 배열 합을 저장초기값으로 첫 번째 요소를 설정배열의 두 번째 요소부터 순회하며, 현재 요소를 시작으로 새로운 부분 배열의 합(arr[i])과 이전 부분 배열에 현재 요소를 추가한 합(nowMax + arr[i]) 중 더 큰 값을 nowMax에 저장overMax는 nowMax와 비교하여 더 큰 값을 저장하여 전체 최대 부분 배열 합을 유지소스코드import java.io.*;import java.util.StringTokenizer;public class _1912 { public static void main(Strin..

문제https://www.acmicpc.net/problem/1254문제풀이입력된 문자가 처음부터 팰린드롬인지 확인한다.아닐 경우 반복하여 검사하며 팰린드롬 구조로 만드는 작업을 해야 한다.앞부분 문자를 추출하여 뒤집고 뒷부분에 맞춘 후 팰린드롬인지 체크한다.팰린드롬이 될 때까지 추출하는 앞 문자 개수를 늘려간다.소스코드import java.io.*;public class _1254 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Buffe..

문제https://www.acmicpc.net/problem/3019문제풀이7가지 모양의 블록이 주어지고 입력한 블록이 90도, 180도, 270도 회전하여 모양을 변경하는 경우를 생각한다.1,3,4 블록 : 2가지 / 2블록 : 1가지 / 5,6,7블록 : 4가지의 모양으로 변경할 수 있다.문제에서 언급된 대로 행은 고려하지 않고 블록이 떨어질 바닥면 높낮이만 생각한다.블록의 아랫면만 체크하면 되기에 String[][] blocks에 각 회전하여 닿는 부분을 "0", "1"로 표현하였다.ex) ㄴ: 000, ㄱ: 110, ㅜ: 101, ㅓ: 10블록의 모양별로 전체 열에 대해 순회를 하며 블록의 아래모양과 바닥이 같은지 비교(빈칸 발생)하며 카운트한다.소스코드import java.io.BufferedR..

문제https://www.acmicpc.net/problem/28702문제풀이문제에서 원하는 출력값은 3개의 입력값 다음에 올 문자열이다.문제의 요구대로 3번의 문자열을 입력할수 있도록 반복문을 만든다.입력받은 문자가 숫자 정규식 "-?\\d+(\\.\\d+)?" 에 해당되는지 체크하여 숫자인 경우순번에 맞게 값을 더해 4번째의 값을 구한다. ex) 1번째인 경우 4번째까지 +3이 필요하다.i는 3부터 감소하며 반복을하고 n(4번째값)은 s(입력문자열) + i 가 된다.n(4번째값)을 구했으면 FizzBuzz 조건에 해당되는 문구를 출력하고 반복문을 종료한다.소스코드import java.io.*;public class _28702 { public static void main(String[] arg..

문제https://www.acmicpc.net/problem/30802문제풀이N : 참가자 수sizeArr : 티셔츠 사이즈별 신청자의 수T : 티셔츠 묶음 단위 갯수 P : 펜의 묶음별 갯수cnt : 주문할 티셔츠 총 묶음 수티셔츠 사이즈 종류의 수만큼 반복하여 사이즈별 총 필요한 묶음수를 구한다.cnt += sizeArr[i] / T;// 티셔츠는 남아도되기에 묶음 단위로 나눴을때 나머지 발생시 한 묶음 추가한다.cnt = sizeArr[i] % T > 0 ? cnt + 1 : cnt; 펜의 묶음 수 (N / P) 와 한 자루 단위 주문할 개수 (N % P) 출력소스코드import java.io.*;import java.util.StringTokenizer;public class _30802 { ..