2007/08/09 01:22 :: 개발자로의 생각/알고리즘
이에 대한 원래 문제는 http://minjang.egloos.com/1392478 여기서 확인할 수 있다.
간단히 문제를 설명하자면...
그런데 정렬이 되지 않은 상태에서는 아무리 생각해봐도 space의 O(1) 은 불가능해보인다.
space O(N)의 경우를 생각해보면 답이 혹시 나올 가능성이 있지 않을까 해서, 인터넷도 좀 뒤지고 이리 저리 조금 생각해서 코딩해보았더니 대략 이렇게 나오긴 한데...
이러면 bitset의 크기는 sum 에 따라 space가 좌우된다. 사실 최선인지도 모르겠지만
문제는 제시하는 이상적인 솔루션은 아니라는 것이다. 물론 정렬되어 있다는 가정 내에서는 sum 과 양쪽 끝 포인터에서의 합을 가지고 비교하면서 포인터를 이동해나가는 솔루션으로 하면 해결할 수 있다.
어떻게 생각해보면 두 개 값의 다양한 조합을 체크하는데 있어 O(1) 의 space를 쓰는게 불가능하지
않나 싶다. O(N^2)을 제외하고 말이다. 증명은 실력 문제로 안되지만 결국 sort 의 문제와 비슷한 이유로
결국은 안되지 않나 하는 생각이 들긴 한다.
간단히 문제를 설명하자면...
정수 배열이 있고, 여기에 두 수의 합이 특정한 숫자가 되는지를 판별을 해야 한다. 예를 들어:인데, 이에 대한 솔루션 알고리즘은 아주 무식하게는 O(N^2) 이거나 또는 space complexity O(N), time complexity O(N) 이 될 수 있다. 하지만 요구하는건 space 는 O(1), time은 O(N) 이다.
int a[] = {4, 7, 1, 10, 9};
가 있다고 하고, 14를 줬다고 하자. 그러면 이 경우엔 10과 4가 있으므로 만족한다. 그러나 30을 주었을 경우에는 30이 되는 두 정수의 조합이 없으므로 실패를 반환한다.
그런데 정렬이 되지 않은 상태에서는 아무리 생각해봐도 space의 O(1) 은 불가능해보인다.
space O(N)의 경우를 생각해보면 답이 혹시 나올 가능성이 있지 않을까 해서, 인터넷도 좀 뒤지고 이리 저리 조금 생각해서 코딩해보았더니 대략 이렇게 나오긴 한데...
이러면 bitset의 크기는 sum 에 따라 space가 좌우된다. 사실 최선인지도 모르겠지만
문제는 제시하는 이상적인 솔루션은 아니라는 것이다. 물론 정렬되어 있다는 가정 내에서는 sum 과 양쪽 끝 포인터에서의 합을 가지고 비교하면서 포인터를 이동해나가는 솔루션으로 하면 해결할 수 있다.
어떻게 생각해보면 두 개 값의 다양한 조합을 체크하는데 있어 O(1) 의 space를 쓰는게 불가능하지
않나 싶다. O(N^2)을 제외하고 말이다. 증명은 실력 문제로 안되지만 결국 sort 의 문제와 비슷한 이유로
결국은 안되지 않나 하는 생각이 들긴 한다.
이올린에 북마크하기
이올린에 추천하기'개발자로의 생각 > 알고리즘' 카테고리의 다른 글
| "어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?" 에 대한 끄적거린 생각 (4) | 2007/08/09 |
|---|---|
| ACM 100 - 3n+1 Problem (3) | 2006/10/27 |
이 글의 관련글(Trackback) 주소 :: http://snaiper.tistory.com/trackback/250
