mushi   6년 전

1 2 1 2 1 2 처럼 증가 후 감소나, 감소 후 증가 가 반복되는 수열 중 가장 긴 수열을 찾습니다.

가장긴 증가(혹은 감소)수열 찾는걸 조건을 넣어서 믹스시켰습니다만 

아래와 같은 소스는 O(n^2) 인데, 다른 방법도 있을까요?


p.s  혹시 백준에 비슷한 문제 있을까요?

chogahui05   6년 전

증가 후 감소..

감소 후 증가.. 구간이 두 부분으로 쪼개진 건가요?


그 경우에는 증가 후 감소를 예로 들자면..

(1) 극점의 위치를 x라고 두시고

처음 ~ x까지의 최대 증가 수열 + x ~ 끝까지의 최대 감소 수열의 값 중

최대치를 찾으면 될 거 같은데요. 이 두 연산은 c++에 있는 upper_bound나 lower_bound를 이용하면 O(nlogn)에 끌날 수 있는 연산입니다.


1 2 4 5 6 3 2 4

같은 경우

x에서 끝까지의 최대 감소 수열은 어떻게 찾을까요?

이건 수열을 뒤집어서 생각하시면 됩니다.

4 2 3 6 5 4 2 1


뒤집어진 수열과 원래 수열을 어떻게 어떻게 mapping 시키면 될 거 같네요.


역방향인 경우에는 그냥 -1을 곱해가지고 하시면 됩니다.

mushi   6년 전

주어진 수열이 1 3 5 4 6 2 5 1 3 이면 1 3 2 5 3 (길이 5)의 지그재그 수열을 찾을 수 있습니다.

찾아보니 지그재그 라는 문제가 있더군요.  구간내 지그재그 숫자를 찾는거던데,  이것도 엄청 어려워 보이네요...(범위가  어마어마)


주어진 수열에서 가장긴 지그재그수열을 찾는 법중 빠른 해법이 있나요???

댓글을 작성하려면 로그인해야 합니다.