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

카데인 알고리즘이란?카데인 알고리즘은 연속 부분 배열의 최대 합을 구하는 효율적인 방법으로, 컴퓨터 과학과 알고리즘 문제 해결에서 자주 사용됩니다. 이 알고리즘은 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/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 { ..

Queue의 개념큐는 선입선출(FIFO) 방식으로 작동하는 자료구조입니다. 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 큐의 두 가지 주요 연산은 다음과 같습니다: - 삽입(Enqueue): 요소를 큐의 끝에 추가 - 삭제(Dequeue): 큐의 앞에서 요소를 제거 Java에서는 Queue 인터페이스를 통해 큐를 지원하며, 다양한 구현체가 제공됩니다.Queue 인터페이스와 주요 메서드add(E e): 큐의 끝에 요소를 추가 (삽입에 성공하면 true 반환, 실패하면 예외 발생) offer(E e): 큐의 끝에 요소를 추가 (삽입에 성공하면 true 반환, 실패하면 false 반환) remove(): 큐의 앞에서 요소를 제거하고 반환 (큐가 비어있으면 예외 발생) poll(): 큐의 앞에서 요소를 제거..