코딩 테스트 - 메모리 초과 / 시간 초과 (추가)

1. DP - 메모리 초과 (DP 문제인데 안 되어서 수학적인 생각을 하다가 재귀로 바꿔봄)

2. 재귀 - 시간 초과 (DP가 더 빠름...)

3. 이중 루프 - 시간 초과 (안 될 줄 알고 짜봄)

4. 탑다운 - 메모리 초과 

5. 바텀업 - 메모리 초과

6. 백트래킹 - 시간 초과 (안 될 줄 알고 짜봄)

7. Stream 써서 그런가? -> System 함수 써봄 -> Memory 접근하는 함수 써봄 -> 메모리 초과

8. Collections 써서 그런가? -> 테스트용으로 0 찍는 것 돌려봄 -> 메모리 초과

https://jemerald.tistory.com/81 

↑ 이 문제인데 대체 뭘까! 

이 블로거 분도 사실 시간 복잡도 충족 못 해서 도움이 안 되었음.

궁금해서 Javascript랑 파이썬으로도 풀어봤는데 저 1 2 3 4 5 6 의 성을 넘지 못함.

(7 8 은 없으니까...)

DP 아니면 재귀로 해결이 되는 문제인데 왜 효율성이 이랬을지 궁금하다.

* 최대값 범주로 <<<< >>>> 하는 경우에는 최대값이 들어있다고 SUM 값이 최대가 아닌 경우가 있어서 빨간 줄 뜬다! (이게 제일 빠르긴 함)

이런 느낌으로.

어쨌든 프로그래머스와의 전투에서 효율성이란 중요한 것이다...

오늘은 너무 늦어버려서 codility 테스트는 못 풀고 잔다...★

이따 오후에 두 개 풀어야지!

어쨌든 이 문제 궁금한데 정답을 좀 알려주면 좋겠다.

O(1)은 가능하지 않고... O(log n)으로 짠것도 효율적이지 않다고 하면 무엇이 답인지 궁금하다.

이거 문제가 어렵지 않은 건데 시간 복잡도를 체크를 아무리 해봐도 툴을 돌려봐도

O(log n)이었는데 ... 왜지...

메모리를 더 좋은걸 쓰세용 (?) 이라는 얍삽한 결론