jeen0112   2년 전

이 코드는 왜 안되죠?? 가장 긴 증가하는 부분 수열 2,3은 아래 코드 응용해서 되는데 밑에 작성된 건 거기다가 배열도 같이 출력하라해서 출력문 만들었는데 안되는 이유가 있을까요

dk10211   2년 전

자바 컴파일 할 줄 모르지만 

5

1 10 100 1000 5

가 입력으로 들어온다면 답은 

4

1 10 100 1000 이지만

해당 코드는 아마도

4

1 5 100 1000 을 출력하겠죠?

추가로 설명을 하자면 어떠한 수열의 LIS가 k일때 항상 그 이전에는 k-1이 존재합니다. 그 k-1에서 앞의 원소를 탐색하다 보면 또 k-2를 찾고 이런 식으로 계속 탐색하다 보면 O(n)에 역추적이 가능해요.

하지만 arr에 있는 원소는 size부터 역추적을 하는 것은 가능하지만 1~size로 순회 할 경우 꼭 맞는 순서란 법은 없습니다.

그 이유는 이분 탐색으로 i에 삽입을 한다고 가정할 때 당연하게도 i+1의 원소보다 뒤에 위치한 것이기 때문에 계속 반복하다 보면 당연히 순서가 엉키게 됩니다.

댓글을 작성하려면 로그인해야 합니다.