1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 0-1 Knapsack: 각 물건을 배낭에 넣거나 넣지 않거나 두 가지 경우만 고려하는 문제.0-N Knapsack: 각 물건을 배낭에 여러 개 넣을 수 있는 문제입니다.Fractional Knapsack: 각 물건을 배낭에 일부분만 넣을 수 있는 문제입니다.: 무게 대비 가치가 높은 물건부터 배낭에 담는 탐욕 알고리즘(Greedy Algorithm)을 이용하여 풀 수 있다.  import java.io.Buf..

0. 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 문제 이해 Brute force DP 2. 제출 가. Brute force import java.util.Scanner; // brute force -> 144ms public class BOJ1463 { static int N, ret = Integer.MAX_VALUE; // 입력받은 수 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); solve(N, 0); System.out.println(ret); sc.close(); } stat..

1. 이항 계수 구하기 가. 이항 계수 이항 정리 : 이항식의 거듭제곱을 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리. 이항 계수 : 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. (x+y)^3 = x^3 + 3x^2y + 3xy^3 + y^3 조합으로 이항 계수를 구할 수 있다. 위와 같이 일반화할 수 있다. 나. 조합 공식 nCr = n! / (r!( n-r)!) 조합 공식 - 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다. nCr = (n-1)C(r-1) + (n-1)Cr 이는 재귀 함수로 구현할 수 있다. comb(n, r) IF n==k or k==0 : RETURN 1 // 모두 뽑거나 하..

1. Memoization 가. 피보나치수열 F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn; 피보나치수열의 점화식이다. fib(n) IF m < 2 : RETURN n ELSE : RETURN fibo(n - 1) + fibo(n - 2) fib1, fib2 ... 등이 중복 호출이 발생한다. fib()는 순수 함수다. 💡 순수 함수 함수 반환 값은 동일한 인수에 대해 일정합니다. 이 함수에는 부작용이없습니다. (함수 밖에 위치한 어떠한 상태 값도 수정하지 않는다.) 그렇기 때문에 fib1, fib2, … 등을 계산 결과는 항상 일정하다. 한 번만 계산하고 결괏값을 재사용할 수 있다. 나. Memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 매번 다시 계산..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 백트래킹 순열 DP 2. 제출 가. 순열 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA1247 { static int n, ret; static boolean[] vis; static Point work, home; static Point[] custs; public static void main(String[] args) throw..

0. 문제 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. 문제 이해 2개의 돌을 뺄 수 없다는 조건 때문에 수학적 규칙을 찾기 어려웠다. N=1000이고 제한시간은 1초다. 1초를 1억으로 가정하면 시간복잡도는 O(n^2)쯤이다. 모든 경우의 수를 다 구해서 풀면 O(n^3)이다. DP로 풀어야 한다. 상근이가 이기는지 지는지 알아내는 방법은 다음과 같다. 돌의 개수가 1 ~ 5까지는 비교적 쉽게 구할 수 있다. 돌의 개수가 6일 때는 6에서 1, 3, 4개를 빼본다. 6 - 1 = 5, 6 - 3 = 3 그리고 6 - 4 = 2에서 단 한 번이라도 상근이가 이기면 6에서도 상근이가 이긴다. (= 모든 경우에서 창영이가..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자. 1. C++ 가. 제출 #include #include using namespace std; const int MAXN = 20; int n, l, ret; int t[MAXN], k[MAXN]; void solve(int depth, int cal, int score){ if(depth == n){ if(cal ret){ ret = score; } return; } if(cal > l) re..