질문있습니다!!

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

60. 합이 같은 부분 집합 (아마존 인터뷰 문제 : DFS 완전탐색)

작성

422

안녕하세요 선생님 저는 59번 문제를 참고하여 진행을 하였습니다.

제가 작성한 코드중에서 뭐가 틀린건지 봐주시면 감사드리겠습니다.

틀린 부분을 잘 몰라 질문 올립니다.

#include <iostream>
#include <vector>
using namespace std;
int n, tatal = 0;
int ch[11];
int a[11];
void DFS(int L, int sum)
{
    int sum2 = 0;
    if (L == n + 1)
    {
        for (int i = 1; i <= n; i++)
        {
            if (ch[i] == 1)
            {
                sum = sum + a[i];
            }
            if (ch[i] == 0)
            {
                sum2 = sum2 + a[i];
            }
        }
        if (tatal - sum == sum2)
        {
            cout << "YES";
        }
        else
        {
            cout << "NO";
        }
    }
    else
    {
        ch[L + 1] = 1;
        DFS(L, sum);
        ch[L + 1] = 0;
        DFS(L, sum + a[L]);
    }
    
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        tatal = tatal + a[i];
    }
    DFS(1, 0); //시작점 합
}

c++코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

재귀함수 안에서 YES, NO를 출력하면 매번 부분집합의 경우가 완성될 때마다 YES, NO가 출력됩니다.

그리고 ch[L] = 1로 체크하고 DFS(L+1, sum+a[L])와 같이 해야 합니다.

개선된 코드를 넣어드립니다. 분석해보세요.

#include<bits/stdc++.h>
using namespace std;
int n, total = 0;
int ch[11];
int a[11];
int flag = 0;
void DFS(int L, int sum)
{
    if(flag) return;
    if (L == n + 1)
    {
    	cout<<sum<<" "<< total - sum<<endl;
        if((total - sum) == sum) flag = 1;
    }
    else
    {
        ch[L] = 1;
        DFS(L+1, sum + a[L]);
        ch[L] = 0;
        DFS(L+1, sum);
    }
    
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        total = total + a[i];
    }
    DFS(1, 0); //시작점 합
    if(flag) cout<<"YES";
    else cout<<"NO";
}

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요.

코드를 보면서 문제점을 찾을 때, 원하는 결과가 얻어지지 않는 경우일 수도 있으니 문제에서 요구하는 결과와 비교해보는 것도 중요합니다.

제가 보았을 때, 오타는 없는 것 같지만 다음과 같은 문제점이 있을 수 있습니다.

DFS 함수에서 sum 전달 값에 동일 변수(sum)를 이용하여 누적시키고 있어 잘못된 결과를 만들 수 있습니다. sum이라는 변수를 다른 변수명으로 변경하여 사용하십시오.
DFS 함수에서 L+1을 ch[L+1]로 변경하여 처리합니다. 이 부분을 ch[L]=1, ch[L]=0 으로 변경하여 처리하시면 됩니다.
탈출 조건인 L == n+1 일 때 결과 출력을 누락하고 있으니 결과 출력을 추가하면 됩니다.

다음은 수정된 코드입니다.

#include
#include
using namespace std;

int n, tatal = 0;
int ch[11];
int a[11];

void DFS(int L, int sum)
{
int sum2 = 0;
if (L == n + 1)
{
for (int i = 1; i <= n; i++)
{
if (ch[i] == 1)
{
sum = sum + a[i];
}
else if(ch[i] == 0)
{
sum2 = sum2 + a[i];
}
}
if (tatal - sum == sum2)
{
cout << “YES” << endl;
exit(0);
}
return;
}
else
{
ch[L] = 1;
DFS(L+1, sum);
ch[L] = 0;
DFS(L+1, sum + a[L]);
}
}

int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
tatal = tatal + a[i];
}
DFS(1, 0); //시작점 합
cout << “NO” << endl;
return 0;
}

이상입니다. 참고하시길 바랍니다. :)

인프런 커뮤니티 질문&답변

질문있습니다!!