일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 백준 double rainbow
- 암호만들기 백트래킹
- 너비우선탐색
- icpc 2021
- 백준 암호만들기
- 23567 c++
- 암호만들기 c++
- 동적계획법
- C++
- dp
- 백준 double rainbow c++
- 백준 1759 c++
- 백준 더블 레인보우
- 백준 1094 막대기
- BFS
- 깊이우선탐색
- 다이나믹 프로그래밍
- 막대기 c++
- 1094 c++
- 백준 1094 c++
- 백준 5430 c++
- 백준
- 백트래킹
- 백준 암호만들기 c++
- 백준 23567
- 백준 1094 막대기 c++
- 백준 23567 c++
- 1759 c++
- double rainbow c++
- dfs
- Today
- Total
dev study-log
[백준 / #11054 / C++] 가장 긴 바이토닉 부분 순열 본문
이번 문제는 DP 연습 겸 해서 풀어본 문제이다. 이 문제와 연관된 문제들도 풀어볼 예정이다.
https://www.acmicpc.net/problem/11054
문제 해석:
문제는 LCS (Longest Common Sequence)와 비슷하고 다른 여타 순열 문제와 마찬가지로 동적 계획법(Dyanamic
Programming. 이하 DP)로 풀어나가는 문제이다. 문제에서 주어진 수열의 최대 길이는 1,000으로 비교적 작은 편에 속하므
로 모든 경우의 수를 탐색해도 1초 안에 충분히 들어오는 시간이기 때문에 dp테이블을 완성하고 최댓값을 찾는 과정에서
모든 경우를 탐색해도 충분한 시간이라고 본다. 이 문제에서 DP를 어떻게 사용하는 가는 아래에서 설명하겠다.
알고리즘 코드 및 해설:
DP 테이블을 어떻게 구성하느냐가 관건이다. 우선 문제에서 주어진 바이토닉 부분 순열은 오름차순으로 K에 도달하고 K
에서부터는 내림차순으로 구성되는 순열이라고 설명해주었다. 이는 곧 주어진 순열에서 K까지 갔을 때 구할 수 있는 최대
의 오름차순 부분 순열의 개수를 구해주고 K부터 순열의 끝까지 최대의 내림차순 부분 순열을 구해주고 더하면 된다. 한마
디로 주어진 순열에서 우선 오름차순으로 부분 순열의 최대 크기를 각각의 위치마다 구해주고 내림차순도 마찬가지로 구
해준 후 두 수를 각각의 위치에서 더했을 때 최대가 되는 K를 찾고 그 더한 값을 출력해주면 된다.
그렇다면 dp 테이블은 어떻게 구하냐, 바로 하나하나씩 대조해보면 된다. 이중 for문 중 첫번째 겉의 for문으로 순열에서 위
치를 지정하면 만약 그 위치보다 앞 쪽의 위치에 작은 수가 존재하면 그 수의 dp 값에 + 1 해주는 형식으로 구해주면 된다.
이 때, 주의해야 할 점은 이렇게 비교할 때 기존의 dp값을 같이 비교해줘야 한다는 것이다. 그리하여 최댓값을 dp에 남겨놓
으면 마찬가지로 그 뒤의 위치에서 순열 값을 비교하고 만약 비교하고자 하는 수보다 작으면 오름차순 / 혹은 역방향으로
내림차순이므로 dp값을 비교해주면 된다. 내림차순은 마찬가지로 끝에서부터 시작하여 역으로 비교해주며 dp 값을 채워
주면 된다.
이번 문제는 그렇게 설명할 것이 많지 않아 여기서 마무리하겠다.
이렇게만 보면 참 쉬운데 필자는 DP 문제가 익숙치 않아 테이블을 구성하는 방법을 고안해내는데 오래 걸렸다. 앞에서 구
한 사례를 어떻게 이용할 지에 대해 생각만 잘해낸다면 쉽게 풀어낼 수 있을 것이다.
'Algorithm' 카테고리의 다른 글
[백준 / #2294 / C++] 동전 2 (0) | 2023.02.07 |
---|---|
[백준 / #10844 / C++] 쉬운 계단 수 (0) | 2023.02.02 |
[백준 / #14503 / C++] 로봇청소기 (0) | 2023.01.30 |
[백준 / #10026 / C++] 적록색약 (1) | 2023.01.29 |
[백준 / #1987 / C++] 알파벳 (2) | 2023.01.25 |