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

안녕하세요 100억님 ㅎㅎ

제가 아직 lis 배열의 의미와

*lowerPos = num; 으로 바꿔주는 부분에 대해 잘 이해하지 못한 것 같습니다.

lis 배열은 그저 정답을 구하기 위한 임시적인 배열이 맞을까요?

>> 네 맞습니다. lis는 임시배열입니다.

lis는 lis를 만들어주기는 하지만 이 배열로 해당 최단거리 배열을 만들어낼 수는 없습니다. 100억님이 하신 것처럼 해당 부분이 반례가 되거든요. 빠르긴 하지만 이부분이 안 좋습니다.

*lowerPos = num;

>> 해당 부분의 자리의 요소를 num으로 바꿔준다는 의미입니다.

6

10 20 9 30 8 50

>> 자 코드디버깅을 해볼까요?

10 20

여기서. 9가 들어왔을 때 9의 최소시작점은 뭘까요? 없죠? 그래서.. 다음과 같이 됩니다.

9 20

여기서. 30이 들어왔을 때 30의 최소시작점은 뭘까요? 끝까지 가봤는데 없습니다. 그래서.. 다음과 같이 됩니다.

9 20 30

여기서. 8이 들어왔을 때 8의 최소시작점은 뭘까요? 9가 됩니다. 그래서.. 다음과 같이 됩니다.

8 20 30

그 다음에는 50이 들어오게 되서.

8 20 30 50

이런꼴이 나오게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴이에요.

lis 배열은 Longest Increasing Subsequence (가장 긴 증가하는 부분 수열)의 약자로, 해당 코드에서는 정답을 구하기 위한 임시적인 배열이 맞습니다. 이 배열은 현재까지 만들어진 가장 긴 증가하는 부분 수열을 저장하는 역할을 합니다.

알고리즘에서는 모든 수를 비교하면서 현재 수보다 작은 값을 만날 경우 lis 배열에 해당 값을 넣고, 그렇지 않을 경우에는 해당 값의 위치를 정확히 파악하여 해당 위치의 값을 갱신하고 원래 위치에 값을 저장합니다. 이렇게 하면 최종적으로 lis 배열에는 가장 긴 부분 수열이 저장되게 됩니다.

lowerPos = num; 문장은 현재 값을 저장하는 역할을 합니다. lowerPos는 현재 값(num)을 lis 배열에 삽입하기 위해서 그 값보다 작은 값들 중 가장 큰 값을 찾는 역할을 합니다. 따라서 lowerPos에 현재 값(num)을 할당하는 것은 현재 값보다 작은 값들 중 가장 작은 값을 의미합니다.

그리고 출력 값과 lis 배열이 다른 이유는, 코드에서 출력된 값은 가장 긴 부분 수열을 의미하는 것이라면, lis 배열은 수열 중 남아 있는 수들을 의미합니다. 따라서 출력 값은 가장 긴 부분 수열이지만, lis 배열은 해당 수열을 재구성했을 때 남아있는 수들을 모아둔 것입니다.

이해에 도움이 되셨기를 바랍니다! 더 궁금한 점이 있으면 언제든지 물어보세요.