검색 알고리즘의 일종입니다.
글쓴이: gizrak / 작성시간: 토, 2004/03/20 - 3:34오후
이건 책에 나온 문제인데 혼자서 생각해봐도 맞는지 말 몰라서 이렇게 올려 봅니다.
n개의 숫자를 가진 배열 S가 있는데 거기서 가장 작은 수와 가장 큰 수를 찾는 알고리즘 입니다. 매우 간단하죠.
그런데 문제는 배열의 아이템을 비교하는데 최대 1.5n만의 비교를 사용하라는 것입니다.
만약 앞에서부터 순차검색으로 제일작은 수를 찾으면 n번의 비교를 하고 다시 가장 큰 수를 찾으면 또 n번... 그럼 2n번이 되겠죠?
그래서 저는 한번의 루프로 두가지를 찾아버리는 방법으로 만들어 보았는데 좀 긴가민가 하군요.
int edgeSearch(int n, const S[])
{
int smallest, largest; // output data
smallest = S[0]; // set S[0] to smallest number
largest = S[1]; // set S[1] to largest number
// verify which number is large
if((largest-smallest) < 0) {
smallest = S[1];
largest = S[0];
}
// compare numbers with largest and smallest
for(i=2 ; i<n ; i++) {
if(S[i] > largest) // find larger one
largest = S[i];
else if(S[i] < smallest) // find smaller one
smallest = S[i];
}
return 0; // program return
}
더 깔끔한 방법이 있으신분?
Forums:
그렇게 쓰셔도 2n입니다. -_-;루프가 n번 돈다고 n인게 아니고요
그렇게 쓰셔도 2n입니다. -_-;
루프가 n번 돈다고 n인게 아니고요.
n번 돌아도 그 안에서 2번 돌면 2n이죠.
방법은요.
처음엔 배열 전체를 둘씩둘씩 짝지어서 큰쪽과 작은쪽으로 나눕니다.
( 둘씩 묶어서 가위바위보 하듯이요. -_-a )
그러면 비교횟수 n/2회만에 큰쪽 n/2, 작은쪽 n/2로 나뉘죠.
이후 큰쪽 그룹에서 최대값을, (비교횟수 n/2)
작은쪽 그룹에서 최소값을 (비교횟수 n/2)
각각 구하시면 됩니다.
이렇게 하면 3n/2 만에 최대값 최소값을 구할 수 있게 되죠.
[quote="vacancy"]그렇게 쓰셔도 2n입니다. -_-;루프
아... 그런 방법이 있군요! 고맙습니다. ^^;
그런데 제 방법의 경우에 만약 위의 if문이 참일경우 아래 else if문이 실행되지 않을테니 평균적으로 n보다 크고 2n보다 작은 값이 나올 것이란 생각에 만든 것이거든요.
그런데 2n이 나오나요? 먼저나온 if문의 여부에 따라 1번만 비교하는것 아닌가요?
void main(void)
{
char *brain;
brain = malloc(sizeof(stress));
free(brain);
}
뭐든지 답은 간단한데서 시작한다.
Time Complexity를 계산할 때는 대개,Worst case를
Time Complexity를 계산할 때는 대개,
Worst case를 전제로 해서 세는데요.
처음 수가 최대값이 나와버리면,
이후에는 매회 무조건 두 차례의 비교를 다 하게 됩니다.
( 그렇지 않더라도 최대값이 1/2 확률로 경신되는 경우는 드물죠. )
따라서 2n이라고 보는 것이 맞는 것 같네요.
그리고 함수 자체에도 한가지 문제가 있는데,
n = 1 인 경우 작동하지 않을 것 같습니다. ;;
[quote="vacancy"]Time Complexity를 계산할 때는
아... 그렇군요... 제 생각이 짧았습니다.
그리고 n값이 1일 경우에 동작하지 않는다는 커다란 버그까지... 정말 고맙습니다. ^^;
void main(void)
{
char *brain;
brain = malloc(sizeof(stress));
free(brain);
}
뭐든지 답은 간단한데서 시작한다.
제가 다시한번 짜 보았습니다.
가르쳐 주신 방법대로 해보려고 코드를 짜 보았습니다. 그런데 배열의 요소가 짝수나 홀수냐 일때도 따로 구현해야 하더군요.
일단 다음과 같습니다...
int divideSearch(int n, int S[]) { int major[], minor[]; // two sub array int largest, smallest; // variable for result if(n%2 == 0) { // if even elements // divide major and minor array for(int i=0 ; i<n ; i=i+2) { if(S[i] > S[i+1]) { major[i] = S[i]; minor[i] = S[i+1]; } else { major[i] = S[i+1]; minor[i] = S[i]; } } } else { // if odd elements // divide major and minor array for(int i=0 ; i<n-1 ; i=i+2) { if(S[i] > S[i+1]) { major[i] = S[i]; minor[i] = S[i+1]; } else { major[i] = S[i+1]; minor[i] = S[i]; } } major[n/2] = S[n-1]; // put more element into major array } // get largest number in the major array largest = major[0]; for(int i=1 ; i<n/2 ; i++) { if(major[i] > largest) largest = major[i]; } // get smallest number in the minor array smallest = minor[0]; for(int i=1 ; i<n/2 ; i++) { if(minor[i] < smallest) smallest = minor[i]; } return 0; }뭐 그냥 대는대로 급하게 짠 코드인데 정확하게 돌아갈지는 모르겠군요. 일단 코드 내용은 맞을까요?
void main(void)
{
char *brain;
brain = malloc(sizeof(stress));
free(brain);
}
뭐든지 답은 간단한데서 시작한다.
흐 돌려보시면 알지 않을까요. -_-;눈으로 돌려보는데는 한계가
흐 돌려보시면 알지 않을까요. -_-;
눈으로 돌려보는데는 한계가 .. ;;
댓글 달기