본문 바로가기

동적프로그래밍6

[백준] 1010번 다리 놓기 JAVA (자바) 풀이 문제 1010번 (DP) :  도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다    :  다리를 짓기에 적합한 곳 = 사이트    강 서쪽 사이트 = N개, 동쪽 사이트 = M개 (N ≤ M)  :  한 사이트 - 한 다리 연결     크로스처럼 다리끼리 겹칠 수 없다  :  서쪽과 동쪽을 연결하는 다리를 지어라   [입력]  : 첫 줄에는 테스트 케이스의 개수 T : 그 다음 줄부터 서쪽과 동쪽의 있는 사이트의 개수 정수 N, M (0    [출력] : 다리를 지을 수 있는 경우의 수를 출력   [과정]  1:1로 연결해야하므로 최대 N개의 다리를 설치할 수 있다 단, 크로스처럼 다리가 겹쳐서는 안된다  크로스는 동쪽 다리의 인덱스가 순서대로 (이전 인덱스 되어야한다고 생각.. 2024. 6. 29.
[백준] 1003번 피보나치 함수 JAVA (자바) 풀이 문제 1003번 (DP)int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }} fibonacci(3) = fibonacci(2)와 fibonacci(1) fibonacci(2) = fibonacci(1)과 fibonacci(0)    [입력] :  첫째 줄에 테스트 케이스의 개수 T    각 테스트 케이스에 N이 주어진다 ( N은 40보다 작거나 같은 자연수 또는 0)  [출력] :  각 테스트 케이스.. 2024. 6. 29.
[백준] 9095번 1, 2, 3 더하기 JAVA (자바) 풀이 문제 9095번 (DP) : 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지   합을 나타낼 때는 수를 1개 이상 사용1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.    [입력] :  첫째 줄에 테스트 케이스의 개수 T    각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다 ( n은 양수이며 11보다 작다)  [출력] :  각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-do.. 2024. 6. 29.
[백준] 14916번 거스름돈 JAVA (자바) 풀이 문제 14916번 (DP) :  거스름돈 = 2원, 5원  :  거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램  :  예) 거스름돈이 15원이면 5원짜리 3개, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개   [입력] :  첫째 줄에 거스름돈 액수 n (1 ≤ n ≤ 100,000)   [출력] :  거스름돈 동전의 최소 개수를 출력 (거슬러 줄 수 없으면 -1 출력)[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나.. 2024. 6. 11.
탐색 알고리즘2 (이분탐색, DP) 탐색 DP(Dynamic Programming, 동적 계획법) 겹치는 결과를 별도의 메모리 영역에 저장해서 한번만 계산하고 재사용하도록 한다  DP 공식 f(n) = f(n-1) + f(n-2) 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나눠서 해결작은 것부터 해결해서 점차 빌드업메모제이션 (memoization)타뷸레이션 (tabulation)일부만 계산해도 답이 나올 때모두 계산해야 답이 나올 재귀반복문시간 복잡도 O(n)시간 복잡도 O(n) DP의 조건최적 부분 구조(Optimal Substructure)큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.중복되는 부분 문제(Overlapping Subproblem)부분 문제가 중.. 2024. 6. 3.
[백준] 2839번 설탕 배달 JAVA (자바) 풀이 문제 2839번  :  설탕 N킬로그램 배달해야 한다    설탕은 봉지에 담겨져 있다 ( 3킬로그램 봉지 or 5킬로그램 봉지 )    봉지의 최소 개수를 구해라 [입력] :  첫 줄에 N  [출력] :  봉지의 최소 개수 출력    ( 정확하게 N킬로그램 만들 수 없다면 -1 출력 )[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 1) Top-down(하향식)     하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식      이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization사용 public.. 2023. 9. 22.

티스토리툴바