프레젠테이션에도 나와있지만 OSPF는 라우터에서 쓰는 기법입니다.

Dijkstra 알고리즘을 이용해 가상 시뮬레이션을 구현해보았습니다.

지금 생각해보면 이때가 가장 즐거웠지 않을까 싶습니다.

시간은 촉박했지만, 정말 생각해볼 수 있는 여러가지를 응용해봤거든요.

잘 쓰지는 않지만 Vector 라든지, 인접리스트, 우선순위 큐 등등

Data structure쪽은 뇌자알을 많이 참고했습니다.

이 자리를 빌어 책의 저자님께 감사의 메세지를.

씬횽 땡큐 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

중간고사만 잘 봤어도 A+일텐데 ㅠㅠ

세종대학교 2009년 2학기 송오영교수님의 알고리즘 수업의 기말 과제로 제출되었습니다.

행여나 이 과제를 베껴서 얻는 피해를 저에게 따지지 마세요.

프로그램은 여기서 공개하고

소스는 따로 정리해서 올릴 생각입니다.
Posted by Yria

댓글을 달아 주세요

  1. 참 잘했어요 ^^

    2010.09.29 13:50 [ ADDR : EDIT/ DEL : REPLY ]
    • 오오 씬횽이 집적 나타나다니!

      덕분에 알고 시험&프로젝트 잘 봤음 흐흐

      2010.10.06 23:36 신고 [ ADDR : EDIT/ DEL ]



제목 그대로 삼각함수를 이용한 영상처리 인코딩 알고리즘입니다.

조잡해 보일진 몰라도 아이디어 짜내느라 머리가 터지는줄 알았음 ㅠㅠ

이건 제가 생각해낸 인코딩 알고리즘 아이디어입니다.

혹시나 어딘가에 똑같은 자료가 있을지 모르지만 전 그런거 모릅니다.

아이디어부터 개발까지 제 손으로 한거거든요.

세종대학교 2010년 1학기 프로그래밍 언어의 개념 수업 기말과제로 제출한 프로젝트이며

저작권은 저에게 있으나 개인이나 단체의 영리로 사용되지 않는다면 누구나 읽을 수 있습니다.

오픈되어 있기 때문에 여러분들이 검색해서 과제로 낸다 하더라도 교수님 또는 조교님이 금방 찾을 수 있습니다.

그러니까 참고만 하세요.
Posted by Yria

댓글을 달아 주세요

프로그래밍/C/C++2010.01.13 20:57

#include 
#include 

void main(){

	int i, j;
	printf("2~200 사이에 있는 모든 소수 출력\n");

	for (i=2; i<=200; ++i){
		for(j=(int)sqrt((double)i); j<=i; ++j){
			if(i==j || i==2 || i==3){
				printf("%d, ",i);
			}
			if(i%j==0){
				break;
			}

		}
	}
	printf("\n"); 
}


코드 자체는 별거 없다. for문이 두개가 돌면서 i는 소수인지 아닌지 확인하려는 숫자, j는 그걸 확인하기 위한 값이다.

소수라 함은 자기자신으로만 나누어 떨어지는 수를 말하며 그렇기 때문에 소수인지 아닌지 확인하는 j값이 i값과 같은 크기일때까지만 커지면 된다.

또한 자기자신외에 다른 숫자로 나누었을시 나누어 떨어지면 이 숫자는 소수가 아니기 때문에 더이상 j값을 증가시킬 필요가 없다.

그런데 여기서, 숫자는 제곱근을 기준으로 대칭형의 곱셈형식으로 나타낼 수 있다.

예를 들어 12의 경우 1*12, 2*6, 3*4, 4*3, 6*2, 12*1 같이 대칭형을 이룸을 알 수 있다.

그렇기 때문에 원하는 숫자의 제곱근까지 확인하면, 그 이상은 확인하지 않아도 알 수 있기 때문에 제곱근함수(sqrt)를 사용하여 더욱 단축할 수 있다.

소스에서는 제곱근부터 시작하여 소수인지 확인하려는 숫자 i와 그걸 확인하기 위한 숫자 j가 같을때 출력하도록 짜보았다.

시간 복잡도 상으로는 O(n^2) 가 되겠지만 실제로 두번째 for는 검사하려는 숫자의 제곱근부터 검사하기 때문에 평군시간복잡도를 구하면 O(n^2)보다 떨어질것이라 추측한다.



이 외에도 에라토스테네스의 체를 이용하는 방법이 있다.

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
  2. 2는 소수이므로 오른쪽에 2를 쓴다.
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과


이를 이용하면 더욱 빨리 구할 수 있다.

웹에서 다른사람이 만든 코드를 인용하겠다.

#void eratosthenes(int *iPrimes, long long *lSum)
{
    bool *bNoPrime = new bool[PRIMES];
    lSum = 0;
    iPrimes = 0;
    int iMaxCompare = (int)sqrt((double)PRIMES);

    memset(bNoPrime, 0, sizeof(bool)*PRIMES);

    int i;
    for (i=2; i<=iMaxCompare; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }

        for (int j=i*i; j<PRIMES; j+=i) bNoPrime[j] = true;
    }

    for (i=iMaxCompare+1; i<PRIMES; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }
    }

    delete bNoPrime;
}
Posted by Yria

댓글을 달아 주세요