Study (63) 썸네일형 리스트형 [백준 자바JAVA] 2579번 - 계단 오르기 https://www.acmicpc.net/problem/2579● 문제문제의 요구사항을 살펴보자1. 계단을 오를땐 한 계단 또는 두 계단씩만 오를 수 있다2. 연속된 3개의 계단을 밟으면 안된다(ex. 1층 2층 3층 연속으로 밟기)3. 마지막 계단은 반드시 밟아야 한다 이 문제는 Top-Down 방식보단 Bottom-Up방식이 더 어울릴 것 같아서 Bottom-Up 방식으로 생각해보았다.계단 1층부터 하나씩 값을 더해가면서 채워나가 마지막 누적 합을 구하면 되는데 인덱스 i일때 두칸 전의 값과 첫칸 전 + 세번째칸 전의 값 중 큰 값을 현재 i의 계단에 저장하여주면된다.● 코드import java.io.*;public class Main { public static void main(String.. [백준 자바JAVA] 11726번 - 2xn 타일링 https://www.acmicpc.net/problem/11726● 문제n의 입력에 따라 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 계산하는 dp 문제이다.n=1부터 각각 하나씩 그림을 그려보면서 수를 세어보게되면n123456789경우의 수1235813213455즉, dp[n] = dp[n - 2] + dp[n - 1]의 경우의 수가 발생하게 된다. 근데 문제에서 10007로 나눈 나머지를 출력하라고 하여서 결과값 출력때 10007을 나누게 되면 Integer.MAX_VALUE를 넘어 Overflow가 발생하므로 연산시에 10007로 나눈 나머지를 저장해주어야한다.● 코드import java.io.*;public class Main { public static void m.. [백준 자바JAVA] 1003번 - 피보나치 함수 https://www.acmicpc.net/problem/1003● 문제피보나치 수열에서 호출되는 0과 1의 갯수를 구하면 되는 문제이다.처음에는 원래 있던 피보나치 dp코드에 0과 1이 호출될때에 전역변수에 카운팅을 하는 방식으로 구성하였는데 이는 시간초과가 발생하였다.생각을 해보니 피보나치 수열이 진행되면서 반복해서 사용되는경우가 발생하여 시간초과가 발생한 것 같았다.예를 들어 fib(5)의 경우에는 0, 1, 2, 3을 반복해서 여러번 사용하므로 이는 다시 사용할 필요 없이 저장해 두었다가 사용하면 시간측면에서도 효율적이다. 그리고 0과 1이 나오는 패턴을 분석해보니N123456789Fib(0)1011235813Fib(1)01123581321N에 대한 0호출 횟수 = N - 1의 1 호출 횟수N에 .. [백준 자바JAVA] 14606번 - 피자 (Small) https://www.acmicpc.net/problem/14606● 문제피자의 층 수를 계속해서 분해해 나가는 DP문제 중의 일부이다.예를들어 피자가 5판인경우 먼저 3x2 = 6 으로 분리 시킨 후 2x1 + 1x1 = 3 으로 분리시킨다 1인 친구들은 더이상 분리가 불가능하지 그대로 두고 2를 1x1 = 1 로 분해시키면 총 6 + 3 + 1 = 10 이 얻을 수 있는 최대 즐거움이 된다.이거를 표로 정리해보면피자 판 수123456789행복도01361015212836증감량0+1+2+3+4+5+6+7+8 표를 확인해보면 증감량이 일정하게 증가하는것을 확인할 수 있다!● 코드import java.io.*;public class Main { public static void main(String[].. [백준 자바JAVA] 10826번 - 피보나치 수 4 https://www.acmicpc.net/problem/10826 ● 문제보기에는 간단한 피보나치 수열 문제 같지만 "10,000 보다 작거나 같은 자연수" 라는 조건 때문에 조금 까다로워진 문제였다.int형과 long형 둘 로는 해결이 안되고 BigInteger라는 자료형을 사용해 해결해야 하는 문제이다.BitInteger은 무한대를 커버할 수 있는 자료형으로 평소 사용하는 자료형과는 달리 여러 메소드들이 존재한다.● 코드import java.math.BigInteger;import java.io.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new .. [백준 자바JAVA] 13301번 - 타일 장식 https://www.acmicpc.net/problem/13301 ● 문제일반적인 피보나치 수열을 활용한 문제에서 변형된 문제이다!피보나치 수열과는 다르게 각 변을 더한 둘레를 구하는 것이므로 일단 한번 작성해 보았다.입력(N)123456789둘레값461016264268110178증가2461016264268110 1, 1, 2, 3, 5, 8 ... 처럼 증가하는 피보나치 수열처럼 둘레값 역시 피보나치 수열처럼 올라가는 것을 확인할 수 있다그리고 서브 태스크상에 long 자료형을 사용하라고 나와있으므로 해당 부분까지 반영해준다.● 코드import java.io.*;public class Main { public static void main(String[] args) throws IOExcepti.. [백준 자바JAVA] 9625번 - BABBA https://www.acmicpc.net/problem/9625● 문제초기상태는 A 1번 눌렀을땐 B 2번 눌렀을 땐 BA 3번 눌렀을땐 BAB 4번 눌렀을땐 BABBA.....이는 화면에 A는 B로 바뀌고 B는 BA로 바뀐다는 걸 알 수 있다. 각 A,B의 횟수를 표로 나타낸다면클릭수(K)123456789A갯수01123581321B갯수112358132134각 숫자를 비교해보면 전전의 값과 전의 값을 더한 값이 현재의 값인걸 확인할 수 있다.이는 피보나치수열과 똑같다는것을 의미한다! 이를 이용한 DP코드를 만들어 보았● 코드import java.io.*;public class Main { public static void main(String[] args) throws IOException{ .. Dynamic Programming(동적 계획법) 다이나믹 프로그래밍이란?최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 DP를 쓰는 이유일반적인 재귀방식과 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다. 예를들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하게 된다면return f(n) = f(n - 1) + f(n - 2)그러나 위의 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게되고 이로인해 100번째 피보나치수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 늘어난다. 이러한 반복되는 문제들의 결과값을 저장해두고 재사용하게된다면 매우 효율적으로 문제를 해결할 수 있게 된다.. 이전 1 2 3 4 5 ··· 8 다음
