백준 1182번 부분수열의 합(C++) 알고리즘을 풀며 반성..

문제

1182번: 부분수열의 합

https://www.acmicpc.net/problem/1182

정답 코드

#include<bits/stdc++.h>
using namespace std;
int n,s;
int cnt;
int num[21];
int ret[21]; // 결과를 담을 배열
void	func(int k,int tot)
{
	if (k == n)
	{
		if (tot == s)
			cnt++;
		return ;
	}
	func(k+1,tot);
	func(k+1,tot+num[k]);
}

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n>>s;
	for (int i=0;i < n;i++) cin >> num[i];
	func(0,0);
	if ( s== 0 )
		cnt --;
	cout << cnt;
}

문제 풀이의 흐름

바킹독 흐름을 따라간다.

[실전 알고리즘] 0x0C강 - 백트래킹

이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는 경우도 있습니다. 앞 단원에서 재귀를 충실하게 익혔다면 그렇게까지는 어렵지 않을 수 있으니까 너무 걱정은 마시고 백트래킹을 시작하겠습니다. 먼저 백트래킹에 대해 설명을 드리고 관련 문제들을 풀어보는 방식으로 진행하겠습니다.

https://blog.encrypted.gg/945

주의 할 점

그냥 백드래킹을 혼자서 안 해봐서 그런지.. 너무 오래걸렸다..

반성 및 고찰

실패 코드

#include<bits/stdc++.h>
using namespace std;
int n,s;
int cnt;
int num[21];
int vis[21];
void	func(int depth,int sum)
{
	if (depth == n + 1)//n개가 된 경우 0~n - 1까지가 원하는 만큼이므로 종료
		return ;
	// cout << "d : "<<depth << " ";
	if (depth != 0 && sum == s)
	{
		cout << depth << " ";
		cnt++;
	}
	for (int i=1;i <= n;i++)
	{
		if (vis[i] == 0)
		{
			vis[i] = 1;
			func(depth+1,sum + num[i]);
			vis[i] = 0;
		}
	}
}

int main()
{
	cin >> n>>s;
	for (int i=1;i <= n;i++) cin >> num[i];
	func(0,0);
	cout << cnt;
}

첫번쨰 오답코드의 경우 모든 경우 예를들어 {0,1,2} 의 경우에

0 ,1 ,2 | 1,2,0 | 0, 2,1 | 2,1,0 | 2,0,1 |1,0,2 이 모든게 다 다른 경우로 아마 들어갈것이다.

두번째 오답 코드

#include<bits/stdc++.h>
using namespace std;
int n,s;
int cnt;
int num[21];
int vis[21];
int ret[21]; // 결과를 담을 배열
void	func(int depth)
{
	if (depth == n)//n개가 된 경우 0~n - 1까지가 원하는 만큼이므로 종료
		return ;
	// cout << "d : "<<depth << " ";
	int sum = 0;
	for (int i=0;i < depth;i++)
		sum+=ret[i];
	if (depth != 0&& sum == s)
		cnt++;
	for (int i=1;i <= n;i++)
	{
		if (depth != 0 && num[depth -1] < i)
			continue;
		if (vis[i] == 0)
		{
			vis[i] = 1;
			ret[depth] = num[i];
			func(depth+1);
			vis[i] = 0;
		}
	}
}

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n>>s;
	for (int i=1;i <= n;i++) cin >> num[i];
	func(0);
	cout << cnt;
}

난 바보다.

속상하다.

쉬운 문제인데도 못푸는 내가 너무 스트레스다.

이 문제를 위해서 2시간을 넘게 잡고 있었는데도 혼자 힘으로 못 풀고 결국 답지를 본 나 자신이 너무 싫다. 내가 멍청한 것 같고 코딩을 해도 되나라는 생각이 자꾸 든다.

나의 알고리즘 열등감이 또 쌓여간다.

백준 골드 3을 달성했지만 할 줄아는 알고리즘만 계속 하고, 거의 다 dfs 그리디 문제들이여서 편식 그 자체를 했었다. 사실 내 실력은 실버는 될까..

속상하다.속상해. 알고리즘 공부는 너무 힘들다.

그래도 하루 한문제씩은 해봐야지…

Uploaded by N2T