목록전체 글 (154)
Dazzling 개발 노트
문제 가로의 길이가 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..
반복문 사용하다가 자꾸 헷갈려서 확실히 정리하고 넘어가기 위해 작성한다. break : 루프 종료 : 제어문의 제어를 벗어나기 위해 사용 continue : 다음 문장을 실행하지 않고 루프의 처음으로 돌아감 return : 루프와 루프를 감싸고 있던 메소드까지 종료 : 값을 반환
문제 풀이/후기 재귀가 아닌 반복문을 이용하여 파라메트릭 서치로 풀이 코드 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(" "..
[백준] 16918 - 봄버맨 (Java) 문제 https://www.acmicpc.net/problem/16918 풀이/후기 처음 생각보다 막히지 않고 잘 풀었는데, 조금씩 정답 출력과 다른 부분이 있어 문제를 찾느라 시간이 좀 걸렸다. bombFunc()에서 if (arr[cx][cy] != 2) 부분을 해주지 않아 자꾸 폭탄이 있는데 터지지 않는(?) 현상이 발생했다. 디버깅으로 열심히 찾아내서 뿌듯함...! 그리고 자바로 제출한 사람들과 비교하니 제출 시간이 좀 걸리길래 StringBuilder로 sysout을 바꾸니 확실히 시간이 확 줄었다!!! 이것 또한 뿌듯! 코드 package GraphTheory; import java.io.*; public class Problem16918 { stat..
[백준] 2740 - 행렬 곱셈 (Java) 문제 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 풀이/후기 행렬 곱셈 개념이 오랜만이라 다시 찾아보고 풀이하는데, 개념 자체는 어렵지 않았다. 근데 왜 이게 분할정복 문제인지는 의문이었음,, 이 문제를 풀면서 그렇게 느낀 사람이 많은 것 같은데 분할정복으로 풀려면 슈트라센 알고리즘을 이용해야 한다고 한다. .........ㅎ 일단 소스코드 참고용으로만 이해하고 넘어갔다. 코드 ..