52일차. BruteForce, Depth_first

서울게임아카데미 교육과정 6개월 C++ ~ DirectX2D

52일차. BruteForce, Depth_first_search

WDmil 2023. 7. 4. 00:10

728x90

BruteForce

무차별 대입법(BruteForce) 은 완전탐색 알고리즘 으로, 가능한 모든 경우의 수를 전부 탐색하여

정확한 해답을 찾는 방법이다. 이 방법은 모든 가능한 조합을 검사하기 때문에, 시간이 오래걸림으로

큰 입력값, 매우 넓은 범위를 탐색하는것 에 대해서는 매우 비효율적이다.

그러나, 직관적인 방식으로 탐색하기 때문에 쉽게 문제를 해결할 수 있다.

다음은 BruteForce를 구현한 알고리즘으로, 10개의 숫자중 8개의 숫자를 더했을 때 100이 나오는 경우를 구하는 코드 이다.

#include <iostream>
#include <list>

using namespace std;

// 무식하게 탐색한다.
// 완전탐색 알고리즘.
// 모든 경우의 수를 전부 탐색한다.
// 백트래킹 = 의미없는 경우는 제외하고 전부 탐색한다.
// 진행하는게 의미없는 조건을 찾아야 한다.

// 제외해줘야 하기 때문에 처리 자체가 불가능 해질 수 있다.

/*
	10개의 숫자가 있다.
	7 15 21 8 14 25 10 11 17 5

	이 중 숫자가 딱 100이 되는 8개의 숫자 찾기
	예외처리 해주면서,
	어떻게 해줘야 최대한 이 반복문을 줄일 수 있는지 생각해보기.

	의미 없는 경우
	
	배열은 먼저 sort한 뒤, 작은숫자대로 더한다.
	그러나 남은 덧셈 수가 남아있는수 보다 작을 경우 의미가 없기 때문에 전 수는 빼낸다.
	빼낸 뒤 나머지를 덧셈 해준다.

	왼쪽부터 오른쪽까지 다 계산해야한다.

	왼쪽부터 다 더하면서 가다가 결과가 안나왔을 시 전 것을 빼고 바로 다음꺼를 더해서 계산

	순방향 정렬을 한 뒤 완전탐색을 시도하였을 경우,
	임의의 모든 값을 순환시키는것 보다 약 O^n/2 만큼 더 줄어들 수 있다.

*/

auto Chack_dup(int arr[] ,int size ,int a) -> bool
{
	for (int i = 0; i < size; i++)
		if (arr[i] == a) return false;
	return true;
}

auto Array_Sum(int arr[], int size) -> int
{
	int result = 0;
	for (int i = 0; i < size; i++) result += arr[i];
	return result;
}

auto PRINT(int arr[], int size, string str) -> void
{
	cout << str;

	for (int i = 0; i < size; i++) {
		if (arr[i] != 0) cout << arr[i] << " ";
	}

	cout << "\tSUM : " << Array_Sum(arr, size) << endl;
}

auto BruteForce(int arr[], int start, int end, int count = 0) -> bool
{
	static int result[8] = { 0 };
	static int stic_i = 0;
	// 10^10 차원의 8개의 점으로 이루어진 선 한줄을 찾아야한다.
	for (int i = start; i <= end; i++) { // 10^10차원을 제귀를 통해 전개한다.
		if (count == 8) break; // count == 8 이 됨은, 들어간 배열이 가득 찼다는 의미이다. 그럼으로 전개된 차원을 탈출
		if (Chack_dup(result, 8, arr[i])) { // 중복값을 체크하여, 현재값에 진입해 있는지 확인한다.
			result[count] = arr[i]; // 현재 차원위치에 지정된 값을 삽입해준다.
			BruteForce(arr, start + 1, end, count + 1); // 재귀를 사용하여 다음 차원위치로 이동해준다.
		}
	}

	int Asum = Array_Sum(result, 8); // 현재 결과에 있는 모든 데이터를 더해준다.

	if (Asum == 100) { // 모든 데이터를 더했을 때 100이 나올경우,
		PRINT(result, 8, "RESULT : "); exit(0); // 결과를 출력해주고 1을 반환한다.
	}

	if (start >= end) { return 0; } 
	// start가 end보다 크거나 같을경우, 10^10 차원순환이 전부 완료되었을 경우, 
	// 순환완료한 재귀의 기입된 배열데이터는 의미가 없어지기 때문에 0을 반환하고 종료해준다.
	else if (Asum != 100 && count == 8) {
		// Asum 이 100이 아니고 count가 8일경우, 위의 if문에 해당이 안되기 때문에 차원순환이 전부 종료되지 않아
		// 남은 차원을 전부 순환시켜주어야 한다.
		result[count] = 0; // 현재 가득 찬 배열은 100을 만들어내지 못함으로 0으로 초기화시켜준다.
		BruteForce(arr, start + 1, end, count - 1);
		// 현재 남은 배열을 전부 순환시켜주기 위해 count를 1 줄여 마지막 값을 다음으로 넘길 수 있게 하고,
		// 다음 배열위치로 넘겨준다.
	}

	return 0;
}

int main()
{
	int arr[] = { 7, 15, 21, 8, 14, 25, 10, 11, 17, 5 };
    BruteForce(arr,0, 9);
	return 0;
}

Depth_first_search

그래프를 탐색하는 알고리즘 중 하나로, 시작 노드 에서 탐색을 시작하여, 다음 노드로 계속해서 탐색을 진행하며,

더이상 탐색할 수 없는 상태까지 깊이 들어가면 이전 단계로 돌아와, 다른 경로를 탐색한다.

이것을 반복하여 그래프를 탐색하는 방식이다.

DFS 알고리즘의 특징은 다음과 같다.

깊이 우선 탐색은 스택 또는 재귀 함수를 사용하여 구현할 수 있다.
탐색 도중에 더이상 가갈 수 없는 경로가 없다면, 이전단계로 돌아가 다른 경로를 탐색한다.
DFS는 깊이에 우선순위를 두기 때문에 시작 노드와 가까운 노드를 먼저 탐색하게 된다.

DFS 알고리즘의 장점은 다음과 같다.

구현이 간단하고, 직관적이다.
노드를 방문하는 순서를 추적할 수 있음으로 경로를 복구하는데 유효하다.
그래프에서 연결된 모든 구성요소를 탐색할 수 있다.

DFS 알고리즘의 단점은 다음과 같다.

그래프에 순환 경로가 있는 경우, 무한루프에 빠질 수 있다.
그래프가 매우 깊거나 무한한 경우, 탐색경로가 길어지기 때문에 스택 오버플로우(Stack Overflow)가 발생할 수 있다.
최단 경로를 찾는것과 같이. 최적의 해를 찾는 문제에는 적합하지 않다.

DFS 알고리즘은 다음 상황에서 사용된다.

그래프에서 한노드부터 연결된 모든 노드를 탐색해야 할 경우.
어떠한 반복되는 노드 간의 사이클을 탐지해야 할 경우,
시작 노드에서 목표 노드까지의 경로를 찾아야 할 경우,
트리구조 일 경우, 모든 트리를 탐색할 경우.

DFS 알고리즘 의 코드 예시는 다음과 같다.

#include <iostream>

using namespace std;

// 깊이 우선 탐색
// 내가 갈 수 있는 대로 최대한 들어가는 방식.
// 불필요한 경우를 차단하거나 그런건 없다.
// 그래서 경우의 수를 줄일 수 없다.
// 제귀로 들어가는 방법과 스텍으로 들어가는 방법이 있다.

template<typename T>
class Graph
{
public:

	struct Node;
	struct Edge // 간선 제작
	{
		Node* Start = NULL;
		Node* Target = NULL;
		Edge* Next = NULL;
	};
	struct Node
	{
		T Data;
		int Index = -1;
	
		Node* Next = NULL; // 다음 노드에 대한 포인터
		Edge* Edge = NULL; // 다음 간선에 대한 포인터
		
		bool Visited = false; // 방문 여부에 대한 결과
	};

private:
	Node* Head = NULL;
	int Count = 0;

public:
	static Edge* CreateEdge(Node* start, Node* target)
	{
		Edge* edge = new Edge(); // 동적할당.
		edge->Start = start;
		edge->Target = target;

		return edge;
	}
	static Node* CreateNode(T data)
	{
		Node* node = new Node();
		node->Data = data;

		return node;
	}

public:
	void AddNode(Node* node)
	{
		Node* nodeList = Head; // Head = 연결리스트에서 머리를 구현한다.

		if (nodeList != NULL)
		{
			while (nodeList->Next != NULL)
			{
				nodeList = nodeList->Next;
			}
			nodeList->Next = node; // 새로운 노드가 연결리스트 끝에 위치하게 된다.
		}
		else
		{
			Head = node;
		}

		node->Index = Count++;
	}

	void AddEdge(Node* node, Edge* edge)
	{
		if (node->Edge != NULL)
		{
			Edge* edgeList = node -> Edge;
			while (edgeList->Next != NULL)
			{
				edgeList = edgeList->Next;
			}

			edgeList->Next = edge;
		}
		else
		{
			node->Edge = edge;
		}
	}

	void Print()
	{
		Node* node = NULL;
		Edge* edge = NULL;
		if((node = Head) == NULL) // 헤드가 없다면 정보가 없으니까 종료
			return;
		while (node != NULL)
		{
			cout << node -> Data << " : ";
			if ((edge = node->Edge) == NULL)
			{
				node = node->Next;
				cout << endl;

				continue;
			}

			while (edge != NULL)
			{
				cout << edge->Target->Data;
				edge = edge->Next;
			}

			cout << endl;

			node = node->Next;
		}

		cout << endl;
	}

	void DFS(Node* node)
	{
		cout << node->Data;

		node->Visited = true;

		Edge* edge = node->Edge;

		while (edge != NULL)
		{
			if(edge->Target != NULL && edge->Target->Visited == false)
				DFS(edge->Target);
			edge = edge->Next; // 간선이 하나가 아니기 떄문에, 다음 간선도 체크해주는 부분을 만들어주어야 한다.
		}
	}
};

typedef Graph<char> G;

int main()
{
	G graph;

	G::Node* n1 = G::CreateNode('A');
	G::Node* n2 = G::CreateNode('B');
	G::Node* n3 = G::CreateNode('C');
	G::Node* n4 = G::CreateNode('D');
	G::Node* n5 = G::CreateNode('E');

	graph.AddNode(n1);
	graph.AddNode(n2);
	graph.AddNode(n3);
	graph.AddNode(n4);
	graph.AddNode(n5);
	
	graph.AddEdge(n1, G::CreateEdge(n1, n2));
	graph.AddEdge(n1, G::CreateEdge(n1, n3));
	graph.AddEdge(n1, G::CreateEdge(n1, n4));
	graph.AddEdge(n1, G::CreateEdge(n1, n5));
	
	graph.AddEdge(n2, G::CreateEdge(n2, n1));
	graph.AddEdge(n2, G::CreateEdge(n2, n3));
	graph.AddEdge(n2, G::CreateEdge(n2, n5));

	graph.AddEdge(n3, G::CreateEdge(n3, n1));
	graph.AddEdge(n3, G::CreateEdge(n2, n2));

	graph.AddEdge(n4, G::CreateEdge(n4, n1));
	graph.AddEdge(n4, G::CreateEdge(n4, n5));

	graph.AddEdge(n5, G::CreateEdge(n2, n1));
	graph.AddEdge(n5, G::CreateEdge(n2, n2));
	graph.AddEdge(n5, G::CreateEdge(n2, n4));

	graph.Print();

	graph.DFS(n1);







	return 0;
}

위 코드는 graph 라는 하나의 구조체를 생성한 뒤, 구조체 안에 모든 함수를 구현한 형태이다.

728x90