dfs
-
Spanning TreeC 자료구조/Graph 2020. 10. 15. 21:51
0. 참고 문헌 1. 개념 신장 트리( Spanning tree )란 그래프 내의 모든 정점을 포함하는 트리이다. 신장 트리는 트리의 특수한 형태이므로, 모든 정점들이 연결되어 있어야 하고, 또한 사이클을 포함해서는 안 된다. 따라서, 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 그래프에서 신장 트리를 찾으려면 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 여기서는 깊이 우선 탐색 방법을 사용한다. 아래에 하나의 그래프가 주어졌다고 가정하자. 아래의 그림들은 모두 위의 그래프에서 시작정점을 바꾸어 가면서 깊이 우선 탐색 혹은 너비 우선 탐색을 해서 만든 신장 트리의 일부이다. 첫 번째 신장 트리 그래프..
-
마족 찾기Algorithm with C/DFS 2020. 9. 9. 11:34
1. 문제 2. 문제 분석 이 문제는 BFS방식으로 접근하는 것이 올바르다. 주민의 수가 너무 많아지면, DFS방식에서는 stack overflow가 나타나기 때문이다. 그러나, 여기서는 DFS방식으로도 접근을 해볼것이다. 아래의 구현에서는 Res배열을 하나 선언할 것인데, 선언하는 이유는 아래와 같다. 마을 주민이 3사람이 있다고 하자. (1,2,3 이라고 칭하겠다.) 주민 1번이 마을 주민 2,3,4 번을 지목했다고 하자. 그러면 지목을 받은 주민 2번 주민이 지목을 한다. 3.4.5번 주민을 지목한다고 하자. 그리고, 3번 주민이 지목을 한다. 3번 주민이 2,4,5번을 지목했다고 했을 때, 이미 주민2번이 주민3번을 지목했고, 다시 3번 주민이 2번 주민을 지목한 상황이 되었다. 즉, 위와 같은 ..
-
집합의 부분 집합 출력하기 - 상태공간트리Algorithm with C/DFS 2020. 9. 7. 10:15
1. 문제 입력으로 ABC가 입력되었다고 가정했을 때, 이 ABC의 부분집합들을 출력하면 된다. 입력 ABC 출력 { } { A }, { A, B }, { A, B, C } { B }, { B, C } { C } 구현방법 먼저, 출력의 형태를 다음과 같이 다시 써보도록 하자. 집합의 원소 개수가 3일 때, 부분집합의 개수는 총 2^3 = 8개가 나온다. 구현 방식은 두 가지가 있다. 첫 번째 방식은 별도의 출력 배열을 가지고 있는 경우와 두 번째 방식은 별도의 메모 배열( 동적 프로그래밍을 위한 )을 두고서 기록하는 경우이다. 두 부분에서 일치하는 방식은 아래와 같다. 먼저 사용자로부터 집합 원소의 개수를 입력 받도록 하자. 입력으로 3이 들어오면, 3칸짜리 char형 배열이 만들어지면서 이 배열안에 각..
-
출근길은 즐거워Algorithm with C/DFS 2020. 9. 2. 17:49
1. 문제 이번에는 출근길에 주위 경치의 아름다움을 느낄 줄 아는 즐거워 씨의 이야기이다. 즐거워 씨는 동네의 각 위치마다 아름다운 정도를 나타내는 자연수 값을 적어두고 있다. 아름다운 정도를 나타내는 즐거워 씨의 동네 지도는 다음의 2차원 배열로 나타낼 수 있다. 즐거워 씨의 동네에는 공사 중인 곳이 없다. [그림 1] 즐거워 씨도 매일 아침, 위치 (0,0)에서 위치 (4,4)로 출근한다. 즐거워 씨가 출근길에 느끼는 즐거움은 지나가면서 만나는 경치의 아름다움의 합이 된다. 예를 들어, 아래의 [그림 2]와 같이 출근하면 1+1+2+1+3+1+2+1+2 = 14 만큼의 즐거움을 느끼며 출근하게 된다. [그림 2] 즐거워 씨도 항상 최단 거리로 출근한다. 예를 들어, 아래 [그림 3]과 같은 경로는 매..
-
숙직 선생님Algorithm with C/DFS 2020. 8. 31. 17:43
1. 문제 2. 문제분석 BFS 나 DFS는 항상 트리의 개념으로 이해를 해야 한다. 그리고, 위의 입력 예시와 같이 먼저, 선생님의 현재위치를 1로 고정시키고, 누군가의 위치를 15로 고정 시키자. 그러면 다음과 같이 될 것이다. 그리고 Tree의 개념으로 그림을 그려보자. 위의 그림에서 2, 5, 7이라는 붉은 상자안의 숫자의 의미는 선생님이 한 번에 이동할 수 있는 능력이다. 문제의 입력 예시 부분에서 볼 수 있다. 그리고, 위의 트리 구조에서 1은 선생님의 현재 위치이다. 즉, 선생님이 이동 할 수 있는 위치가 각 각 3,6,8 이라는 위치이다. 1 + 2 = 3 1 + 5 = 6 1 + 7 = 8 그리고, 3,6,8의 위치에서 다시 움직일 수 있는 위치는 아래와 같다. 3 + 2 = 5 3 + ..
-
4종류 동전으로 N 센트를 표현하는 경우의 수Algorithm with C/DFS 2020. 8. 27. 19:22
1. 문제 쿼터( 25센트 ), 다임( 10센트 ), 니켈( 5센트 ), 페니( 1센트 ) 의 네 가지 동전이 무한히 주어진다고 했을 때, N 센트를 표현하는 모든 경우의 수를 구하라. 2. 문제 분석 이 문제는 재귀 문제이다. 함수 makeChange(N)을 부분 문제들의 답을 통해 계산하는 법을 알아내 보도록 하자. N = 100 이라고 해보자. 도합 100 센트의 잔돈을 만드는 방법을 계산해야 한다. 이 문제와 부분 문제들은 어떤 연관성을 가지는가? 100센트의 잔돈에는 쿼터가 0개, 1개, 2개, 3개, 4개 있을 수 있다는 것을 알고 있다. ( 쿼터는 25센트니까, 25 * 5 = 125센트가 되어서, 쿼터는 5개가 될 수 없다. ) 그러므로, 위의 관계가 성립한다. 이 결과를 좀 더 들여다보면..
-
미로 탐색Algorithm with C/BackTracking 2020. 8. 26. 19:26
0. 참고 문헌 1. 개념 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데, 이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다. 여기에서 부분 문제의 답은 어느 것이라도 될 수 있다. 선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로. 게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고, 그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다. 백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있..
-
N - QueenAlgorithm with C/BackTracking 2020. 8. 24. 18:19
0. 참고 문헌 1. 문제 2. 문제 분석 퀸은 8가지 방향으로 움직이며 공격을 할 수 있고, 이동 범위도 체스판 전체이다. 8개의 퀸 문제는 8 X 8 크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스 판으로도 문제의 확장과 축소가 가능하다. 4 X 4 이상의 크기라면 이 문제를 적용할 수 있는데, 그래서 8개의 퀸 문제를 N 개의 퀸 문제라 부르기도 한다. 퀸을 체스판에 배치할 때, 행을 기준으로 배치하는 것으로 약속을 하도록 하자. 그리고 체스판은 4 X 4로 고정하고 문제 풀이에 접근한다. 당연히 퀸은 하나의 행에 하나만 배치가 가능하다. (퀸의 공격 범위가 가능하므로) 아래의 [그림 1 ~ 4]는 체스판의 크기가 4 X 4일 때의 퀸을 놓는 방법을 나타낸 것이다. 별 모양이 퀸이다. [그..