섹션 8. DFS, BFS 활용 1. 합이 같은 부분집합(DFS : 아마존 인터뷰)

문제

• N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
• 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
• 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
• 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다

입력

• 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
• 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

출력

• 첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

입출력 예제

---

풀이방식

재귀함수란 자기가 자기 자신을 호출하는 함수이며, 스택 프레임을 사용한다.

---

재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

---

설계과정

1. YES가 발견되면 그 뒤에 재귀함수는 모두 넘기고 리턴한다.

2. 부분집합들의 누적합이 절반이 넘으면 더 구할 필요가 없으므로 리턴한다.

3. 모든 레벨에 대해 탐색을 끝냈다면 원소의 전체 합에서 부분집합의 누적합을 뺀다.

4. 그 값이 sum이면 즉, total의 절반 값이면 결과를 YES로 변경하고 flag를 true로 바꿔준다.

5. 탐색이 끝나지 않았다면 부분집합에 사용할때에는 DFS(L+1, sum+arr[L], arr) 을 매개변수로 넣어준다.

6. 부분집합에 사용하지 않을 때에는 DFS(L+1, sum, arr) 을 매개변수로 넣어준다.

---

풀이과정

1. 각 변수들을 선언 및 초기화한다.

• result : 결과를 저장할 변수로, NO 로 초기화한다.
• total : 전체 배열 원소의 합이다.
• sum : 부분집합의 누적합이다.
• flag : YES가 발견되면 그 뒤의 재귀함수는 모두 넘기기 위해 선언한다.

2. DFS 메소드를 작성한다.

 

3. flag가 true이면 리턴한다.

• 이는 즉 result가 YES임을 의미한다. 이미 YES에 해당하는 값을 찾았다면 그 뒤는 더 탐색할 필요가 없으므로 리턴한다.

4. sum이 total / 2 보다 크다면 리턴한다.

• 부분집합의 누적합이 전체합의 절반보다 크다면 해당 부분집합은 true 가 아니므로 바로 리턴한다.

5. L과 N이 같은 상황에서 total - sum이 sum과 같다면 result를 YES로 바꾸고 flag를 true로 바꾼다.

• L과 N이 같다면 모든 레벨의 탐색을 끝냈다는 것을 의미한다.
• total - sum == sum 은 부분집합의 누적합이 전체합의 절반이라는 의미이다. 즉, 두 부분집합의 합이 동일하다.

6. L과 N이 다르다면 탐색을 계속해야 한다. 해당 원소가 부분집합에 사용된다면 DFS(L+1, sum+arr[L], arr) 을 매개변수로 넣어준다.

• sum에 배열의 원소 값을 누적시킨다.

7. 해당 원소가 부분집합에 사용되지 않는다면 DFS(L+1, sum, arr) 을 매개변수로 넣어준다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.