DNF LOVE

DP의 대표격인 피보나치 알고리즘. 이를 구현하는 데에는 다양한 방법이 존재한다. 그 중 몇가지를 소개하고자 한다. 1. 재귀함수 import java.util.*; import java.io.*; public class fibo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); System.out.println(fibo(num)); } public static int fibo(int n) { if(n

알고리즘 시험 유형 중 가장 기본 중 기본이 소인수 분해, 약수 구하기가 아닌가 싶다. 당연히 '약수를 구하는 알고리즘을 구현하시오'가 아닌 약수를 이용한 심화된 알고리즘을 풀어야 한다. [약수 구하기] '약수'란, 어떤 수로 정수가 나누어떨어지는것을 대하여 이르는 말이다. 그리고 1과 자기자신으로밖에 나누어 떨어지지 않는 수를 우리는 소수라고 부른다. 그렇다면 약수를 알고리즘 화 시키는 것은 어떻게 해야할까? 약수의 정의를 조금 다르게 해보자. 어떤 자연수 a, b가 있을 때 a를 b로 나누었을 때 나머지가 0이면 b는 a의 약수라 한다. 이렇게 정의를 알고리즘 화시켜보면 if문과 for문을 어떻게 활용해야할지 감이 잡히게 된다, import java.util.*; public class divisor..

DP알고리즘의 또 다른 문제 2xn타일 구하기 문제이다. 이 문제도 어제 풀었던 1, 2, 3 더하기와 똑같은 원리로 이루어져 있다. 우선, 타일은 2x1 과 1x2 이 두가지가 주어진다. 그러다면 우리가 바로 알 수 있는 경우의 수는 1일떄와 2일때이다. tile[1] 일때, 2x1 하나밖에 쓰이지 못하니 경우의 수는 1이다. 또, tile[2] 일때, 2x1 타일을 두개 겹친 것과 1x2 타일을 가로로 두 개 겹친 것해서 경우의 수는 2가지가 나온다. 그렇다면 3일때는 어떨까? 2x1타일을 앞에 세울 때, 2가지 경우와 1x2타일을 두개로 겹쳐서 2x2로 만들때 1가지 경우의 수를 더하면 3가지의 경우의 가지가 나온다. 그렇다. 2x1타일을 맨 앞에 세웠을 때의 경우의 수와 1x2타일을 가로로 겹쳐 ..