문제 ❓ 문제 풀기 : https://www.acmicpc.net/problem/1092문제 분석 ⏳문제에서 중요한 두가지가 있다.무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구해야 한다.위 두가지 조건을 만족하기 위해서는 가장 큰 무게제한을 가진 크레인이 가장 큰 무게의 상자를 옮겨야한다.최적해를 구하는 그리디알고리즘 문제임을 알 수 있다.(그리디 알고리즘에 대해서는 나중에 작성하겠다.)문제 해설 💡arrayList를 활용하기로 한 후 크레인과 상자를 각각 craneList와 boxList에 값을 할당했다.가장 큰 무게를 옮길 수 있는 크레인이 가장 무거운 상자를 옮기게 하기 위해 각각의 List를 오름차순으로 정렬했다.첫번째 크레인(가장 ..

문제문제 풀기 :   https://www.acmicpc.net/problem/1932해설1. numTriengle과 dp 이중배열에 공간복잡도를 효율적으로 사용하기 위해 각각의 층에 맞는 배열크기를 할당한다.2. numTriengle배열에 입력 받은 값을 할당한다.3. dp배열에는 현재 인덱스까지 최대값을 넣어준다.3-1. 이때 고려해야할 사항은 가장 왼쪽에 위치한 인덱스인 경우 오직 자신의 오른쪽 위 대각선에서만 값이 온다.3-2. 가장 오른쪽에 위치한 인덱스인 경우 오직 자신의 왼쪽 위 대각선에서만 값이 온다.3-3. 중간에 위치한 인덱스의 경우 왼쪽 위 대각선과 오른쪽 위 대각선의 값을 비교하여 더 큰값을 받는다.4. 마지막 줄에 위치한 dp배열의 값들중 최대값을 max변수에 할당한 후 출력한다...

문제문제 풀기 :  https://www.acmicpc.net/problem/18353해설1. 잘못된 접근처음 문제를 보고서 남아있는 병사들의 전투력의 총합이 가장 크게 만드는 문제로 이해했다.문제 이해 자체가 잘못되어 올바른 코드를 산출하지 못했다.와중에 올바른 코드를 산출하지 못해 혼자 계속 고민하다 코드를 다 지우고 문제를 다시 읽었다...import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String args[]) throws IOException { ..

문제못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다.다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다.12의 약수인 1, 2, 3, 4, 6, 12 중에서 2와 3이 소인수이다.1은 못생긴 수라고 가정한다.따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다.이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라.예를 들어 11번째 못생긴 수는 15이다.입ㆍ출력 조건입력 조건첫째 줄에 n이 입력된다.(1 출력 조건n번째 못생긴 수를 출력한다.입ㆍ출력 예시입력 예시10출력 예시12해설접근방법문제를 처음 봤을때는 그냥 모든 경우의 2,3,5를 다 곱해서 배열에 넣고 정렬해야겠다는 생각을 했다.하지만 1000번째..

서론다이나믹 프로그래밍이라는 알고리즘 기법에 대해서 깊이있게 공부하던 중에 문제를 많이 풀어보면 습득하기 좋을거 같아. 이것이 취업을 위한 코딩 테스트다 with 파이썬-(동빈나)에 나오는 다이나믹 프로그래밍 문제를 풀어보며 공부하면 좋을거 같아 문제를 풀어보고 푸는 과정을 기록으로 남긴다.문제 문제 풀기 : https://www.acmicpc.net/problem/1904해설접근 방식기존에 풀었던 다이나믹 프로그래밍과 약간은 다른 방식이라 생소하게 다가와 처음에는 많이 당황스러웠다.계속 입력예시를 직접 손으로 적으며 고민하던중에 "작업이 끝나는 시간"에 집중해야 한다는 것을 깨달았다.1. 먼저 입력을 받는다.2. 입력 받은 값을 기준으로 각각의 작업이 시작하는 날과 끝나는 날을 같이 저장한다.3. 버블..

문제n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 촐력하는 프로그램을 작성하세요.입ㆍ출력 조건입력 조건첫재 줄에 테스트 케이스 T가 입력됩니다. (1 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 있습니다. (1 출력 조건테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스틑 줄 바꿈을 이용해 구분합니다.입ㆍ출..

서론최근 다이나믹 프로그래밍이라는 알고리즘 기법에 대해서 깊이있게 공부하던 중에 문제를 많이 풀어보면 습득하기 좋을거 같아. 이것이 취업을 위한 코딩 테스트다 with 파이썬-(동빈나)에 나오는 다이나믹 프로그래밍 문제를 풀어보며 공부하면 좋을거 같아 문제를 풀어보고 푸는 과정을 기록으로 남긴다.1. 1로 만들기 문제문제 접근 전략동적 프로그래밍의 전형적인 최적화 문제각 숫자마다 최소 연산 횟수를 저장하는 메모이제이션 필요Bottom-Up 방식으로 접근 가능모든 가능한 연산 중 최소 연산 선택중복 계산 방지를 위한 DP 테이블 활용연산의 우선순위와 최적성 보장문제 해결 핵심 로직1을 뺀 경우와 2, 3으로 나눈 경우 비교각 숫자별 최소 연산 횟수 누적 계산import java.io.BufferedRead..

1. 다이나믹 프로그래밍의 정의다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작고 단순한 하위 문제들로 분해하여 해결하는 알고리즘 설계 기법입니다. 이 접근 방식은 문제의 최적해를 찾기 위해 중간 결과를 저장하고 재사용함으로써 계산 효율성을 높입니다.2. 다이나믹 프로그래밍이 적용 가능한 문제다이나믹 프로그래밍은 다음과 같은 특징을 가진 문제에 효과적으로 적용됩니다:최적 부분 구조(Optimal Substructure): 문제의 최적해가 하위 문제들의 최적해로부터 구성될 수 있는 경우중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제들이 반복적으로 해결되는 경우대표적인 예시: 피보나치 수열, 최단 경로, 배낭 문제, LCS(Longest ..