john6014   9달 전

음.. 현재 LIS 관련 알고리즘을 3개 밖에 공부 안했는데.. 얘들은 데이터가 양수일 떄만 돌아가는 것같네요.. [ 이진탐색 , lower_bound ]

머리가 나빠서 변형해보려고 노력해도 방법이 안떠올라서...

구글링해도 전부 양수기반의 데이터로만 테스트해놧고.. ㅠ

음수 양수 혼용되어도 작동하는 LIS 알고리즘이 있나요?

ntopia   9달 전

정확히 구현했다면 양수 음수 상관없이 동작해야합니다

namnamseo   9달 전

이진탐색이나 lower_bound를 쓸 때, 그 값을 인덱스로 쓰지 않고 그 위치를 인덱스로 쓰지 않나요?

john6014   9달 전

네 위치를 인덱스로 사용하다보니 도중에 음수 데이터가 들어오면 값이 뒤틀려버리더라구요 그래서 질문해봤어요 ㅋㅋ

koosaga   9달 전

증가 관계만 따지니까, 만약에 음수가 입력으로 주어지면 모든 수에다가 최솟값을 빼주고 똑같이 계산하면 됩니다.

예를 들어 -1 -2 -3 -4 -5에서 LIS와 4 3 2 1 0에서의 LIS는 일대일 대응됩니다.


다만 저런걸 굳이 안 해도 대부분의 구현에서 음수 때문에 문제가 생길 일은 없을텐데..

john6014   9달 전

아 잘못 이해했군요... lower_bound 사용해서 LIS 배열에 저장되는 값이 바로 최장 증가수열 요소인줄알앗네요 ㅎㅎ

감사들합니다

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