알고리즘 부분은 수업정도만 들었지, 다른 컴공친구들 처럼 알고리즘 공부를 집중적으로 하지는 않았기 때문에, 자신이 없었습니다.
특히 몇군대 알고리즘 예선전 문제의 난이도를 보고 더 자신감이 떨어지기도 했습니다;
간만에 다른 알고리즘 예제 문제를 하나 접하게 되었는데, 속으로 그다지 어렵지 않아보이는데? 와 js도 지원하네? 로 인해 한문제를 풀어보게 되었습니다.
문제자체는간단했습니다.
integer로 이루어진 array에서 중복되는 숫자가 있는지를 검출하는 내용이었습니다.
아무생각없이 이터레이터 방식으로 처음에 해결을 하였으나..
(효율성 테스트에서 형편없다는 문제점을 받게되었습니다.)
이제 슬슬 오기가 붙어서, 재귀적으로..
(삽질을 시작했으나...정확성 테스트에서 한가지가 계속해서 런타임 fail로 실패를 당합니다..)
지금생각하면 당연한 문제인데도 불구하고, 다른 오류(int가 아니다거나) 검출을 실수했나 싶어 한참을 찾았습니다만..크흣..
마침내, 많은 테스트 케이스가 문제가 아닐까 라는 추측에 마침내 도달했고, 가이드라인에 따라 10만개의 array를 만들어 테스트를 돌려봤습니다..
(예상은 했지만 막상 닥쳐보니 눈앞이 깜깜..)
분할정복법을 이용해 만든 재귀함수인데, 10만 이라하면 함수호출이.. 두번째 식에 따라선 으음..nlogn이니깐.. 최소 5만?번은 더 호출이 되야했기 때문에.. 이러한 문제가 발생한다는것을 꺠달습니다 -_-
(미친듯이 함수 호출이 찍혔지만, 재귀로 인해 끝나지 않기에, 가비지 컬렉트가 안되어 지옥이 발생!)
여기서 고민과 검색을 좀 했는데, 지금 당장 제 수준에서는 어떻게 이 재귀함수를 오버플로 없이 해결 할지 감이 오지 않습니다..
힙 메모리가 일정 수준이고, 비교할 array가 기대치보다 높다면 그냥 이터레이션으로 할까? 하는 좀 멍청한 생각도 났기 때문에, 검색을 좀 해봤는데 :
함수를 몇개 호출하는지 따위의 제한을 둘 수가 없는게, 해당 함수가 얼마만큼의 메모리를 할당하느냐, 해당 클라이언트에 얼마만큼의 메모리를 힙으로 쓰느냐를 비교해야 하기때문에, 이것도 영...아니다 라는 생각에 포기했습니다.
그래서 궁여지책 끝에, 분할정복을 하는 기준을 높여, 함수 호출의 수를 줄여보는게 어떨까에 도달..
이전의 경우에는, 검사할 array의 index가 3 이상이면 분할정복을 했었기 때문에,
이 값을 5로 올려보았습니다.
if(array.length >= 5 )
devideNconquer(left)
devideNconquer(right)
당연하게도 이렇게 함으로써 함수 호출은 극적으로 줄어들게 되었고 -_-
정확성 테스트와 효율성 테스트에서 이전보다 나은 점수를 얻게 됩니다...
하지만 아직도 대부분의 효율성 테스트에서는 구동조차 실패했기 떄문에, 어떻게든 손은 더 봐야 할거 같습니다..
간만에 다시 컴공으로 알고리즘 공부만 파는애들에게 경외심이 드는 하루 -_-...
저런애들을 어떻게 이겨...
