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

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

1. 문제이해 주어진 정점과 간선으로 그래프를 만들었을때 서로 이어져있는 그래프의 집합이 몇개인지를 구하는 문제이다. 2. 알고리즘 전략 문제 자체는 간단하지마 한가지 고려해야 할 사항은 그래프를 표현할때 다음과 같이 1. 2차원 배열로 나타낼수도 있고 2. 벡터를 사용하여 정점과 그 간선의 연결상태만 나타낼 수 있다. 위 문제의 경우 정점의 개수가 최대 1000개 이므로 배열의 크기는 1000*1000*4byte(int)로 약 400MB정도 되어 문제에서의 최대 메모리인 512MB보다는 작지만, 아마 프로그램 실행을 위한 기본 메모리값으로 인해, 최대 메모리인 512MB를 넘어 메모리초과가 발생한다. 따라서 벡터를 이용해서 각 정점들과 이어진 정점들만 넣어 구현하고, 1차원 배열을 만들어 방문한 정점은..

1. 문제 이해 경찰차 문제는 (1,1), (n,n) 에 위치한 경찰차 두대가 w개의 사건들을 가장 짧은 거리를 이동하여 처리하는 문제이다. 주의해야할 부분은 한 경찰차가 하나의 사건을 처리한후 다시 원래자리로 돌아가는 것이 아니라 그 자리에서 다음사건을 처리하게 되고, 사건들은 같은 장소에서 여러번 일어날 수 있다는 점이다. 2. 알고리즘 전략 먼저 문제의 예시를 통해 시나리오를 분석해보자. 경찰차는 (1,1) 그리고 (6,6)에 위치해있고 3개의 사건이 분포되어있다. 만약 첫번째 사건을 처리한다고 가정해보자. 위와같이 1번 경찰차가 6칸을 이동하여 1번 사건을 처리할수도 있고, 2번 경찰차가 4칸을 이동하여 1번 사건을 처리할수도 있다. 그렇다면 총 몇번 시도를 해봐야 모든 경우의 수를 다 탐색해 볼..

올해로 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

문제 이해 토마토 문제에서는 각 박스내에 3가지 상태가 존재한다. 익은 토마토(1), 안익은 토마토(0), 비어있는 칸(-1). 주의할 점은 익은 토마토는 자신의 상하좌우에 위치한 토마토만을 익힐 수 있고, 비어있는칸이 존재할 수 있기때문에, 문제의 예제2 처럼 모든 토마토를 전부 익힐 수 없는 상황이 주어질 수도 있다는 점을 고려해야한다. 알고리즘 설계 문제에서 주어진 예제3의 경우를 시각화했을 때의 모습이다. 간단하게 생각해보면, 1. 현재 익은토마토(1)의 상하좌우의 토마토들의 상태를 1로 바꾼다. 2. 현재 익은토마토들 주변에 익힐수 있는 토마토가 없을 경우 종료 / 아닐 경우 1 반복 로 표현할수 있다. 그런데 현재 익은 토마토의 개수는 매번 달라지므로 일반적인 재귀함수로 표현하기는 힘들것 같다..