BackTracking_백준1182번

• 부분수열에 속한 원소를 모두 합한 것이 S가 되는 부분수열의 개수를 출력.
• 부분 수열이라는 것은 결국, 어떤 시작점부터 어떤 끝점까지 연속한 원소들의 집합.
• 전체 탐색을 해야하는가? 시간제한이 2초고, 1<=n<=20 인 것으로보아 전체 탐색을 고려한 문제 같다.

#include <iostream>
int arr[21];
int n,s;

using namespace std;
int main()
{
	cin >> n>>s; 
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int start, end,sum=0,cnt=0;
	// 3 0
	// 0 0 0
	for (start = 0; start < n; start++) {
		sum = arr[start]; 
		
		for (end = n - 1; end >= start; end--) {
			for(int i=end; i>=start;i--)
				sum += arr[i];
			if (sum == s) cnt++;
		}
		
	}
	cout << cnt << endl;
}

고 생각해서 틀렸다.

부분수열에 대한 이해

주의 할 것 (수학적 개념의 부족에서 생긴 문제 이해에서 오류가 생겼다)

• 부분 수열이라는 것이 연속된 수열만을 의미하는 것 이 아니다.
• 예를들어 수열 (x1,x2,x3,....,) 에서 부분수열은 (x1,x3,x5,...) 이 될 수 있다.

이 문제가 속한 알고리즘 자체가 떠오르지도 않았고 몰랐다. 나는 알고리즘 바보기에 알고리즘을 모르는 상태에서 문제를 풀 확률은 희박하다고 생각한다. 배워나가자. 재밌으니까

BackTracking algorithm

• "재귀적으로 문제를 풀어"가는 기술 - 한 번에 한 조각씸 점진적으로 해결해 나가며, 각 순간마다의 제약조건을 만족하는데 실패한 solution은 제외해 나가면서 풀어나가는 것.
• 스도쿠를 예로 들 수 있다. 스도쿠의 경우, 숫자를 하나씩 채워나간다. 해당 숫자가 solution이 아님을 발견할 때마다, 이는 제외시키고(backtrack) 다음 숫자를 시도 해 본다. 어찌보면 꼭 naive approach같지만, naive approach보다 낫다( naive approach는 모든 "가능한 조합"들을 생성해서, 모든 조합을 하나씩 시도해보는 것) . 왜냐하면, 여기서는 fail(backtrack)할때마다, 해당 permutation(순열)을 drop하기 때문.
• BackTracking역시 답을 찾는 solution을 찾을 때 까지 서로 다른 solutions를 시도해 보는 것 임.
• 보통 Backtracking 기술을 사용해서 불리는 문제들은 다음과같은 공통적인 특징이 있다.
  • 모든 가능한 configuration을 시도해야지만 풀 수 있다. + 각 Configuration은 한 번만 try
• Naive Solution : "모든" configurations을 시도해서, 문제의 주어진 제약조건을 따르는 configuration을 산출하는 것.
  • Naive Solution은 "모든 가능한 configurations"을 생성하고 모두 시도해봐야만 함.
• BackTracking은 works in incremental way.
• BackTracking은 Naive solution 을 최적화 시킨 것이다.

여기까지 보면 그래서 어떤식으로 진짜 풀이해나간다는 건지 잘 모르겠지만,

https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/

예제 : Knight's Tour 문제

주어진 N*N 보드가 있다. 나이트는 이 emtpy board의 첫 번째 block에 놓여있다. 체스 규칙에 따라 나이트는 각 사각형을 정확히 하나씩만 방문할 수 있다. 각 cell이 방문되는 순서를 출력하라.

Input : 
N = 8
Output:
0  59  38  33  30  17   8  63
37  34  31  60   9  62  29  16
58   1  36  39  32  27  18   7
35  48  41  26  61  10  15  28
42  57   2  49  40  23   6  19
47  50  45  54  25  20  11  14
56  43  52   3  22  13  24   5
51  46  55  44  53   4  21  12

Naive 알고리즘으로 풀이

• 가능한 모든 tour의 경우의 수 를 생성하고, 각 경우에 대해 제약조건(constraint)을 만족하는지 체크해나간다.

whlie(IsUntiredTours){
	generate the next tour
	if(this tour covers all squares)
	{ print this path;
	}
}

BackTracking 알고리즘으로 풀이

1. next moves를 solution vector에 추가해가면서, 재귀적으로 이 move 가 solution을 이끌어내는 지를 확인한다. 나이트는 최대 8가지의 move를 할 수 있기에 , 각 step마다 8개의 move를 확인하도록 해야 한다.
2. 1에서 선택된 move가 solution을 이끌어내지 못하면, solution vector에서 이 move를 제거하고 다른 alternative move를 선택한다.
3. 어떤 alternative move도 work하지 않으면 false를 return 한다.
   1. Returning false will remove "the preivously added item" in recursion,
   2. and if , 이 false를 return한 것이 recursion의 initial call이면 solution 이 존재하지 않는 것이 된다.

이 예제를 통해, BackTracking은 이런식으로 재귀적인 방식을 통해서, 점진적으로 풀어 나간다는 것이 이해가 되었다.

Complexity

• 이 나이트 문제의 경우, 하나의 step에는 8가지 move가 존재한다. 첫 번째 8 가지 move 각 각에서 N^2개의 cells를 ㅂ아문해야함. 따라서 worst running은 O(8^(N^2))이다.

백준 1182번

• 생각
  • 백트래킹 이론을 한 번 보고 나니 이문제가 딱 백트랙킹이구나 싶었다.
  • 원소 하나가 실패한다고 전체 경우를 처음부터 다시하는 것이 아닌, 실패한 원소 하나를 빼고 다른 대체 원소를 확인하는 이런생각이 백트랙킹 방식이었던 듯 하다.
  • 또한 재귀적으로 확인해 나가기 때문에 이 부분순열의 원소의 개수를 미리 고려하지 않는다. 재귀적으로 하는 것을 통해 정답 vector에 원소를 추가해 나가는 방식으로 하면 되기 때문이다. for문으로 하게 되면, 이것이 불가능.(?가능한가?. 하지만 재귀적으로 생각하는게 더 편하긴 하다)
  • 이 문제의 경우 1≤N≤20으로 원소의 수가 적고 시간제한이 2초로 비교적 길기 때문에 이런식으로 solution을 확인해 나가는 백트랙킹 방식을 떠올리는 것을 고려할 것.
  • 일단 이 문제는 "부분수열"이라는 것에 대한 이해가 부족해서 치명적이었다.
  • 순열이라는 것이 순차적이지만은 않다는 것에도 주의해야한다.
  • 💥주의 할 것은, (solution을 찾고도, 뒤의 것을 계속 탐색해야한다는 것이다)
    • ( -5 -1 -3 -2 0 0 5) 을 갖고 -5를 만든다고 할 때 -5 만을 보고 (-5 , 0)과 ( -5 ,-3 ,-2 , 5)를 지나치면 안 되니까.
    • 이 모든 것은 서로 다른 case에 해당된다.
    • solution인 부분수열의 원소의 개수를 특정지을 수 없다. 따라서, sum이 S와 같아지더라도 계속해서, 부분수열을 만들어가면서, sum이 될 때 마다 count를 ++ 하도록 해야 한다.
    • S와 같은 값으로 sum이 될 때 마다 count를 하도록 해야 한다.

#include <iostream>
#include <vector>

using namespace std;

int arr[21];
int N, S,g_cnt=0;
void solve(int start, int sum)
{
	if (start >= N) return;
	int temp_sum = sum;
	temp_sum += arr[start];
	if (temp_sum == S) g_cnt++;
	for (int i = start + 1; i < N; i++)
		solve(i, temp_sum);
}
int main()
{
	int i, temp_sum;
	std::cin >> N >> S; 
	for ( i = 0; i < N; i++)
		cin >> arr[i];	
	
	for (i = 0; i < N; i++)
	{
		temp_sum = 0;
		solve(i,temp_sum);
	}

	printf("%d", g_cnt);
}

• 구현생각
  • 첫 번째 원소에 대한 후보 : N개 . for문을 통해 solve함수를 호출한다.
  • 순열이라는 특성 상, find를 해도 이후 원소들을 점검해야한다. find한 것에서 cnt를 증가시키고, 이후 원소들을 더한 것에서도 또 find하면 그 때도 또 cnt를 증가시킨다 (-4 0 4 -2 2) 가 있을 때 (-4 0 4) (-4 0 4 -2 2) 도 0이 되기 때문임.
  • 테스트 :

        5 0
        -7 -3 -2 5 8
        //1
        3 5 
        5 0 0
        // 4
        3 0
        0 0 0 
        //7
        3 -5
        -4 0 -1
        //2
        12 1000000
        1000000 1000000 1000000 1000000 100000 100000 100000 100000 100000 100000 100000 -100000
        //12