art.oriented : 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?

minjang.egloos.com

소개 · 이전글 · 구독

컴퓨터 · 그리고 · 나머지

문제를 쓰기도 간단치 않다. 간단하게 다시 설명하면, 정수 배열이 있고, 여기에 두 수의 합이 특정한 숫자가 되는지를 판별을 해야 한다. 예를 들어:

int a[] = {4, 7, 1, 10, 9};

가 있다고 하고, 14를 줬다고 하자. 그러면 이 경우엔 10과 4가 있으므로 만족한다. 그러나 30을 주었을 경우에는 30이 되는 두 정수의 조합이 없으므로 실패를 반환한다.

아주 무식하게 O(n^2) 알고리즘으로 for 두 번을 돌리면 간단하게 확인을 할 수 있다. 그러나 O(n)을 만드는 것은 그렇게 쉽지가 않다. 일단, map이나 hash 자료구조를 이용한다면 O(n) 공간을 쓰는 대가로 O(n) 시간에 풀 수 있다. 비교적 알고리즘이 간단하므로 코드는 적지 않는다. 그렇다면 별도의 자료구조도 사용하지 않고, 즉 O(1) 공간을 쓰면서 O(n) 시간에 풀 수 있는 방법이 있을까?

만약 배열이 전혀 정렬이 되지 않았다면 O(n)으로 푸는 것은 불가능한 것 같고, 주어진 조건이 정렬이 되어있다고 가정해보자. 그러니까:

int a[] = {1, 4, 7, 9, 10};

과 같이 정렬이 되어 있고 여기에서 O(n) 시간과 O(1) 공간을 이용해서 두 수의 합이 특정한 숫자가 되는지를 판별해보자...

혹시 푸실 수 있으신 분 계시는지요? 저는 이런 쪽 알고리즘은 무척 싫어해서 잘 모르겠네요. 도와주세요~~

알고리즘싫어

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

[C 프로그래머가 알아야 할 것들] 자료 구조 | (엘키) [퍼옴] by 사랑아빠
데이터 압축에 쓰인다는(?) 허프만 코드... Huffman code by sakuragi

# by object | 2007/08/08 04:29 | 컴퓨터 | 트랙백(4) | 핑백(3) | 덧글(10)

트랙백 주소 : http://minjang.egloos.com/tb/1392478
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

Tracked from IdeA thinKIN.. at 2007/08/08 08:40

제목 : 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있..
art.oriented에 올라온 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?라는 글의 트랙백입니다. 코드가 비교적 단순해서 코드만 보시면 어떤 방법인지 아실 수 있습니다. 실행 파일을 ......more

Tracked from [天狼]™ Log 남기기 at 2007/08/08 11:19

제목 : 간단한 이글루 스킨 변경 - CSS
트래백 : 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?먼저 이 문제를 풀기 위한 트래백은 아닙니다! 이글루에서 인용문을 쓸경우 스킨에 따라서 효과가 있는데 지금 쓰는 스킨에는 들여쓴 것 이외에 표시가 없어서 한번 바꿔봐야지 라는 생각만 가지고 있었습니다. 그러다가 트랙백 글을 읽다가 CSS를 바꿔보면 쉽게 되겠구나. 라는 생각이 들었습니다. 문제 풀 생각이 전혀 없었습니다. ㅠㅠCSS 설명한 사이트를 한번 구글에게 검색 시켰더니 [......more

Tracked from 애니와 프로그래밍 at 2007/08/08 15:22

제목 : 수열의 어떤 두 정수의 합이 주어진 숫자가 되는 경..
트랙백: 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가? - object 님일단 문제는, 다음과 같이 정렬된 임의의 숫자 배열있다고 할 때...int a[] = {1, 4, 7, 9, 10};여기에 어떤 정수 n 이 주어졌다고 할때, 배열 내의 두 정수의 합이 n이 되는 경우가 있는지 판별하는 겁니다.가령 n = 19라고 하면, 9 + 10 = 19 이므로 참(true) 입니다.뭐, 자세한 내용은 트랙백된 주소를 따라......more

Tracked from at 2007/08/08 20:30

제목 : 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있..
int a[] = {1, 4, 7, 9, 10};...more

Linked at IdeA thinKING v2.. at 2007/08/08 08:40

... 8 Aug, 2007 Programming art.oriented에 올라온 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?라는 글의 트랙백입니다. 코드가 비교적 단순해서 코드만 보시면 어떤 방법인지 아실 수 있습니다. 실행 파일을 만들 수 있는 전체 코드입니다. &nbs ... more

Linked at [天狼]™ Log 남기기 : .. at 2007/08/08 11:19

... 트래백 : 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?먼저 이 문제를 풀기 위한 트래백은 아닙니다! 이글루에서 인용문을 쓸경우 스킨에 따라서 효과가 있는데 지금 쓰는 스킨에는 들여쓴 것 이외에 표 ... more

Linked at 애니와 프로그래밍 : 수열의 .. at 2007/08/08 15:21

... 트랙백: 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가? - object 님일단 문제는, 다음과 같이 정렬된 임의의 숫자 배열있다고 할 때...int a[] = {1, 4, 7, 9, 10 ... more

Commented by jaygarl at 2007/08/08 06:19

a 배열이 수열이라면 풀 수 있을꺼 같은데..수열이 아니네요..
예를 들어 10을 선택했을때, 바로 10이랑 조합될 수 있는 수가 배열에 있는지 여부를 한번에 알아내야 하고, 알아냈다 하더라도 써칭 없이 한번에 포인팅 가능해야 하므로...
소팅된 숫자 배열의 규칙이 있던가 다른 자료구조를 쓰던가 해야할듯..
맞나요? 긁적...

Commented at 2007/08/08 07:31

비공개 덧글입니다.

Commented by ㄹㄹㄹㄹ at 2007/08/08 10:18

목적에 맞는 알고리즘인진 모르겠지만 (지금 밤을 새서..) Introduction to Algorithms책 후반부에 Subset-sum algorithm이 있습니다. 이것은 배열 전체의 모든 부분집합의 합을 대상으로 하는 알고리즘이구요, 기본적으로는 NP인데 정확도를 조금 희생해서 근사적 방법을 사용하면 n이었던가 n log n이었던가.. 아무튼 금방 답이 나옵니다.

Commented by object at 2007/08/08 10:53

사실 O(n)은 k*O(n)도 포함이 되기 때문에 아주 한 번만 딱 돌아아하는 것은 아닙니다. 답변들 감사합니다. 저도 지금 생각을 해보고 있습니다 ㅎㅎ

Commented by hoonja at 2007/08/08 12:00

정렬되어 있다면, 배열의 맨 앞과, 맨뒤를 합해서 원하는 값(14)와 매칭되는 지 확인하고 크냐 작으냐에 따라 인덱스를 하나씩 이동하면 될 것 같습니다. 즉, 합의 작은 경우에는 앞의 인덱스를 증가 시키고, 큰 경우에는 뒤쪽의 인덱스를 감소 시키는 것이죠. 그럼, O(n)으로 가능하지 않을까요? (근데, 내가 O표기법을 제대로 이해는 하고 있는 건가..ㅡ.ㅡ;; )

Commented at 2007/08/08 13:24

비공개 덧글입니다.

Commented by 시즈하 at 2007/08/08 14:25

그런데, 만일 {1, 3, 4, 7, 9, 10} 로 있을 때, 13의 조합을 찾는다고 하면, {3, 10}, {4, 9} 2개가 나올 수 있는데, 이런 경우에 대해서는 어떻게 처리해야 하는 거죠?

Commented by object at 2007/08/08 14:45

여러개 나오는 것은 상관이 없습니다. 아무거나 하나만 있는지만 알면 됩니다. 저도 몇 분들께서 올려주신 방법으로 생각했었는데 이걸로 안되는 경우가 있었거든요.. 흠.. 좀 더 생각해봐야겠네요.

Commented by object at 2007/08/10 03:41

많은 분들이 도움 주셔서 감사합니다. 나중에 완벽히 정리해서 다시 올리겠습니다. 정말로 감사합니다.

Commented by rain at 2007/11/22 09:37

bool findMatchSum(int arr[], int count, int num) {
int i = 0;
while (i != count) {
if (arr[i] + arr[count] > num) count--;
else if (arr[i] + arr[count] < num) i++;
else return TRUE;
}
return FALSE;
}
hoonja님 생각과 같네요^^