인프런 커뮤니티 질문&답변
작성한 질문수
6-K
해결된 질문
작성
·
34
0
http://boj.kr/da5acdd9bf904e17b2a814c2f3c9d646
N이 1,000,000이라 O(NlogN) 방식을 응용해서 풀려고 했습니다. 교안에는 O(NlogN) 방식으로 LIS의 길이를 측정하는 방법만 나와있으니까요. 사실 LIS 벡터가 LIS 그 자체가 되지 못하는 이유가 LIS의 길이가 최대로 갱신된 이후에 더 작은 값이 LIS의 앞 요소를 바꾸어버린다면, 수열에서 순서대로 뽑는 게 아니기 때문이라고 생각했습니다. 그래서 짠 방법이 lis의 최대를 갱신시키는 순간의 벡터만 계속해서 저장해주면, 수열의 앞에서부터 순서대로 뽑아서 증가하는 순서대로 저장한거고 이후의 수열을 검사하면서 LIS의 앞 부분을 건들여도 상관없는거니까 될 줄 알았는데 틀렸다고 뜨네요. 아마도 같은 lis 벡터의 동일한 인덱스에 들어올 수 있는 값들 중에서 수열의 가장 앞쪽에 위치한 원소를 저장해 만든 가장 긴 증가 수열이 문제에서 원하는 LIS라서 그런 것 같긴 한데... 제 코드가 틀린 이유가 알고 싶어요.
답변 2
1
안녕하세요 ㅎㅎ
auto it = lower_bound(lis.begin(), lis.end(), sequence[i]);
if(it == lis.end()){
lis.push_back(sequence[i]);
ret = lis;
}
else *it = sequence[i];이부분을 보시면 *it = sequence[i]로 대체하는 부분이 있습니다.
예를 들어
(base) zagabi@zagabiui-MacBookPro 코테 % ./test.out
4
2 5 3 7
로 실행하면
3
2 3 7
이 반환되게 됩니다. 물론 2, 3, 7은 정답이지만 이렇게 원본배열의 순서가 달라진 상태로 출력이 될 가능성이 있습니다.
예를 들어 다음과 같은 반례가 있습니다.
5
3 10 2 1 20
수강생님 코드:
3
1 10 20
이러한 부분 때문에 틀리는 것 같습니다.
또한,
LIS의 앞 부분을 건들여도 상관없는거니까
-> 이부분에 대한 코드가 혹시 어디인가요? *it = sequence[i]는 lis의 앞부분이 아니라 lower_bound로 찾은 해당 부분을 바꾸는 코드입니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 유병욱님.
질문하신 내용과 관련하여 LIS(Longest Increasing Subsequence)를 O(NlogN) 방식을 통해 구현하는 과정에서 발생할 수 있는 일반적인 문제와 그 이유에 대해 설명드리겠습니다.
LIS를 구하는데 사용하는 O(NlogN) 방식은 보통 이분 탐색과 배열을 활용하여 진행됩니다. 이 방법은 다음과 같은 과정을 통해 수행됩니다:
LIS 벡터는 배열의 길이를 관리하며, 실제로 그 자체가 LIS의 배열을 의미하지는 않습니다. 대신, 각 단계에서 증가하는 수열의 최적의 길이를 추적하는 데 사용됩니다.
- 새로운 숫자가 들어올 때마다,
이분 탐색을 통해 LIS 배열에서 이 숫자가 들어가야 할 위치를 결정하고, 그 자리에 업데이트를 합니다.
- 만약 새로운 숫자가 현재 LIS 배열의 끝보다 크다면, 바로 LIS 배열에 추가합니다.
하지만 여기서 주의할 점은 실제 수열의 순서가 아닌 최적의 길이를 추적한다는 것입니다. 이로 인해, 임의의 작은 수로 맨 처음의 원소들이 갱신될 수도 있는데, 이는 단순히 길이를 위한 최적화일 뿐, 실제 LIS 구성에는 영향을 주지 않습니다.
이 코드를 사용할 때 주의할 점:
- 최소 원소 삽입: 수열의 순서에는 영향이 없으나 LIS의 시작 구성에는 영향을 줄 수 있습니다. 따라서 순서는 따로 저장되어야 합니다.
- 동일한 길이를 가진 경우, 동일한 인덱스에서 발생할 수 있는 교체 상황을 올바르게 트래킹해야 합니다. 이는 최적해와 실제 수열을 매치시키는 데 주의해야 할 점입니다.
제가 추천드리는 것은 이미 해결된 비슷한 질문과 답에서 힌트를 얻는 것인데, 강의의 6-K 문제를 반드시 역추적하는 방법으로만 풀 수 있나요? 질문을 참고하시기 바랍니다. 여기서는 O(NlogN) 접근법에서의 일반적인 제한점을 어떻게 극복해야 하는지를 설명하고 있습니다.
더 궁금한 점이 있으시면 언제든지 추가로 질문해 주세요. 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
LIS의 앞 부분을 건들여도 상관없는거니까
->제가 LIS 벡터 자체에서 가장 긴 증가 수열을 뽑아내려고 했습니다. 그래서 문제였던 것이 가장 긴 증가 수열은 원본 수열에서 순서대로 일부 원소를 골라내어 부분 수열을 완성해야 하는데, LIS의 가장 뒷부분을 갱신하고 난 뒤에 그 원소보다 작은 원소를 lower_bound로 LIS에서 위치를 찾아 값을 덮어 씌우게 되면 순서대로 골라내서 만든 부분 수열이 아니게 됩니다. 예를 들어 3 10 2 1 20이란 수열이 있으면 LIS 3 > 3 10 > 2 10 > 1 10 > 1 10 20 이렇게 변화하게 되는데 3 10은 순서대로 골라낸 부분 수열이 맞지만 이후에 원소 2를 lower_bound로 LIS에 집어 넣어서 만든 2 10 부분 수열은 원래 수열에서 순서대로 골라낸 수열이 아니게 된다는 의미입니다. 저는 이런 상황만 방지하면 LIS를 그대로 사용할 수 있을 줄 알았는데 LIS의 앞 부분에서 이미 순서가 뒤바뀌어서 들어가면 의미가 없겠군요. 으으 항상 느끼지만 자기 생각을 글로 표현하는 건 어려운 거 같네요. 난잡한 글 읽느라 고생하셨습니다..