DP

[Java] Knapsack

작성자:
Featured image for [Java] Knapsack

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 2. 공간 복잡도 개선 기존의 동적 계획법(DP)은 O(NK)의 공간 복잡도를 가지고 있다. (여기서 N은 물건의 개수, K는 배낭의 최대 무게를 … 더 읽기

[Java] DP – 응용

작성자:
Featured image for [Java] DP - 응용

1. 이항 계수 구하기 가. 이항 계수 조합으로 이항 계수를 구할 수 있다. 위와 같이 일반화할 수 있다. 나. 조합 공식 조합 공식 – 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다. 이는 재귀 함수로 구현할 수 있다. 중복되는 계산을 줄이기 위해서 메모이제이션을 활용한다. 순수 함수, 중복 부분문제 구조, 최적 부분문제 구조를 만족하기 때문에 … 더 읽기

[Java] Memoization, DP

작성자:
Featured image for [Java] Memoization, DP

1. Memoization 가. 피보나치수열 피보나치수열의 점화식이다. fib1, fib2 … 등이 중복 호출이 발생한다. fib()는 순수 함수다. 💡 순수 함수 그렇기 때문에 fib1, fib2, … 등을 계산 결과는 항상 일정하다. 한 번만 계산하고 결괏값을 재사용할 수 있다. 나. Memoization 하지만 이 방식은 memo라는 추가적인 메모리 공간이 필요하다. 재귀 함수 호출과 memo 저장을 위해서는 많은 메모리를 사용한다. … 더 읽기

[알고리즘] 9658. 돌 게임 4

작성자:
Featured image for [알고리즘] 9658. 돌 게임 4

0. 문제 9658번: 돌 게임 4 1. 문제 이해 2개의 돌을 뺄 수 없다는 조건 때문에 수학적 규칙을 찾기 어려웠다. N=1000이고 제한시간은 1초다. 1초를 1억으로 가정하면 시간복잡도는 O(n^2)쯤이다. 모든 경우의 수를 다 구해서 풀면 O(n^3)이다. DP로 풀어야 한다. 상근이가 이기는지 지는지 알아내는 방법은 다음과 같다. 큰 문제를 작은 문제로 나누고 작은 문제의 결괏값을 큰 문제를 … 더 읽기

[알고리즘] 5215. 햄버거 다이어트

작성자:
Featured image for [알고리즘] 5215. 햄버거 다이어트

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자. 1. C++ 가. 제출 재귀함수를 사용해서 모든 … 더 읽기