4개의 댓글이 있습니다.
-
-
infoefficiency -
일단 수열이 주어져있고 빈 배열을 하나 만들어요 ㅎㅎ
(저는 벡터가 편해서 그냥 벡터라고 할께요)
일단 처음에 수열의 제일 처음값을 빈 벡터에 하나 넣어요
그리고 그다음 수열의 요소부터 끝까지 어떤 작업을 수행해주면 되요
그 작업이 뭐냐면요 ㅎㅎ
1)만약 수열에 해당하는 값이 벡터의 마지막 값보다 크다면
벡터 맨 마지막에 그냥 붙여요 ㅎㅎ
ex) 수열에 해당하는값 5
벡터값 1,3,4
그러면 그냥 벡터마지막에 5를 붙여요 ㅎㅎ
그러면 1,3,4,5가 되겠죠?2) 만약 수열에 해당하는 값이 벡터의 마지막 값보다 작다면
수열에 해당하는 값보다 큰 값 중에서 가장 작은 값과 바꾸면 되요.
ex) 수열에 해당하는 값이 4
벡터 1 3 5 6 7
그러면 4보다 가장 큰 값중 (5,6,7) 가장 작은 값은 5 이죠?
그러면 4와 5를 바꾸면 됩니다.
그러면 1,3,4,6,7이 되겠죠?여기서!! binary_search를 이용하여 그 수를 찾는것이 관건이겠죠
그 수행시간이 lgN 이라서 전체가 nlgN이 됩니다.
단 단점이 있다면, 전체 길이는 알 수 있지만LIS 구성요소는 알 수 없습니다. 왜냐하면 계속 내부를 수정해주기
때문입니다.즉 속도를 높이기 위해서 정보(?)와의 tradeoff를 한 것이라고
저는 생각하네요 ㅎㅎ혹시나 틀린점 있으면 수정해주세요 ^^
10년 전 link
-
-
-
kriii -
이런 질문이 올라왔었었네요
intoefficiency님은 질문의 의도를 잘못 파악하신것 같습니다.LIS에서 D[i] = i번째 숫자까지만 고려했을때, i번째 숫자로 끝나는 LIS의 길이 라고 하고 아마도 인덱스트리를 이용한 방법으로 LIS의 길이를 O(NlgN)만에 구할 수 있을 것인데
이제 여기에 C[i] = i번째 숫자까지만 고려했을때, i번째 숫자로 끝나는 LIS의 개수를 덧붙여서 저장하시고, 인덱스트에도 길이와 동시에 저장하시면 됩니다. 인덱스 트리 상에서 두 페어를 합칠때는
1) 길이가 같은 경우에는 길이는 그대로, 개수는 더해서 저장하면 되고,
2) 길이가 다른 경우에는 길이가 더 긴 것의 길이와 개수를 저장하면 됩니다.답은 D[i]가 LIS의 길이인 것의 C[i]의 합이 됩니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Sharifa
어떤 수열에서 LIS의 총 개수를 구하는 방법이 O(nlgn)으로 알고 있는데 어떤 방법을 쓰면 되나요?
딱히 인터넷 검색해도 잘 나오지도 않고;;
10년 전