▪︎ 문제 백준 1351 문제 ▪︎ 알고리즘 설계 점화식을 그대로 재귀로 구현 A(n) = A(n / P) + A(n / Q) 조건을 보면, 배열로는 구할 수 없음 배열의 인덱스는 long 타입이 안됨. 무조건 int만 가능. ...

▪︎ 문제 백준 1202 문제 ▪︎ 알고리즘 설계 각 가방은 하나의 보석만 담을 수 있음 가방 용량 C보다 작거나 같은 무게의 보석만 담을 수 있음 선택된 보석의 총 가격의 합을 최대화해야 함 즉, 여러 개의 제한된 자원(가방)에 대해 이익이 최대가 되도록 보석을 배정하는 문제 각 단계의 최적해를 구하는 문제 → ...

▪︎ 문제 백준 1106 문제 ▪︎ 알고리즘 설계 예시 목표 고객 수 C = 10 도시 A: 고객 3명 확보, 비용 2 도시 B: 고객 5명 확보, 비용 4 초기값: dp[0] = 0, dp[나머지] = INF (매우 큰 값) dp 배열은 확보할 수 있는 고객 수를...

▪︎ 문제 백준 2243 문제 ▪︎ 알고리즘 설계 명령어 1: 사탕 꺼내기, 맛의 순위 선택, 개수 무조건 1개, 꺼내는 사탕 출력 명령어 2: 사탕 넣기 or 꺼내기(+ / -), 맛의 순위 선택, 개수 정할 수 있음 예시로 이해하기 2 1 2 : 1위 맛 사탕 2개 넣기 (현재 사탕 개수: 1위 ...

▪︎ 문제 백준 14428 문제 ▪︎ 알고리즘 설계 세그먼트 트리를 사용하여 각 노드에 해당 구간의 최솟값의 인덱스를 저장한다. 구간이 주어진 쿼리 시, 최솟값을 비교하는 것이 아니라 인덱스를 비교하여 트리 값을 관리한다. ▪︎ 코드 import java.io.*; import java.util.*; pub...

▪︎ 문제 백준 2357 문제 ▪︎ 알고리즘 설계 세그먼트 트리를 이용한다. 배열을 트리 형태로 만들어서 미리 초기화를 통해 값을 계산한 후 저장해 빠른 쿼리가 가능하도록 한다. 제한 시간 1초이므로 선형 탐색을 통해 설계하면 시간 초과가 발생한다. 최솟값, 최댓값 트리 배열 초기화, 쿼리 계산 ...

▪︎ 문제 백준 2042 문제 ▪︎ 알고리즘 설계 세그먼트 트리? 배열의 특정 구간 합, 최댓값, 최솟값 등을 빠르게 구하기 위해 만든 트리구조 세그먼트 트리의 핵심 아이디어 배열을 트리로 표현! 각 노드는 자신이 담당하는...