알고리즘

처음에 자신있게 점화식을 f(N) = f(N-1) - fibo(N) 으로 세웠지만, 틀렸습니다.. ㅎㅎ 조건 - N자리 숫자의 계단수 개수를 출력하라. 풀이 - N자리 숫자의 각 value(0~9)가 가지는 계단수를 저장하고, => dp[N][value] 메모제이션 한 값을 활용한다. (개인적으로는 dp 구조를 생각하기 어려웠음) - 계단수를 만들기 위해서는, value가 0일 때는 1 / 9일 때는 8 / 이 외에는 value-1, value+1 두가지로 뻗칠 수 있다. https://st-lab.tistory.com/134 [백준] 10844번 : 쉬운 계단 수 - JAVA [자바] www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,..

조건 - 계단을 1칸 or 2칸씩 오를 수 있다. - 연속 3개의 계단은 오를 수 없다. - 마지막 계단은 무조건 밟아야 한다. 풀이 1) 마지막 계단은 무조건 밟아야 하므로 dp[N] = ? + ary[N] 이어야 한다. 2) 최대 2칸의 계단을 오를 수 있으며(한 칸 건너뛰기), 연속 3개의 계단은 오를 수 없으므로 다음과 같은 점화식을 도출할 수 있다. N-2 까지의 값 vs N-3까지의 값에 직전값(ary[N-1]), 연속되지 않는 위치의 값에 대해서만 비교를 해주어야 한다. dp[N] = Math.max(solve(N-2), solve(N-3) + ary[N-1]) + ary[N] https://st-lab.tistory.com/132 [백준] 2579번 : 계단 오르기 - JAVA [자바] w..

1번 - 배열을 계산하는데 ArrayIndexOut이 안되려고 1열에 '0'을 넣은 N*(N+1) 배열을 만드려다가 시간이 오래 걸린 문제.. (결국 그냥 간단히 index 체크 구문 써서 해결했다..) → 0행을 복사하고, Math.max(dp[i-1][j-1], dp[i-1][j]) 로 접근했다. (마지막 N-1행에서 max 값을 찾기 위한 검사가 필요하다) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] ary; //n개의 수열을 입력받을 공간 static In..

1번 - 머릿속으로 'dp[] 배열, 메모제이션을 어떻게 할까?' 고민만 하다가 아래 자료를 참고하며 풀었다. - 연속합 중 최댓값을 찾는 문제이므로, dp[i] = Math.max(dp[i-1]+ary[i], ary[i]) // i까지의 연속합 vs i 값 => i-1까지의 연속합이 음수이면, i부터 연속합을 구하는 방식 의 점화식을 세울 수 있다. https://st-lab.tistory.com/140 [백준] 1912번 : 연속합 - JAVA [자바] www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정..

1번 → 노트에 적으며 규칙을 찾아보면 다음과 같은 점화식을 얻을 수 있다. f(n) = f(n-5) + f(n-1) → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { //출력값 범위가 int max 값을 넘어가므로 long 배열로 만든다. static long[] dp = new long[101]; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다. public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

1번 → 규칙을 찾아보면 피보나치 수열과 같아, 동일한 방식으로 접근해 풀면 되는 문제 → Top-down 방식 (Intellij 에서는 StackOverflow 가 났지만 백준에서는 통과됐다.) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] dp; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

1번 → 1. 입력값 a,b,c 에 해당하는 출력값을 구분하기 위해서 dp[][][] 3차원 배열 공간을 생성한다. 2. 각 조건에 맞게 계산을 진행하고, 계산한 출력값들을 dp 에 저장한다. 3. 재귀로 함수가 다시 호출될 시, 똑같은 입력에 대한 dp 에 저장된 값이 있으면 해당 값을 사용한다. (중복 계산 줄임) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][][] dp = new int[21][21][21]; //중복 계산을 막기 위해 중간 결과값들을 저장하기 ..

1번 → 기존 중복 계산이 포함된 재귀로 풀었던 문제를, DP(동적 프로그래밍)로 해결한 문제 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int fib_count = 0; static int fibonacci_count = 0; static int[] ary; static int[] ary2; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //버..