유튜브 ALGORITHM JOBS 채널에서 풀이해준 영상을 통해 배우고 공부한 내용 정리
https://www.youtube.com/watch?v=8OGlq6zKOl0
해당 문제는 LIS(Longest Increasing Subsequence, 최장 증가 부수열(문자열))를 구하여 푸는 문제다.
문제를 읽으면서 LIS를 이용해서 풀어야 된다는 것을 빨리 캐치하는 것이 중요할 것 같다.
해당 문제에서는 염도를 숫자로 나태내는데 이것이 "점점짜게 먹다가 어느 순간 부터 점점 싱겁게 먹으려고 한다." 라는 문장을 통해 순열과 관련된 문제라는 것을 유추할 수 있을 것이다.
"최대 몇 개를 먹을 수 있는지 구하여라" 라는 문장을 통해 가장 많은 (여기서는 한 줄로 쭉 나열되어 있으니 가장 긴) 집합을 찾으라는 것을 알 수 있다.
"짜게 먹다가 어느 순간 부터 점점 싱겁게"를 통해 정방향과 역방향 모두 적용 가능하다는 것을 알 수 있다.
즉, 이 문제는 나열된 수열로 부터 왼쪽으로부터는 증가하는 부분 수열, 오른쪽부터 시작하는 것으로는 감소하는 부분수열, 이 둘을 조합하여 가장 큰 긴 수열을 찾는 것이다.
알고리즘 잡스 강사님께서는 해당 문제를 다음과 같이 수열의 각 원소에 위치마다 정방향과 역방향 LIS 값을 계산한 후 각 위치에서 정방향과 역방향의 LIS 값을 더한 것에 1을 빼기 연산 함으로써 답을 찾는 방법을 알려주셨다.
1번 문제를 풀어보면 다음과 같이 표를 그려 풀 수 있다.
위와 같은 방식으로 나머지 2번 3번도 풀어보면
위와 같은 답이 나온다. (실제 정답과 다를 수 있습니다.)
