💡 문제

문제설명

🤔 고민사항

• 몇차례 코딩테스트 경험을 통해 특히 '백트래킹' 유형에 약하다는 것을 알았다. 백준에서 백트래킹 문제집을 전부 풀어보자고 마음먹고 시작했는데 실버2 문제에서 걸려버렸다.
• 처음에 '부분수열', '다 더한값이 S가 되는~'을 보고 구간합을 적용하면 되겠구나 하고 삽질했다. (논리적으로 좀 생각해라)
• 풀이과정을 생각해내 봤다.

1. 입력받은 Array를 오름차순으로 sort한다.
2. 첫번째 인덱스 값부터 순차적으로 합해간다. 이때 S와 같아지면 ANS++하고 다음 인덱스로 넘어가고, S보다 값이 커지면 바로 다음 인덱스로 넘어간다.

• 이때까지만 해도 이정도면 풀어질줄 알았다. 또 2중 for문으로 구현할 수 있겠다 싶어 recursive하지 않게 구현해봤다.

public class 부분수열의합 {

	static int N, S, ANS;
	static int[] ARR;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		ARR = new int[N];

		for(int i=0; i<N; i++)
			ARR[i] = sc.nextInt();

		Arrays.sort(ARR);

		for(int i=0; i<N; i++){
			int n = ARR[i];
			for(int j=i+1; j<N; j++){
				n += ARR[j];
				if(n == S){
					ANS++;
					break;
				}
				if(n > S)
					break;
			}
		}

		System.out.println(ANS);
	}
}

• ㅋㅋ 될리가 있나 12%에서 틀린다. 생각해보니 배열을 순차적으로 탐색하면 크기가 양수인 부분수열 조합을 전부 찾지 못한다.
• 다른 블로그를 참고해서 아이디어를 얻었다.

  [백준-1182]부분수열의 합 (Java) :: 기억 안 나면 다시 보면 되지

• 전체 집합에서 부분집합, 즉 부분수열을 구하는 테크닉이 있었다. 생각해보니 알고리즘 전공때 해봤던 기억이 있다. 역시 전공자는 '어디서 봤던건데' 하는사람이다
• 블로그에서 친절히 수필로 부분수열을 구하는 트리까지 그려줬다. 부분수열을 찾고 합이 S인 경우 answer++ 하기만 하면 된다.

• 직접 TREE 를 그려봤다.
  TREE의 각 depth는 배열의 각 원소를 나타낸다. 즉, depth 끝까지 TREE를 탐색하면 전체 수열의 부분수열을 구할 수 있다. (정확히는 부분수열의 합을 구하는 것)
  TREE의 link를 살펴보면, 왼쪽 가지는 원소를 포함하고, 오른쪽 가지는 원소를 포함하지 않음을 뜻한다.
  쉽게 말해 왼쪽으로 탐색하는 과정과 오른쪽으로 탐색하는 과정을 재귀적으로 구현하면 된다.

문제를 복기하면서.. (2023.09.03)
검색의 힘을 받아 문제를 해결하고 며칠 후 다시 한번 풀어봤다.
역시 처음 풀 땐 안보였던 요소들을 발견할 수 있었다.

import java.util.Scanner;
public class 부분수열의합_prac {
    static int N, S, ANS;
    static int[] ARR;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        ARR = new int[N];
        for(int i=0; i<N; i++)
            ARR[i] = sc.nextInt();
        dfs(0, 0);
        if(S == 0)
            ANS -= 1;
        System.out.println(ANS);
    }
    public static void dfs(int depth, int sum){
        if(depth == N){
            if(sum == S)
                ANS++;
            return;
        }
        dfs(depth + 1, sum + ARR[depth]);
        dfs(depth + 1, sum);
    }
}

직접 다시한번 트리를 그려보며 dfs를 구현해봤다.

• 백트래킹, DFS 문제를 풀 때에는, 일단 그림을 그려봐야한다. 일단 그리고 볼 것.
• 다시 생각을 해보니 이 문제는 말만 바꾸면 전체 집합에서 가능한 모든 경우의 조합을 찾는 문제이기도 하다. 비교적 최근 어딘가의 코딩테스트에서 '가능한 조합의 갯수를 찾는 문제'를 해결하지 못했던 기억이 난다. 그래도 몇 문제는 풀어봤기에, 이게 dfs를 활용한 백트래킹으로 해결하는 문제라는 것을 눈치채기 까지는 했는데, 정작 구현을 못했었다.
• dfs() 코드를 자세히 따라가다 보면 전체 수열에서 나올 수 있는 모든 부분수열(즉 집합)을 탐색해낸다.

👨‍💻 CODE

mport java.util.Scanner;

/**
 * 백준 1182
 * 실버 2
 *
 */
public class 부분수열의합 {

	static int N, S, ANS;
	static int[] ARR;

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		ARR = new int[N];
		for(int i=0; i<N; i++)
			ARR[i] = sc.nextInt();

		dfs(0, -1);

		if (S == 0)
			ANS -= 1;

		System.out.println(ANS);
	}

	public static void dfs(int val, int depth){

		/**
		 * 부분 수열을 전부 구하고, 부분수열의 합과 S 를 비교할려고 한다.
		 * depth + 1 == N 이면 tree 에서 부분수열을 전부 구한 단계이고, 부분수열의 합인 val 이 S 와 같으면 ANS++
		 * depth 를 -1에서 시작하여 depth + 1 을 N 과 비교하는 이유는, ARR[depth + 1] 할때 INDEX OUT OF BOUND 에러를 방지하기 위함이다.
		 */
		if(depth + 1 == N){ // 부분수열을 전부 구하기 때문에, depth 가 N 이 되면 부분수열의 합을 S 와 대조해본다.
			if(val == S)
				ANS++;
			return;
		}

		dfs(val + ARR[depth + 1], depth + 1); // TREE 에서 왼쪽 경로로 탐색하는 경우
		dfs(val, depth + 1); // TREE 에서 오른쪽 경로로 탐색하는 경우
	}
}

🛠 리뷰

recursion 그러니까 dfs를 구현해서 문제를 여럿 풀어봤다고 생각했는데, 여전히 dfs를 구현하는 과정이 어려운것 같다.
초기값이 뭔지, 어느 depth에서 return할 것인지, 어떤 값을 return할 것인지 고민하는게 중요하고 경우에 따라
특정 depth에서 계산을 통해 바뀐 state를 return후 돌려놓는 작업도 필요하다.
방법이 있나, 될때까지 문제를 많이 풀어보는 수밖에