알고리즘 암기할 코드들

순열 nPr

순서에 관계있게 뽑는 경우의 수

#include <bits/stdc++.h>
using namespace std;

void printV(vector<int> &v){
	for(int i=0; i<v.size();i++){
		cout << v[i] << " ";
	}
	cout << "\n";
}

int main() {
	int a[3]={1,2,3};
	//벡터에 원소 채우기 
	vector<int> v;
	for(int i=0;i<3;i++) v.push_back(a[i]); //오름차순 순열
	//순열 출력 
	do{
		printV(v);
	}while(next_permutation(v.begin(), v.end())); 
	
	return 0;	
}

 

조합 nCr

순서와 관계없이 한번씩만 뽑는 경우의 수

r<=3일때 중첩 for문

"r 횟수만큼 for문 중첩하기"

#include <bits/stdc++.h>
using namespace std;

int n=5, k=3;

int main(){
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				cout << i << " " << j << " "<< k<< "\n";
			}
		}
	}
	
	
	return 0;
}

r>=4일때 재귀 사용

#include <bits/stdc++.h>
using namespace std;

int n=5, k=3; 

//원소 출력 
void printV(vector<int> &v){
	for(int i=0;i<v.size();i++){
		cout << v[i] << " ";
	}
	cout << "\n";
}

void combi(int start, vector<int> &v){
	if(v.size()==k){ //끝에 다다랐을때 
		printV(v);
		return;
	}
	//원소 뽑아서 추가하기 
	for(int i=start+1;i<n;i++){
		v.push_back(i);
		combi(i, v);
		v.pop_back();	
	}
	return;	
}
int main(){
	vector<int> v; //원소 없는 벡터 생성
	//조합 함수 
	combi(-1, v);
	return 0;
}

 

 문자열 쪼개는 split() 함수

#include <bits/stdc++.h>
using namespace std;

vector<string> split(string input, string delimeter){
	vector<string> ret; //리턴할 벡터(문자열 쪼갠 것 저장한 벡터) 
	long long pos=0; //위치
	string token = ""; //문자열 토큰 
	while((pos=input.find(delimeter)) != string::npos){ //못찾을때까지 반복 
		token = input.substr(0,pos); //delimeter 전까지 문자열 추출 
		ret.push_back(token); //벡터에 저장 
		input.erase(0, pos+delimeter.length()); //delimeter 전까지 지우기 
	}
	ret.push_back(input); //마지막 남은 문자열 저장
	return ret; 
}

int main(){
	string s="안녕하세요 저는 알고리즘을 공부하고 있어요", d=" ";
	vector<string> a = split(s,d); //문자열, delimeter(구분자)
	for(string b: a) cout << b << "\n";