프로그래밍에 대한 고찰 및 생각

1. 오일러 서킷 ( 한붓그리기) 오일러 서킷이란 한 정점에서 시작해서 모든 간선을 지나 시작 정점으로 돌아오는 것을 의미한다. 2. 오일러 서킷의 조건 정점들과 간선들이 주어졌을때, 해당 자료에서 오일러 서킷이 존재하는지 판단하려면 어떻게 해야할까? 오일러 서킷이 되기위한 2가지 조건은 다음과 같다. 1. 모든 간선들이 하나의 컴포넌트에 속해야한다. 2. 각 정점마다 간선의 수가 짝수개여야한다. 그 이유에 대해 하나씩 알아보자. 2-1. 모든 간선들이 하나의 컴포넌트에 속해야한다. 위와같은 경우 각 컴포넌트별로는 오일러서킷이 존재하지만, 전체 정점들로 보았을때는 컴포넌트간 순회 할 수 없기때문에 반드시 모든 간선들이 하나의 컴포넌트에 속해야한다. 2-2. 각 정점마다 간선의 수가 짝수개여야한다. 각 정..

올해로 20살이된 민수는 코로나 여파로 겨울방학임에도 불구하고 집에서 나갈 수 없어 옛 추억을 떠올리며 오랜만에 스타크래프트 게임을 시작했다. 평소에 프로토스 종족을 좋아하던 민수는 부푼마음으로 게임을 시작했지만 너무 오랜만에 하는 탓에 지어야 할 건물들의 순서를 몰라 난관에 부딪혔다. 스타크래프트 라는 게임에서는 각 종족마다 많은 건물들이 존재한다. 그러나 이러한 건물들을 게임을 처음 시작하면 바로 건설할수 없는 건물들이 있으며 이 건물들은 지정된 다른 건물들을 먼저 선행으로 건설해야 건설할 수 있다. 예를 들어 0번 건물을 짓기위해서는 1번건물을 지어야한다. 그런데 1번 건물을 지으려면 2번 건물을 지어야한다. 즉 2->1->0 의 순서로 건물을 지을 수 있다. 위와같은 건물의 순서도를 참고해서 10..

너비 우선 탐색 BFS (Breadth-First Search) 너비 우선 탐색 (이하 BFS) 는 시작 정점에서 방문할 수 있는 정점들을 우선 방문한후, 이후에 그 정점들에서 방문 할수 있는 정점들을 방문 하는 탐색 방법이다. 예를 들어 위와같은 그래프에서 0번 정점으로 부터 BFS를 시행한다고 하면 ( 방문할수 있는 정점이 여러개라면 번호가 낮은 정점을 우선 방문한다고 가정 ) 이전의 DFS에서는 1번 정점을 방문한뒤, 1번 정점에서 방문할 수 있는 2번 정점을 방문하였지만 BFS에서는 1번 정점을 방문한뒤, 바로 9번 정점을 방문한다. 이후 1번 정점에서 방문할 수 있는 2,5,7번 정점을 방문한 후, 9번 정점에서 방문할 수 있는 정점을 방문한다. ( 위 그래프 상황에서는 이미 9번과 연결된 7번..

깊이 우선 탐색 DFS (Depth-First Search) 깊이 우선 탐색(이하 DFS)은 하나의 정점에서 시작해서 그래프를 탐색 하는 방법중 하나로 한 정점에서 갈수있는 정점을 방문하고 해당 정점에서 갈수 있는곳을 계속해서 방문하여 더이상 방문할 정점이 없을때까지 방문하는 방법이다. 쉽게생각해서 미로탈출 게임을 할때 만약 세가지 갈림길이 나왔을 때, 셋중 하나를 골라서 끝까지 진행해본후 막혀있다면 다시 원점으로 돌아와 다른 길로 가는 것과 같이 생각하면 될것이다. 다음과 같은 방향이 없는 그래프로 생각해보자. 0번 정점에서 시작해서 DFS를 수행하는 과정은 다음과 같다. 이번 DFS에서는 현재 정점에서 갈 수 있는 정점들 중 가장 번호가 낮은 정점부터 방문한다고 가정하자. 0번 정점에서 처음에 갈수 ..

그래프(Graph) 란? 그래프는 어떤 자료나 개념을 각각의 정점들(vertex)의 집합 V와 그 정점들을 이어주는 간선들(edge)의 집합 E로 구성된 자료 구조이다. 이러한 그래프는 크게 두가지로 표현이 가능하다. 1. 인접 리스트 표현 2. 인접 행렬 표현 1. 인접 리스트 표현 첫번째로 그래프를 표현할 수 있는 방법은 인접 리스트 이다. #include #include using namespace std; int main(){ vector v; for(int i=0;i