6-O 관련해서 질문 있습니다.

jjune0427님, LIS(Longest Increasing Subsequence) 문제를 알아보는 것은 처음에는 어려울 수 있지만, 여러 문제를 해결하다 보면 점점 직관이 생길 것입니다. LIS 문제를 파악하는 데 도움을 줄 수 있는 몇 가지 요령을 알려드리겠습니다.

LIS 문제는 보통 다음과 같이 제시됩니다:
- 어떤 순서나 배열에서 특정한 조건 하에 최대 길이의 증가하는 부분 순서를 찾는 문제로 제시됩니다.
- “최장 증가 수열”이라는 직접적인 언급 없이 문제 조건 속에서 수열을 정렬하거나 순서대로 나열하는 것을 암시적으로 요구하는 경우가 많습니다.

다음은 추가 학습을 위해 추천드릴 수 있는 몇 가지 LIS 관련 문제입니다:

백준 ‘전기줄 문제 (LIS를 활용한 문제)’:
- 이 문제는 전기줄이 서로 교차하지 않게 하기 위해 몇 개의 전기줄을 제거해야 하는 문제로, LIS로 해결할 수 있습니다. 이 문제는 전형적인 LIS 문제로, 수열의 교차를 최소화하는 방식으로 문제를 바라보아야 합니다. 링크
백준 ‘가장 긴 감소하는 부분 수열’:
- 일반적으로 LIS 문제 셋업과 유사하나, 감소하는 조건을 반대로 적용해야 하는 문제입니다. 문제의 본질과 접근 방식을 이해하는 데 도움이 될 것입니다. 링크

강의를 통해 LIS에 대한 개념을 확립하고, 백준과 같은 플랫폼에서 여러 문제를 풀면서 자유롭게 적용해보면 좋겠습니다. 그리고 문제를 풀다 보면, 주어진 배열에서 수열을 생성하거나 정렬하는 과정에서 LIS의 필요성을 자연스럽게 인식할 수 있는 능력이 생길 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

6-O 관련해서 질문 있습니다.