README.md

백준 #11054 가장 긴 바이토닉 부분 수열

• 알고리즘 스터디 문제 풀이입니다.
• 백준 11054번 에서 풀어볼 수 있습니다.

문제설명

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

수열 내에서 어떤 수를 고르던 해당 바이토닉 수열을 만족하는 수열을 골랐을 때 가장 긴 수열은 길이가 얼마인가? 문제

풀이

1. 잘못된 풀이방법 트리를 통해 모든 경우의 수를 따질 경우 메모리 초과

2. dp 를 사용한 풀이

   1. 해당 수열은 증가하는 수열과, 감소하는 수열을 따로 세 주어야 한다. 그러므로 for문을 두번 돌아야 함.
   2. 먼저 증가하는 수열은 정배열로 dp를 해주어 모든 발생하는 증가 수열의 최대값을 저장해준다.
   3. 그리고 배열을 뒤집어서 똑같은 dp를 해주면, 모든 발생하는 감소 수열의 최대값을 저장할 수 있다.
   4. 특정 인덱스의 감소 수열 최대값과, 증가 수열의 최대값이 합쳐질 떄 가장 최대로 되는 값을 구해주면 답

3. 이분탐색을 사용한 풀이

• 업데이트 예정