okayoki

#작성 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int visit[8];
vector<int> v;

void dfs(int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
		return;		// 출력 후에는 dfs함수를 반드시 종료시켜야한다 
	}
	
	for(int i=1; i<=N; i++){
		if( visit[i]==M ) continue;	// 최대 M번까지 방문할 수 있도록 
		visit[i]++;
		v.push_back(i);
		dfs(cnt+1);
		visit[i]--;
		v.pop_back();
	}
}

int main(){
	cin>>N>>M;
	dfs(0);
	return 0;
} 

##

앞의 문제들과 달리 중복순열을 구해야 한다.

visit배열을 int 형 배열로 선언하여 한 숫자를 최대 M번 사용할 수 있도록 했다.

#작성 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> v;
bool visit[9];

void dfs(int idx, int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
	}
	
	for(int i=idx+1; i<=N; i++){
		if( visit[i] == true ){
			continue;
		}
		visit[i] = true;
		v.push_back(i);
		dfs(i, cnt+1);
		visit[i] = false;
		v.pop_back();
	}
}
int main(){
	cin>>N>>M;
	dfs(0, 0);
	return 0;
}

##

앞의 15649문제와 다른 점은 오름차순으로 중복 없는 순열을 출력해야 한다는 것이다.

=> DFS호출시에 현재 idx를 매개변수로 함께 넣어줘서 방문할 숫자를 해당 dfs의 idx에서부터 시작하도록 하였다.

dfs(0, 0)으로 호출했으므로 자연수 1부터 방문해야하니까 i = idx+1 ~ i<=N

#작성 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
bool visit[9];
int cnt;
vector<int> v;

void dfs(int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
		return;
	}
	
	for(int i=1; i<=N; i++){
		// 앞서 방문했던 숫자는 방문x 
		if( visit[i] == true ){
			continue;
		}
		visit[i] = true;
		v.push_back(i);
		dfs(cnt+1);		//재귀함수로 구현한 DFS. i로 시작하는 이하 dfs 수행한다. 
		visit[i] = false;
		v.pop_back();
	}
}
int main(){
	cin>>N>>M;
	// 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 모두 출력.
	dfs(0);
	return 0;
}

##

순열을 구현할 아이디어를 검색을 통해 얻었다.

순열은 조합과 달리 {1, 2}와 {2, 1}을 다른 것으로 취급한다.

#작성 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool comp( pair<int, string> a, pair<int, string> b){
	return a.first<b.first;
}
int main(){
	int N;
	vector< pair<int,string> > v;
	cin>>N;
	for(int i=0; i<N; i++){
		int age;
		string name;
		cin>>age>>name;
		v.push_back( pair<int,string>(age, name) );
	}
	
	stable_sort(v.begin(), v.end(), comp);
	for(vector< pair<int,string> >::iterator i=v.begin(); i<v.end(); i++){
		cout<<i->first<<' '<<i->second<<'\n';
	}
	return 0;
}

##

나이가 같을 경우 기존의 순서 그대로 유지하기 위해서는 sort함수 대신 stable_sort함수를 사용해야 한다.

#작성 코드

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool comp( pair<int, int> a, pair<int, int> b){
	if( a.second == b.second ){
		return a.first < b.first;
	}
	return a.second<b.second;
}

int main(){
	vector< pair<int, int> > v;
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v.push_back(pair<int, int>(x, y));
	}
	
	sort(v.begin(), v.end(), comp);
	for(vector< pair<int, int> >::iterator i=v.begin(); i<v.end(); i++){
		printf("%d %d\n", i->first, i->second);
	}
	return 0;
}

##

11650번과 정렬 기준이 되는 comp함수의 내용만 살짝 다르다.

#작성 코드

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool comp( pair<int, int> a, pair<int, int> b){
	if( a.first == b.first ){
		return a.second < b.second;
	}
	return a.first<b.first;
}

int main(){
	vector< pair<int, int> > v;
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v.push_back(pair<int, int>(x, y));
	}
	
	sort(v.begin(), v.end(), comp);
	for(vector< pair<int, int> >::iterator i=v.begin(); i<v.end(); i++){
		printf("%d %d\n", i->first, i->second);
	}
	return 0;
}

##

vector iterator의 사용!

vector < pair<int, int> >::iterator i = v.begin()

i는 벡터 v의 시작 벡터를 가리키는 포인터처럼 동작. => i->first, i->second 처럼 각 벡터의 pair에 접근해야한다.