패스트터틀

ㅇ 기본적인 틀 ㅇ A에서 A2 -> A3 -> ... -> An 까지 호출후 An -> An-1 -> ... -> A2 -> A1 순서대로 반환 Stack을 쌓고 회수하는 과정이다. 재귀함수가 어려운이유 1. 인간의 직관으로 이해해야 하는영역이기 때문에 직관적이라는 장점과 직관적이라는 단점이 존재 2. 기존에 접해보지 않은 반복문이라 익숙하지 않음 예를들어서 기본 반복문과의 차이점을 살펴볼때 1부터 10까지 출력하는 프로그램 작성하였을때 for(int i = 0 ; i < 10 ; i++){ System.out.println("%d", i); } 위와 같이 단순 반복문을 사용할경우에는 매우 쉽지만 public class _Ere{ // 1부터 10까지 출력한다. static void sum(int a)..

https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net dp(n) = 2*dp(n-1) + 3*dp(n-2) + 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 위의 그림과 같은 과정을 통해 위의 점화식을 도출할수 있다. 그리고 코드를 짜서 제출할경우 시간초과를 겪는데 그러한 이유를 살펴보면은 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 부분에서 계속 구한값을 다시 계산하고 다시계산하는것을 알수있다. 이부분 또한 동적프로그래밍 기법을 적용하여서 한번구한값은 다시 구하지 말자라는 방식을 써야..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net D(n) = 3*D(n-2) + 2*(D(n-4) + D(n-6) +..... + D(0)) package dp; import java.io.IOException; import java.util.Scanner; public class _2133{ static int result = 0; static int..

https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net dp문제의 가장 기본이 되는 피보나치이다. 점화식을 재귀함수로 어떤식으로 표현할수있느냐도 알수있는 핵심문제이다. A(n) = A(n-..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 우선 외판원 문제는 현재 나온 이론으로는 풀수없지만 그나마 가장 나은 방법으로 푸는것이 DP방법이다라는 사실을 알고있어야한다. N! 를 n^2*2^n 으로 줄였다는 사실만 알자. 비트마스크 복습 dp[3][1011] 의 뜻은 3번째도시에서 2 번째도시까지 가는 최소한의 수 dp[2]..

https://www.acmicpc.net/problem/12813 12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net bitmask 문제에 앞서서 손풀기 package etc; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; public class _12813{ public static void main(String args[]) throws IOException{ Buffered..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 우선 내가 주어진 문제가 시험문제이고 DP라는 가정이 있다면 위와같은 가정으로 추론으로 점화식을 풀수있다. 하지만 점화식이 최적의 답인지 아니면 그리디알고리즘에서 더 빨리 찾는법이 있는지 아니면 그외에 더 최적의 알고리즘이 있는지는 경험이 늘어나봐야 알것같다. package dp; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class _11727{ s..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net fibonacci 수열을 구할때랑 똑같다. 2xn의 직사각형에서 n==1 일때는 2x1을 넣는 경우의수 총 1개 n==2 일때는 2x1로 채우는 방법한개, 1x2로 채우는 방방법한개 , 총 2개 n==3 일때는.. ..... .... ... .. . n=x 일경우 경우의수는? 여기서 모든 경우의수를 차근차근 고려하는것은 내가 아닌 컴퓨터가 계산한다고 치고 마지막에 들어올 경우의수부터 따져보자. 여기까지는 강의에서 나온..