|
문제를 쓰기도 간단치 않다. 간단하게 다시 설명하면, 정수 배열이 있고, 여기에 두 수의 합이 특정한 숫자가 되는지를 판별을 해야 한다. 예를 들어:
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) 공간을 이용해서 두 수의 합이 특정한 숫자가 되는지를 판별해보자...혹시 푸실 수 있으신 분 계시는지요? 저는 이런 쪽 알고리즘은 무척 싫어해서 잘 모르겠네요. 도와주세요~~ 이 글과 관련있는 글을 자동검색한 결과입니다 [?]
최근 등록된 덧글
이 글을 보고 온라인 알고리..
by 김정은 at 02:45 리눅스 커널도 바닐라가 있죠.. by Corund at 07/03 궁금증이 이제야 풀리네요... by 유겸애비 at 07/03 아무래도 mpeg 코덱 특성 .. by object at 07/02 그런 건 아닙니다. 논문 중에.. by object at 07/02 최근에 LCD TV를 구입해서.. by kirrie at 07/02 Supreme Commander의 .. by daybreaker at 07/02 같은 입맛을 가지셨군요... by 덤덤 at 07/02 최근 등록된 트랙백
메뉴릿
|