[CH08] LIS - Githubissues

wbluke / Algorithm_PS

Algorithmic Problem Solving Strategies

https://algospot.com/

0 stars 0 forks source link

[CH08] LIS #10

Closed wbluke closed 5 years ago

wbluke commented 5 years ago

https://algospot.com/judge/problem/read/LIS

APSS_p230

wbluke commented 5 years ago

[My Point]

vector를 사용하여 findLIS()를 구현하고, 재귀호출하려했으나 구체적인 로직이 잡히질 않아서 틀만 만들고 stop.

[Idea Point]

현재 인덱스 이후로 큰수들만 모아서 배열 생성 : 완전탐색
현재 인덱스에서 시작하는 부분증가수열 중 최대 길이 : 동적계획법

wbluke commented 5 years ago

[My Point]

책 코드에는 수열 최대길이가 100으로 잡혀있길래 그런줄 알았지...... 테스트 케이스 다 맞는 코드를 맞왜틀하면서 제출 7번만에 문제는 500이란 것을 깨달았다. 미워요. 오늘의 교훈. 수도코드를 믿지마세요.

[Idea Point]

main에서 함수 호출 시 start 인덱스를 반복문 돌려주기 귀찮음으로 인해, -1이라는 인덱스를 놓고 S[-1] <= 0이라 가정한 후에 호출해주면, 자동으로 모든 인덱스를 가지고 비교하게 된다. 캐시도 사이즈를 하나 늘려서 잡는다.
이 알고리즘은 O(N^2) 복잡도를 갖는데, 이분탐색을 이용한 O(N*logN) 복잡도를 갖는 알고리즘이 존재한다. 블로깅 예정.