괴물 클럽

기본적인 동적계획법 접근은 dp[i][j]를 마지막 분할 지점이 i, 이전 분할 지점이 j일 때의 최소 비용으로 정의한다. 누적합을 sum[i] = Σk=1i a[k]로 두면, 전이식은 다음과 같다: dp[i][j] = min{ dp[j][k] + (sum[i] - sum[j])² }   ( sum[i] - sum[j] ≥ sum[j] - sum[k] ) 조건를 정리하면 sum[k] ≥ 2×sum[j] - sum[i]가 되며, 고정된 j에 대해 i가 증가함에 따라 하한 ...

교차하지 않는 다리 건설 문제 강의 양안에 위치한 도시들을 연결하는 다리를 건설할 때 교차하지 않도록 최대 다리 수를 구하는 문제입니다. 하안 도시를 배열 인덱스로, 상안 도시 번호를 값으로 매핑하면 최장 증가 부분 수열(LIS) 문제로 변환됩니다. 도시 쌍을 정렬한 후 LIS 길이를 계산합니다. #include <iostream> #include <algorithm> using namesp ...

주간 개요 이번 주는 생활 리듬이 불규칙하여 학습 효율이 저하되었고, 이를 개선하기 위해 환경을 변경하였다. 새로운 일정으로 인해 다음 주부터는 더 체계적인 학습과 경기 준비를 할 계획이다. 문제 해결 기록 SMU Winter 2025 Round 6 B. 스트리머의 밤 문제 요약: 여러 프로그램의 시작 및 종료 시간이 주어질 때, 전체 시간 내에 볼 수 있는 최대 프로그램 수를 ...

T1: 좋은 수 판별하기 문제는 길이 n의 정수 배열 a가 주어졌을 때, 각 원소 a[i]가 "좋은 수"인지 판단하는 것이다. 여기서 "좋은 수"란, 인덱스가 i보다 작은 세 개의 원소 a[j], a[k], a[l]의 합이 a[i]와 일치하는 경우를 말한다. 단, 같은 인덱스는 중복 사용할 수 없다. 제한 조건이 n ≤ 5000이므로, 최악의 경우 O(n²) 정도의 시간 복잡도를 허용할 수 있다. 따라서 ...

문제 설명 금명은 새 집에 들어가는 것을 기쁘게 생각하며, 자신만의 방을 꾸밀 수 있는 자유를 얻었다. 어머니는 예산을 n 원으로 제한했고, 금명은 이 내에서 최대한 중요한 물건들을 구입하고 싶다. 모든 물품은 두 가지 유형으로 나뉜다: 주요 항목과 보조 항목. 보조 항목은 반드시 해당 주요 항목을 구매한 후에만 살 수 있다. 각 주요 항목은 최대 2개의 보조 항 ...

1049. 마지막 돌의 무게 II 이 문제는 돌들을 두 그룹으로 나누어 각각 충돌했을 때 남는 돌의 무게를 최소화하는 것이 목적이다. 이는 0-1 배낭 문제로 변환할 수 있다. 각 돌의 무게와 가치는 동일하게 설정하며, 총 무게의 절반을 목표로 하는 배낭 용량을 정한다. 일차원 배열 버전 class Solution { public int lastStoneWeightII(int[] stones) { int ...

백트래킹 알고리즘 백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다. def backtrack(current_path, choices): if is_solution(current_path): add_to_result(current_path) return for choice in choices: if not is_valid(ch ...

T1: 중위값이 특정 값인 홀수 길이 부분 배열 개수 세기 주어진 순열에서 특정 수 ( b )를 중위값으로 가지는 홀수 길이의 부분 배열의 수를 구하는 문제이다. 핵심 아이디어는 각 원소를 ( b )보다 작으면 -1, 크면 1, 같으면 0으로 변환한 후, 누적합을 이용해 조건을 만족하는 쌍을 찾는 것이다. ( b )의 위치를 기준으로 오른쪽은 해시맵에 누적합을 저장하고, 왼쪽에 ...

이번 글에서는 문자열 처리를 위한 동적 계획법(DP)의 세 가지 핵심 문제를 살펴보겠습니다. 각 문제는 이전 문제의 개념을 확장하여 최종적으로 편집 거리(Edit Distance) 문제를 해결합니다. 1. 서로 다른 서브시퀀스 개수 문자열 s와 t가 주어졌을 때, s의 서브시퀀스 중 t와 동일한 것의 개수를 구합니다. 편집 거리 개념에서 '삭제'는 긴 문자열의 문자를 제거하는 ...

A B2029 코끼리 물 마시기 - 로그 수학 문제로, 원주율 π를 100배한 정수값을 사용하여 부동소수점 오차를 방지합니다. #include <iostream> using namespace std; void calculate() { int height, radius; cin >> height >> radius; int cylinderVol = height * 314 * radius * radius; int totalWater = 2000000; // 20L * 1000cm³/L * 100 (스 ...