22.07.07

61. 특정 수 만들기(DFS : MS 인터뷰)

void DFS(int l){
	
	
	
	if(l==n){
		int sum=0;
		for(int i=0; i<cnt.size();i++){
			if(cnt[i]==1){
				sum+= nums[i];
			}
			else if(cnt[i]==-1){
				sum-= nums[i];
			}
		}
		if(sum == m){
			answer++;
		}
		return;
	}
	
	else{
		
		
		cnt[l]=1;
		DFS(l+1);
		cnt[l]=0;
		DFS(l+1);
		cnt[l]=-1;
		DFS(l+1);
	}
	
}

int main(){
	//freopen("input.txt","rt",stdin);	
	cin>>n>>m;
	int tmp;
	for(int i=0; i<n; i++){
		cin>>tmp;
		nums.push_back(tmp);
	}

	DFS(0);
	if(answer==0) cout<<-1;
	else cout<<answer;
	return 0;
}

처음에 풀 때는 sum 값에 index l 에 있는 값을 더하거나 그대로 두거나 빼는 형식으로 계속 업데이트 한 후에 l이 마지막 깊이까지 도달하면 sum이 m과 같은지 확인하는 형식으로 코드를 작성했는데, 이렇게 했을 때 문제점이 sum 값이 어떻게 변하는지 추적하기가 너무 힘들고 내가 생각한대로 업데이트가 되지 않았다.
그래서 그냥 이전에 부분집합 문제에서와 동일하게 cnt vector의 인덱스를 1,0,-1 로 구분하고 l이 마지막 깊이에 도달하면 cnt를 돌면서 해당 값에 따라 대응되는 nums의 인덱스에 있는 값을 더하거나 빼는 형식으로 코드를 작성했다.

62. 병합정렬

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
int n;
vector<int> nums;
vector<int> v(100,0);
int tmp;
void divide(int lt, int rt){
	int mid;
	if(lt<rt){
		mid = lt + (rt-lt)/2;
		
		divide(lt,mid);
		divide(mid+1,rt);
	
	
	int p1 = lt;
	int p2 = mid+1;
	int p3 = lt;
	while(p1<=mid&&p2<=rt){
		
		if(nums[p1]>nums[p2]){
			v[p3++]=nums[p2++];
		}
		else v[p3++]=nums[p1++];
	}
	while(p1<=mid) v[p3++] = nums[p1++];
	while(p2<=rt) v[p3++] = nums[p2++];
	
	for(int i: nums)
		cout<<i<<' ';
	cout<<"mid:"<<mid<<"left:"<<lt<<endl;
	
	for(int i=lt; i<=rt; i++){
		nums[i] = v[i];
	}
	}
}

int main(){
	freopen("input.txt","rt",stdin);	
	
	
	cin>>n;
	
	for(int i=0; i<n; i++){
		cin>>tmp;
		nums.push_back(tmp);
	}
	
	divide(0,n-1);
	
	for(int i: nums){
		cout<<i<<' ';
	}
}

병합정렬에 대해 배웠다. 재귀함수를 이용하여 배열을 반으로 나눈 뒤 병합정렬하여, 전체 배열을 정렬하는 방식이다. 코드가 복잡해서 이해하기가 처음에는 조금 어려웠다. 병합정렬은 정렬방법 중 퀵정렬 다음으로 빠른 정렬 방법이다.