Backtracking - 편집 역사

Pinkgo: /* Constructing Subsets by Backtracking */

2025-11-18T03:37:43Z

Constructing Subsets by Backtracking

← 이전 판		2025년 11월 18일 (화) 03:37 판
83번째 줄:		83번째 줄:

	==Constructing Subsets by Backtracking==		==Constructing Subsets by Backtracking==
	해당 문단에서는 주어진 집합의 모든 부분집합(2<sup>2</sup>개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:		해당 문단에서는 주어진 집합의 모든 부분집합(2<sup>n</sup>개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:
	# 각 단계 k마다 후보 집합 S<sub>k</sub> = (True,False)		# 각 단계 k마다 후보 집합 S<sub>k</sub> = (True,False)
	# 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.		# 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.

Pinkgo: /* Constructing Subsets by Backtracking */

2025-11-18T03:32:24Z

Constructing Subsets by Backtracking

← 이전 판		2025년 11월 18일 (화) 03:32 판
83번째 줄:		83번째 줄:

	==Constructing Subsets by Backtracking==		==Constructing Subsets by Backtracking==
	해당 문단에서는 어진 집합의 모든 부분집합(2<sup>2</sup>개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:		해당 문단에서는 주어진 집합의 모든 부분집합(2<sup>2</sup>개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:
	# 각 단계 k마다 후보 집합 S<sub>k</sub> = (True,False)		# 각 단계 k마다 후보 집합 S<sub>k</sub> = (True,False)
	# 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.		# 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.

Pinkgo: /* Applying Backtracking(과제 문제) */

2025-10-29T21:55:16Z

Applying Backtracking(과제 문제)

← 이전 판		2025년 10월 29일 (수) 21:55 판
251번째 줄:		251번째 줄:
	입력: 그래프 <math>G=(V,E)</math><ref>정점 n개, 간선 m개</ref>		입력: 그래프 <math>G=(V,E)</math><ref>정점 n개, 간선 m개</ref>
	목표: 주어진 모든 정점을 일렬로 배치했을 때<ref>정점 순열을 구한다.</ref>, 가장 긴 간선의 길이<ref>두 정점의 거리를 의미한다.</ref>를 최소화하는 순열을 찾는 것이다.		목표: 주어진 모든 정점을 일렬로 배치했을 때<ref>정점 순열을 구한다.</ref>, 가장 긴 간선의 길이<ref>두 정점의 거리를 의미한다.</ref>를 최소화하는 순열을 찾는 것이다.
			[[파일:Figure 3. Bandwidth Problem.png\|섬네일\|Figure 3. Bandwidth Problem]]
	예를 들어 figure 3의 왼쪽 그림은 정점이 1~8 순서대로 있을 때 여러 간선이 길게 연결된 상태이고, 오른쪽 그림은 정점의 재배열을 통해서 간선의 길이가 더 짧아진 것을 보여준다.		예를 들어 figure 3의 왼쪽 그림은 정점이 1~8 순서대로 있을 때 여러 간선이 길게 연결된 상태이고, 오른쪽 그림은 정점의 재배열을 통해서 간선의 길이가 더 짧아진 것을 보여준다.

259번째 줄:		260번째 줄:
	입력: 원소들의 전체집합 <math>U=\{1,2,\cdots,n\}</math>과 여러 부분집합 <math>S_1,S_2,\cdots,S_m</math>		입력: 원소들의 전체집합 <math>U=\{1,2,\cdots,n\}</math>과 여러 부분집합 <math>S_1,S_2,\cdots,S_m</math>
	목표: 이 부분집합들 중 일부를 골라서 <math>U</math> 전체를 덮되, 선택한 부분집합의 수가 최소가 되도록 한다.		목표: 이 부분집합들 중 일부를 골라서 <math>U</math> 전체를 덮되, 선택한 부분집합의 수가 최소가 되도록 한다.
			[[파일:Figure 4. Set Cover Problem.png\|섬네일\|210x210픽셀\|Figure 4. Set Cover Problem]]
	즉, figure 4와 같이 입력이 주어졌을 때, <math>\bigcup_{i\in T}S_i=U</math>를 만족하는 최소 크기의 <math>T</math>를 찾는 문제이다. 이를 해결하는 가장 단순한 방법은 가능한 모든 부분집합을 확인하는 것이다. 하지만 가능한 부분집합의 개수는 <math>2^m</math>개이므로 시간복잡도가 <math>O(2^m\times n \times m)</math>이므로 매우 비효율적이다. 따라서 이를 해결하기 위해서는 완전 탐색이 아니라, 효율적인 백트래킹과 가지치기(pruning) 전략을 사용하여 근사적인 해를 구해야 한다.		즉, figure 4와 같이 입력이 주어졌을 때, <math>\bigcup_{i\in T}S_i=U</math>를 만족하는 최소 크기의 <math>T</math>를 찾는 문제이다. 이를 해결하는 가장 단순한 방법은 가능한 모든 부분집합을 확인하는 것이다. 하지만 가능한 부분집합의 개수는 <math>2^m</math>개이므로 시간복잡도가 <math>O(2^m\times n \times m)</math>이므로 매우 비효율적이다. 따라서 이를 해결하기 위해서는 완전 탐색이 아니라, 효율적인 백트래킹과 가지치기(pruning) 전략을 사용하여 근사적인 해를 구해야 한다.

	==각주==		==각주==

Pinkgo: /* Applying Backtracking(과제 문제) */

2025-10-29T21:53:17Z

Applying Backtracking(과제 문제)

@@ 229번째 줄: / 229번째 줄: @@
+}
 </syntaxhighlight>
 ==Applying Backtracking(과제 문제)==

Pinkgo: /* Applying Backtracking */

2025-10-29T21:35:39Z

Applying Backtracking

@@ 180번째 줄: / 180번째 줄: @@
 위는 전체 프로그램을 실제로 실행시키는 함수이다.
-==Applying Backtracking==
+==The Eight-Queens Problem==
 ===Bandwidth===
 ==각주==

Pinkgo: /* Constructing Permutations by Backtracking */

2025-10-29T20:53:56Z

Constructing Permutations by Backtracking

← 이전 판		2025년 10월 29일 (수) 20:53 판
179번째 줄:		179번째 줄:
	</syntaxhighlight>		</syntaxhighlight>
	위는 전체 프로그램을 실제로 실행시키는 함수이다.		위는 전체 프로그램을 실제로 실행시키는 함수이다.

			==Applying Backtracking==
			===Bandwidth===

	==각주==		==각주==

2025년 10월 25일 (토) 20:14에 Pinkgo님의 편집

2025-10-25T20:14:09Z

← 이전 판		2025년 10월 25일 (토) 20:14 판
89번째 줄:		89번째 줄:

	===Subset Generation Tree / Order===		===Subset Generation Tree / Order===
	~~Figure는~~ 부분집합을 생성하는 탐색 트리(Generation Tree)를 시각화한 것이다. 해당 트리는 루트에서 시작해서 각 단계마다 “포함한다”또는 “포함하지 않는다”의 두 가지 선택지를 가진다. 이때 트리의 깊이는 집합의 원소 개수 n과 같으며, leaf 노드는 완성된 부분집합을 의미한다.		[[파일:Figure 1. Subset Generation Tree - Order.png\|섬네일\|Figure 1. Subset Generation Tree / Order]]
			Figure 1은 부분집합을 생성하는 탐색 트리(Generation Tree)를 시각화한 것이다. 해당 트리는 루트에서 시작해서 각 단계마다 “포함한다”또는 “포함하지 않는다”의 두 가지 선택지를 가진다. 이때 트리의 깊이는 집합의 원소 개수 n과 같으며, leaf 노드는 완성된 부분집합을 의미한다.

	이러한 원리를 백트래킹 코드에 대해 적용할 수 있다. 이를 위해 아래와 같은 조건을 이해하자:		이러한 원리를 백트래킹 코드에 대해 적용할 수 있다. 이를 위해 아래와 같은 조건을 이해하자:
132번째 줄:		133번째 줄:

	==Constructing Permutations by Backtracking==		==Constructing Permutations by Backtracking==
			[[파일:Figure 2. Permutation Generation Tree - Order.png\|섬네일\|Figure 2. Permutation Generation Tree / Order]]
	해당 문단에서는 백트래킹 기법을 이용하여 모든 순열을 생성하는 방법에 대해 설명한다. 순열(permutation)이란 n개의 원소를 서로 다른 순서로 배열하는 모든 경우의 수를 의미한다. 예를 들어, {1, 2, 3}의 순열은 123, 132, 213, 231, 312, 321이다. 이때 n개의 원소로 만들 수 있는 순열의 개수는 n!(팩토리얼)이다.		해당 문단에서는 백트래킹 기법을 이용하여 모든 순열을 생성하는 방법에 대해 설명한다. 순열(permutation)이란 n개의 원소를 서로 다른 순서로 배열하는 모든 경우의 수를 의미한다. 예를 들어, {1, 2, 3}의 순열은 123, 132, 213, 231, 312, 321이다. 이때 n개의 원소로 만들 수 있는 순열의 개수는 n!(팩토리얼)이다.

	순열을 표현하기 위해서는 a라는 배열을 만들어야 하며, 이때 a[i]는 순열의 i번째 자리에 올 숫자를 나타낸다. 따라서 각 a[i]는 아직 사용되지 않은 숫자 중 하나를 선택해야 한다. 이를 백트래킹 알고리즘의 일반 형태로 표현하면:		순열을 표현하기 위해서는 a라는 배열을 만들어야 하며, 이때 a[i]는 순열의 i번째 자리에 올 숫자를 나타낸다. 따라서 각 a[i]는 아직 사용되지 않은 숫자 중 하나를 선택해야 한다. 이를 백트래킹 알고리즘의 일반 형태로 표현하면:
	<math>S_k = \{1, 2, ..., n\} - v</math>		<math>S_k = \{1, 2, ..., n\} - v</math>
	즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다.		즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 2는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다.

	===Implementation of Constructing All Permutations===		===Implementation of Constructing All Permutations===

Pinkgo: /* Constructing Permutations by Backtracking */

2025-10-25T20:11:42Z

Constructing Permutations by Backtracking

@@ 139번째 줄: / 139번째 줄: @@
 ===Implementation of Constructing All Permutations===
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
-<syntaxhighlight lang="c">
+위는 전체 프로그램을 실제로 실행시키는 함수이다.
 ==각주==

Pinkgo: /* Constructing Subsets */

2025-10-25T20:07:47Z

Constructing Subsets

← 이전 판		2025년 10월 25일 (토) 20:07 판
96번째 줄:		96번째 줄:
	* 모든 원소를 처리했을 때 (k == n) → 완성된 해.		* 모든 원소를 처리했을 때 (k == n) → 완성된 해.

	===Constructing Subsets===		===Implementation of Constructing Subsets===
	이를 아래와 같이 ~~적용할~~ 수 있다:		위에서 다룬 내용을 아래와 같이 기본적인 백트래킹 코드 틀(framework)안에 적용하여 C언어로 구현할 수 있다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	int is_a_solution(int a[], int k, int n) {		int is_a_solution(int a[], int k, int n) {

Pinkgo: /* Constructing All Permutations */

2025-10-25T20:05:15Z

Constructing All Permutations

← 이전 판		2025년 10월 25일 (토) 20:05 판
138번째 줄:		138번째 줄:
	즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다.		즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다.

	===Constructing All Permutations===		===Implementation of Constructing All Permutations===
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	</syntaxhighlight>		</syntaxhighlight>