Develop & Dream

• 모든 정점에서 모든정점으로의 최단경로를 구할때 사용
• 경유지(거쳐가는 정점)를 기준으로 최단거리를 구함
• 다이나믹 프로그래밍(큰 문제를 작은 문제들로 나눠서 해결)을 보여줌

자료출처:https://blog.naver.com/ndb796/221234427842

아래의 표는 위그래프를 기준으로 출발지에서 목적지까지의 최소 비용을 구한 것이다, 화살표가 목적지로 정방향으로 가리키지 않거나, 중간에 경유지를 거쳐야 하는 경우(예 2 -> 4)들은 무한(값이 있긴한데 정확히 얼마나 되는지 몰라서 무수히 많은 값)으로 추정한다

따라서 위 그래프를 읽으려면, 1에서 2까지 가는 최소 비용은 5 이고

1에서 3까지 가는 비용은 화살표가 1->3 으로 나와있지 않으므로 무한이고

1에서 1 또는 2에서 2 등등 자기 자신을 향하는 경우 비용이 들지 않으므로 모두 0이다 

플로이드 와샬 알고리즘은 모든 정점을 각각 경유지(거쳐가는 정점)로 봤을때 나올 수 있는 최소비용들을 구해서

표를 갱신해 나가는 것이다

이때 이공식이 사용된다

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 + 경유지 에서 Y로 가는 비용

즉, 거쳐가는 정점을 1번부터 시작해서 4번까지 바꿔가면서, 각각의 경유지(거쳐가는 정점)마다

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한뒤 최소비용을 위의 공식에 맞춰서 갱신해 나가는 것이다 일단 1번부터 거쳐가는 정점이라고 한다면

최소비용을 갱신해야될 부분은 아래의 노란부분과 같다

위의 표의 노란부분은 

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한 나머지들이며 갱신해야될 부분이다

2->3 으로 가는 최소비용은 9인데 

경유지는 1이다

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 +'경유지'  에서 Y로 가는 비용

위의 공식을 대입 시키면

2에서 3으로 가는 최소비용 vs 2에서 1로 가는 비용 + 1에서 3으로 가는 비용

이 된다, 그대로 표를 보고 대입하면

9 vs 7 + 무한

이 된다 여기서 7+ 무한은 값이 확실하지 않으므로 결국 무한으로 추정하고

9와 비교했을때 9가 더 적다고 판단하여 9를 내버려둔다

이런식으로 갱신해 나가면 아래와 같이 된다

여기서 3->2로 가는 값이 무한에서 7로 바뀐걸 알 수 있다

3 -> 2 로 가는 비용 > (3 -> 1) + (1 -> 2)

무한 > 2 + 5

이므로 2+5 가 무한보다 적으므로, 즉 7로 바뀌었다

그뒤 1을 거치는 표를 기준으로 경유지를 1에서 2로 바꾸고 다시 갱신해준다

아래와 같을 것이다

이런식으로 계속 경유지를 바꿔가며 표를 갱신하면된다

경유지가 마지막 정점인 4인경우 표가 다 완성된다

코드

#include <iostream>

int number = 4;
int INF = 100000000;

// 자료 배열을 초기화
int a[4][4] =
{
	{0, 5, INF, 8},
	{7, 0,	9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};


void floydWarshall()
{
	int oldCost = 0;
	int newCost = 0;
	
	// 결과 그래프를 초기화
	//X에서 Y로가는 최소비용 VS X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
	for (int stopover = 0; stopover < number; stopover++) //stopover : 경유지, 거쳐가는 노드
	{
		for (int start = 0; start < number; start++)
		{
			for (int goal = 0; goal < number; goal++)
			{
				if (stopover < number&& start != goal && start != stopover && goal != stopover)
				{
					oldCost = a[start][goal]; //X에서 Y로가는 최소비용

					//X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
					newCost = a[start][stopover] + a[stopover][goal]; 
					
					//둘중에 더 적은 비용을 넣기
					a[start][goal] = oldCost > newCost ? newCost : oldCost; 
				}
			}
		}
	}
}

void PrintGraph(int (*_a)[4])
{
	for (int start = 0; start < number; start++)
	{
		for (int goal = 0; goal < number; goal++)
		{
			if (a[start][goal] == INF)
			{
				printf("INF ");
			}
			else
			{
				printf("%d ", a[start][goal]);
			}
		}
		printf("\n");
	}
	printf("\n\n");
}

int main()
{
	PrintGraph(a);

	floydWarshall();
	printf("after FloydWarshall \n");
	PrintGraph(a);
	
	return 0;
}

n번 만큼의 루프 연산이 삼겹으로 들어가므로 O(n³) 만큼의 시간복잡도를 가진다

실행결과

위에서 봤던 최종 결과 표와 일치한 결과를 볼 수 있다.

• 대량의 범위 안에서 소수들을 판별할때 사용
• 체를 쳐내듯이 합성수를 하나하나 지워나가며 소수만을 골라냄

/*
The Sieve of Erathosthenes 
에라토스테네스의 체

대량의 소수를 한꺼번에 판별할 수 있는 알고리즘

*/

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int number = 100000; //범위
int a[100001]; //수들을 넣을 배열

// 간단한 소수 판별 알고리즘
bool isPrimeNumber(int _x)
{
	int end = (int)sqrt(_x);

	for (int i = 2; i <= end; i++)
	{
		if (_x % i == 0)
		{
			return false;
		}
	}
	return true;
}

//에라토스테네스의 체
void primeNumberSieve()
{
	//초기화, 배열을 2부터 시작해서 정해진 범위까지 채워넣기
	for (int i = 2; i <= number; i++)
	{
		a[i] = i;
	}

	//합성수들을 지우기, 합성수 : 1과 자기자신 이외의 약수의 개수가 3개 이상인 자연수
	for (int i = 2; i <= number; i++)
	{
		if (a[i] == 0) //이미 지워진 수는 제외
		{
			continue;
		}
		
		for (int j = i + i; j <= number; j += i)
		{
			a[j] = 0; // 합성수들을 지우기
		}
	}

	for (int i = 2; i <= number; i++)
	{
		if (a[i] != 0) //지워진 수들을 제외하고 출력, 소수들을 출력
		{
			printf("%d ", a[i]);
		}
	}


}


int main()
{
	//printf("%d", isPrimeNumber(97));
	primeNumberSieve();
	return 0;
}

위의 코드에서 합성수들을 지우는 과정을 살펴보면

i와 j가 일정한 규칙으로 초기화가 되는데 아래와 같다

i == 2, j == 4
i == 2, j == 6
i == 2, j == 8
i == 2, j == 10
i == 2, j == 12
i == 2, j == 14
i == 2, j == 16
i == 2, j == 18

i == 3, j == 6
i == 3, j == 9
i == 3, j == 12
i == 3, j == 15
i == 3, j == 18
i == 3, j == 21
i == 3, j == 24
i == 3, j == 27
...

위처럼 2의 배수, 3의 배수 등등 어떤 소수의 배수들로 j가 초기화 되고, 그런 j들을 배열에서 지워준다

그렇게 배열에 소수만 남게 된다

참고자료 : https://blog.naver.com/ndb796/221233595886

어처구니 없는 경우는 보통, 오타로 인한 실수가 많은데, 이번에 hlsl 파일을 작성 하면서

발생한 경우다

Diffuse, Normal, Specular 샘플 파일들이 적절히 어우러진 결과가 나와야 하는데, Specular 샘플만 나오고 있다

어떠한 경고메시지나 에러메시지도 안나오고, 작성한 hlsl 파일에도 문제 없어 보였는데, 알고보니 정말 한 글자 차이로 발생한 문제였다,,,

정상 작동 화면

위에 코드를 보면 주석처리 한 코드가 실수 코드인데 자세히 보면, * 를 해야 되는데 +를 타이핑 한것이다, 아마도 글자가 너무 작아서 보이지 않았던 것 같다, 이런 경우들을 겪게 되면, 언리얼 엔진에서 Material을 만들때 마인드 맵처럼 작성하기 편하게 되어있는 시스템이, 이런 어처구니 없는 오타를 줄여주는 이점도 있는 것 같다, 이거때문에 4일을 날리다니 ㅠㅠ

언제나 에러메시지, 경고메시지도 안나오는데, 의도한 결과대로 안나온다면, 오타를 의심하자

Phong Pixel Shader를 적용했는데도 도형에 전혀 적용되지 않음

알고보니

hlsl 파일을 만들면 맨 밑에 기본으로 나오는 진입점 함수(entry point function)을 지워 주지 않음, 그래서 결국 맨 밑의 기본값 진입점 함수를 실행함, 문제는 어떠한 에러 메시지도 나오지 않아서 찾기 어려웠음, entry point function 이 2개 이상일 경우 경고 메시지가 나올법도 한데, 전혀 없었음, 다음에도 주의가 필요할 듯

정상 실행 결과

상자를 80개 모두 랜덤 값으로 생성해서 보여주는 코드 그러나

아래처럼 하나의 상자 만 보임, 80개가 보여야함

코드를 분석해보니, 80개가 생성되기는 했는데 튜토리얼 코드와는 다르게

모두 일정한 값을 보이고 있음

원인

std::mt19937 을 전달할 때는 꼭 레퍼런스로 전달해야함, 그렇지 않으면 랜덤값을 전달할 때마다, std::mt19937  내부에 있는 랜덤 값 배열 인덱스가 바뀌지 않음, 즉 같은 값만 전달이됨

std::mt19937 개체를 pass by value 로 했을경우

pass by reference

정상 실행 결과

ConstantBuffer 를 통해 오브젝트를 회전시키는 코드를 구현한뒤 실행 해봤는데

아래와 같이 오브젝트가 아예 출력되지 않았다

에러도 안발생하고 코드에 별다른 이상이 없어 보였는데

정말 어처구니 없게 209번 라인에서 한글자 차이로 발생한 것이었다 즉, VSSetConstantBuffers() 함수를 호출해야 되는데 VSGetConstantBuffer() 함수를 호출해서 벌어진 일이었다

정상 작동, 버그를 찾아내기 위해 몇시간이 걸렸지만 원인은 G 와 S 딱 한글자 오타였다는게 참;;;