devStory

문제 : https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 현재 카드를 선택했을 경우, 현재 카드를 선택하지 않았을 경우 두가지 경우를 체크하는 재귀함수를 작성. 아래는 전체 코드이다. ...

문제 출처 : https://www.acmicpc.net/problem/11727 2 x 1 과 2 x 2 을 기본적으로 왼쪽 그림과 같이 타일링 할 수 있다. 이를 T( 1 )과 T( 2 )라고 하겠다. T( 3 )은 T( 2 ) 오른쪽에 2x1 타일을 더한 것과 같다. 또한, T( 1 )에 2x2 타일과 2x1 타일 두개를 더한 것과 같다. 마찬가지로, T( 4 )는 T( 3 )에 2 x 1 타일을 더한 것 그리고 T( 2 )에 2 x 2 타일 또는 2 x 1 두개를 더한 것과 같다. 즉, T( n ) = T( n-1 ) + T( n-2 )*2 인 것을 알 수 있다. 아래는 전체 코드이다. import java.io.BufferedReader; import java.io.IOException; imp..

문제 출처 : https://www.acmicpc.net/problem/9095 1 = 12 = 1 + 1 = 23 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3으로 나 타 낼 수 있다. 이를 S(1), S(2), S(3) 이라고 할 때 4는 S(3)에 +1을 한 것과 같다. 그리고 S(2)에 +2를 한 것과 같다. 마지막으로 S(1)에 +3을 한 것과 같다.즉, 4 = S(3) + 1 = 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 3 + 1= S(2) + 2 = 1 + 1 + 2 = 2 + 2 = S(1) + 3 = 1 + 3 이를 통해 정수 n을 1, 2, 3 의 합으로 나타내는 방법의 수를 S(n) 이라 할 때, S(n) = S(n - 1) + S(n -2) + S(..

문제 출처 : https://www.acmicpc.net/problem/9507 기존 피보나치보다 조금 더 복잡한 피보나치를 구현하는 문제.오늘 정리한 다이나믹 프로그램을 적용하기에 딱 좋은 기초 문제였다. 입력 첫 줄에 테스트 케이스 수가 주어진다 하여 MEMOZATION 기법을 이용 할 목적으로 전역 변수를 선언 하였다.static long[] fib = new long[68]; int는 -2147483648 ~ 2147483647 long은 -9223372036854775808 ~ 9223372036854775807다음으로 SOLUTION 함수를 작성 하였다. 기존의 B0TTOM-UP 방식으로 피보나치를 구현하는 것과 동일한 짜임(?)이다. public static long koong(int n){..

분할 정복 기법 : 큰 문제를 한번에 해결하기 힘들 때 작은 여러개의 문제로 나누어 푸는 기법. But, 이 작은 여러개의 문제들 중 같은 문제가 반복된다면? -> 오버헤드 증가 = 비효율적인 코드 위 문제를 해결하기 위한 방법은? 중복 제거 중복을 제거하기 위한 방법은 기억하기 방법을 사용. Top-Down 방식과 Bottom-Up 방식 두가지가 있음. 배열을 생성하고, 한번 계산 한 값은 배열에 저장한다. 같은 연산을 호출하면 저장되어있던 값을 return 하여 중복을 없앤다. 점화식을 생각하면 쉬움.대표적인 예 : 피보나치 수열N번째 수 = (N-1)번째 수 + (N-2)번째 수 fib(1) = 1, fib(2) = 1 이다. (기본값)fib(3)..