Dazzling 개발 노트

[백준] 1463 - 1로 만들기 (Java) 문제 https://www.acmicpc.net/problem/1463 풀이/후기 이코테에서 풀었던 1로 만들기와 거의 똑같은 문제였다. 차이점은 5 연산식이 없다는 것. 문제 복습을 위해 점화식을 직접 만들어봤는데, 몇 시간 전에 비슷한 문제를 풀었는데도 한 번에 잘 떠오르지 않았다. 복습이 중요할 것 같다...^^ https://da-zzling.tistory.com/35 코드 package DynamicProgramming; import java.io.*; public class Problem1463 { static int[] d = new int[1000000+1]; public static void main(String[] args) throws I..

문제 https://www.acmicpc.net/problem/11727 풀이/후기 이코테에서 풀었던 바닥 공사 문제와 완전히 동일하다 https://da-zzling.tistory.com/37 코드 package DynamicProgramming; import java.io.*; public class Problem11727 { static int[] d = new int[1000 + 1]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); d..

[백준] 11726 - 2 x N 타일링 (Java) 문제 https://www.acmicpc.net/problem/11726 풀이/후기 이코테에서 DP 유형의 문제를 풀다가, 타일링 문제가 대표적인 유형이라길래 백준에서 비슷한 문제를 풀어봄 총 3가지 경우가 나온다고 생각했는데, 1x2타일이 3번과 같은 경우가 되어 결국 2가지 경우가 나옴 이 부분은 유튜브 풀이 보고 알게된 점인데 역시 글로 여러번 읽는 것보다 영상으로 강의한번씩 듣는게 효과가 큰 것 같다@ 코드 package DynamicProgramming; import java.io.*; public class Problem11726 { static int[] d = new int[1000+1]; public static void main(St..

문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있음 이 얇은 바닥을 1 * 2덮개, 2 * 1덮개, 2 * 2덮개 세 가지의 덮개를 이용하여 채우고자 함 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성 예를 들어 2*3 크기의 바닥을 채우는 경우의 수는 5 * 출력 시 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력 (입력예시) 3 (출력예시) 5 풀이/후기 (다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라고 하는데, 단지 결과값이 굉장히 커질 수 있기 때문임) 다이나믹 프로그래밍의 기초 예제에서 필수적인 타일링 문제 유형임 코드 package ThisIsCT; import java.io.BufferedReader; impo..

문제 개미 전사가 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다 메뚜기 마을에는 여러 개의 식량창고가 있는데 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량차고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 식량창고가 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량차고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성 (예시입력)..

문제 정수 X가 주어질 때 정수 X에서 사용할 수 있는 연산은 아래와 같이 4가지임 - X가 5로 나누어 떨어지면 5로 나눈다 - X가 3으로 나누어 떨어지면 3으로 나눈다 - X가 2로 나누어 떨어지면 2로 나눈다 - X에서 1을 뺀다 정수 X가 주어질 때 연산 4개를 적절히 이용해 1을 만들려고 할때, 연산을 사용하는 횟수의 최솟값을 츨력 풀이/후기 다이나믹 프로그래밍 /보텀업 방식을 이용하여 풀이 아주 전형적인 다이나믹 프로그래밍 문제 코드 package ThisIsCT; import java.io.*; public class ch08_02_master { //Ch.08 다이나믹 프로그래밍 Dynamic Programming DP // 1로 만들기 static int[] d = new int[300..

문제 풀이/후기 재귀가 아닌 반복문을 이용하여 파라메트릭 서치로 풀이 코드 package ThisIsCT; import java.io.*; import java.util.Arrays; public class ch07_03 { //ch.07 이진 탐색 //떡볶이 떡 만들기 //절단기의 높이가 큰 수이므로, 바로 이진 탐색 떠올려야 함!!(순차 탐색 이용 시 시간 초과) /* * [파라메트릭 서치 Parametric Search] * : 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 사용 * : 이진탐색을 이용해 풀이함. * : 파라메트릭 서치에선 이진탐색을 재귀적으로 표현하지 않고 반복문을 이용해 구현함. * * (문제풀이) * 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정 * 현재..

문제 부품찾기 문제 풀이/후기 코드 package ThisIsCT; import java.io.*; import java.util.Arrays; public class ch07_02 { //ch.07 이진 탐색 //부품 찾기 static int[] arrN; static int[] arrM; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); arrN = new int[N]; String[] input = br.readLine().split(" "..