검색 알고리즘의 일종입니다.

gizrak의 이미지

이건 책에 나온 문제인데 혼자서 생각해봐도 맞는지 말 몰라서 이렇게 올려 봅니다.

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
}

더 깔끔한 방법이 있으신분? 
vacancy의 이미지

그렇게 쓰셔도 2n입니다. -_-;
루프가 n번 돈다고 n인게 아니고요.
n번 돌아도 그 안에서 2번 돌면 2n이죠.

방법은요.
처음엔 배열 전체를 둘씩둘씩 짝지어서 큰쪽과 작은쪽으로 나눕니다.
( 둘씩 묶어서 가위바위보 하듯이요. -_-a )
그러면 비교횟수 n/2회만에 큰쪽 n/2, 작은쪽 n/2로 나뉘죠.

이후 큰쪽 그룹에서 최대값을, (비교횟수 n/2)
작은쪽 그룹에서 최소값을 (비교횟수 n/2)
각각 구하시면 됩니다.

이렇게 하면 3n/2 만에 최대값 최소값을 구할 수 있게 되죠.

gizrak의 이미지

vacancy wrote:
그렇게 쓰셔도 2n입니다. -_-;
루프가 n번 돈다고 n인게 아니고요.
n번 돌아도 그 안에서 2번 돌면 2n이죠.

방법은요.
처음엔 배열 전체를 둘씩둘씩 짝지어서 큰쪽과 작은쪽으로 나눕니다.
( 둘씩 묶어서 가위바위보 하듯이요. -_-a )
그러면 비교횟수 n/2회만에 큰쪽 n/2, 작은쪽 n/2로 나뉘죠.

이후 큰쪽 그룹에서 최대값을, (비교횟수 n/2)
작은쪽 그룹에서 최소값을 (비교횟수 n/2)
각각 구하시면 됩니다.

이렇게 하면 3n/2 만에 최대값 최소값을 구할 수 있게 되죠.

아... 그런 방법이 있군요! 고맙습니다. ^^;

그런데 제 방법의 경우에 만약 위의 if문이 참일경우 아래 else if문이 실행되지 않을테니 평균적으로 n보다 크고 2n보다 작은 값이 나올 것이란 생각에 만든 것이거든요.

그런데 2n이 나오나요? 먼저나온 if문의 여부에 따라 1번만 비교하는것 아닌가요?

void main(void)
{
char *brain;
brain = malloc(sizeof(stress));

free(brain);
}
뭐든지 답은 간단한데서 시작한다.

vacancy의 이미지

Time Complexity를 계산할 때는 대개,
Worst case를 전제로 해서 세는데요.

처음 수가 최대값이 나와버리면,
이후에는 매회 무조건 두 차례의 비교를 다 하게 됩니다.
( 그렇지 않더라도 최대값이 1/2 확률로 경신되는 경우는 드물죠. )
따라서 2n이라고 보는 것이 맞는 것 같네요.

그리고 함수 자체에도 한가지 문제가 있는데,
n = 1 인 경우 작동하지 않을 것 같습니다. ;;

gizrak의 이미지

vacancy wrote:
Time Complexity를 계산할 때는 대개,
Worst case를 전제로 해서 세는데요.

처음 수가 최대값이 나와버리면,
이후에는 매회 무조건 두 차례의 비교를 다 하게 됩니다.
( 그렇지 않더라도 최대값이 1/2 확률로 경신되는 경우는 드물죠. )
따라서 2n이라고 보는 것이 맞는 것 같네요.

그리고 함수 자체에도 한가지 문제가 있는데,
n = 1 인 경우 작동하지 않을 것 같습니다. ;;

아... 그렇군요... 제 생각이 짧았습니다.

그리고 n값이 1일 경우에 동작하지 않는다는 커다란 버그까지... 정말 고맙습니다. ^^;

void main(void)
{
char *brain;
brain = malloc(sizeof(stress));

free(brain);
}
뭐든지 답은 간단한데서 시작한다.

gizrak의 이미지

가르쳐 주신 방법대로 해보려고 코드를 짜 보았습니다. 그런데 배열의 요소가 짝수나 홀수냐 일때도 따로 구현해야 하더군요.

일단 다음과 같습니다...

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);
}
뭐든지 답은 간단한데서 시작한다.

vacancy의 이미지

흐 돌려보시면 알지 않을까요. -_-;

눈으로 돌려보는데는 한계가 .. ;;

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.