다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 복잡한 문제를 여러 하위 문제로 나누어 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방법입니다. 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/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 { ..

문제https://www.acmicpc.net/problem/2659문제풀이1 이상 9 이하의 숫자 4개가 시계 방향으로 입력되므로 범위는 1111~9999가 된다.'시계수'란 숫자들의 시작점을 시계방향으로 바꿔가며 나온 수 중에 가장 작은 수를 뜻한다.시계방향이라는 규칙이 큐를 활용해도 된다고 판단하였다.ex) 1 2 2 1 -> 2 2 1 1 -> 2 1 1 2 -> 1 1 1 2와 같이 (큐의 길이 - 1) 반복하며 최소 숫자(시계수)를 구하는 메서드(findClockNum)를 생성했다.예제와 같이 2 1 1 2 가 입력된다면 시계수는 1122가 되며1111 ~ 1122까지의 숫자 중 0을 포함한 숫자와 1121(이 숫자의 시계수는 1112이다)과 같이 시계수가 아닌 수 를 제외하여 카운트를 센다...

브루트포스 알고리즘이란?브루트포스 알고리즘은 가능한 모든 경우를 탐색하여 문제를 해결하는 방법입니다. "완전 탐색"이라고도 불리며, 무차별 대입 방식으로 모든 후보를 검사합니다. 이는 가장 기본적인 알고리즘 기법 중 하나입니다.브루트포스 알고리즘의 특징단순성: 구현이 간단하고 이해하기 쉬움완전성: 해가 존재한다면 반드시 찾아냄비효율성: 경우의 수가 많을 경우 시간이 많이 소요됨브루트포스 알고리즘의 장점쉬운 구현: 복잡한 논리나 데이터 구조가 필요 없으며, 직접적인 접근 방식으로 쉽게 구현할 수 있습니다.명확한 해답 보장: 모든 경우의 수를 확인하기 때문에 해답이 존재하면 반드시 찾아냅니다.브루트포스 알고리즘의 단점비효율성: 입력 크기가 커질수록 탐색해야 할 경우의 수가 급격히 증가하여, 시간 복잡도가 매..