최장 증가 부분 수열의 응용 문제와 해결 전략
교차하지 않는 다리 건설 문제
강의 양안에 위치한 도시들을 연결하는 다리를 건설할 때 교차하지 않도록 최대 다리 수를 구하는 문제입니다. 하안 도시를 배열 인덱스로, 상안 도시 번호를 값으로 매핑하면 최장 증가 부분 수열(LIS) 문제로 변환됩니다. 도시 쌍을 정렬한 후 LIS 길이를 계산합니다.
#include <iostream>
#include <algorithm>
using namesp ...
7월 3일 03:26에 게시됨
하이쿠 조건을 만족하는 구간 존재 여부 판별 알고리즘
O(n log n) 이분 탐색 기법
누적 합 배열을 활용하여 각 시작 인덱스별로 X, Y, Z 합 구간의 종료 지점을 전처리합니다.
이진 탐색을 통해 정확히 X, Y, Z에 해당하는 부분 합의 끝 위치를 계산한 후,
연속된 세 구간이 조건을 만족하는지 O(n) 시간에 검증합니다.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
...
6월 29일 02:27에 게시됨