알고리즘 문제풀이 복습 1

12015 가장 긴 증가하는 부분 수열2

부분 수열1 문제는 DP로 풀 수 있습니다

하지만 같은 풀이를 여기에 적용하면 수열의 크기가 100만이라 TLE를 받습니다

따라서 dp배열을 보다 빠른 방법으로 채워주어야 합니다

이는 이분 탐색을 통해 해결 할 수 있습니다

수열을 s라고 할때, $dp_{i}$를 $s_{i}$를 끝으로 하는 증가하는 부분수열의 길이라고 정의합니다

그리고 $X_{j}$는 $dp_{i}=j, 1\leq i\leq N$를 만족하는 $s_{i}$ 중 min값으로 정의합니다

이후 dp값을 1부터 N까지 보면서 X의 값 중 이때의 수열 s의 값보다 작은 값을 이분탐색으로 찾아줍니다

이렇게 찾은 X의 인덱스로 dp값을 갱신해주고, 갱신한 dp값으로 X의 다음 인덱스 값을 다시 갱신해주면 문제를 해결 할 수 있습니다

시간 복잡도는 $O\left ( NlogN \right )$입니다

 

20033 square, not rectangle

가로길이 N, 세로 길이 H인 배열에서 가장 큰 정사각형의 한 변의 길이를 찾아주는 문제입니다

이때 제한은 N이 30만 H는 10억입니다

정사각형의 한 변의 길이 K를 알고 있다고 가정할때, 배열에서 이를 만족하는 정사각형이 있는지는 $O\left ( N^2 \right)$에 찾을 수 있습니다.

하지만 이런 경우 길이 K를 이분탐색으로 찾아준다해도 TLE를 받습니다

따라서 정사각형 판단을 N안에 해주어야합니다

정사각형의 존재여부를 선형시간안에 판단하는 방법은 다음과 같습니다

먼저 st라는 변수를 무한대로 초기화합니다

배열을 1부터 N까지 봅니다

배열을 탐색하면서 배열의 높이가 K이상이면 st변수를 그때 배열의 인덱스로 바꿉니다

st가 무한대가 아니고 배열의 높이가 K이상이고, 이때의 인덱스 - st + 1이 K이상이면 true를 리턴합니다

배열을 탐색하다 높이가 K이하이면 st를 무한대로 초기화합니다

이렇게 결정함수 able(K)를 만들어주면 문제를 해결 할 수 있습니다

 

2473 세용액

이분탐색 풀이와 투포인터 풀이 두가지가 있습니다.

이분탐색 풀이는 음수해 부분도 고려해야하는 어려운점이 있습니다.

투포인터 풀이는 그냥 용액을 정렬하고, 1부터 N까지 보면서 i+1부터 N사이 구간을 투포인터를 이용하여 조건에 맞는 용액을 찾아주면 됩니다.

 

13302 리조트

dp(i,j) : 1~i일까지 쿠폰 j장을 남길때의 최소 비용

위처럼 dp배열을 정의합니다

만약 i번째일이 갈 수 없는 날이면 그대로 dp(i+1, j)를 저장

아니면 1일권, 3일권 5일권을 샀을때의 가격 중 min값을 저장

쿠폰이 3장 이상이면 이렇게 구한 비용과 쿠폰을 썼을때의 비용 중 min값을 저장

위처럼 점화식을 세우면 문제를 해결 할 수 있습니다

 

3176 도로 네트워크

LCA문제입니다

K개의 쿼리마다 주어지는 정점 u,v에 대해 두 정점 사이의 최소거리와 최대 거리를 출력해주면 됩니다

D(u, i) : u와 u의 $2^i$번째 조상을 잇는 경로의 가중치 중 max,min 값

이렇게 정의하고 배열을 채워주면 됩니다

 

15586 MooTube

Q개의 쿼리에 대해 각각 $v_{i}$정점에 대해 유사도가 $k_{i}$ 이상일때, 추천되는 영상의 수를 찾아주어야 합니다

문제를 있는 그대로를 구현하면 TLE를 받습니다

따라서 유니온 파인드와 오프라인 쿼리를 활용하여 문제를 해결해야합니다

먼저 주어진 간선들을 가중치 순서대로 정렬합니다

마찬가지로 주어지는 쿼리들도 가중치 순서대로 정렬합니다

가중치가 큰 쿼리부터, 가중치가 큰 간선부터 하나씩 보면서 유사도가  K이상이면 merge해줍니다

이때 쿼리가 원래 순서가 아님으로 이에 유의해서 답을 출력해주면 해결 할 수 있습니다

 

14867 물통

문제에서 주어지는 물통의 용량 (a, b)를 정점으로 보고, 가능한 작업 3가지를 간선으로 정의하면 BFS로 해결 할 수 있습니다.

이런 경우 가능한 정점이 10만*10만이라 생각 할 수 있습니다

하지만 10만*10만 배열의 엣지만 고려하면 된다는 사실을 조금 고민해보면 알 수 있습니다

따라서 가능한 정점은 총 40만개뿐입니다