0주차: 재귀, 순열, 조합, split

출처: https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C 

10주완성 C++ 코딩테스트 | 알고리즘 IT취업 - 인프런 | 강의

수업들으면서 정리한 글입니다. 

<bits/stdc++.h> 헤더 파일

string,vector,array 등등 자주 쓰이는 라이브러리들이 한번에 컴파일된다.

C++ #include 헤더 사용하기

재귀함수

재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수

전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수

큰 문제를 작은 부분문제로 나눠서 풀 때 사용

주의사항

• 반드시 기저사례를 써야 한다.(종료 조건)
• 사이클이 있다면 쓰면 안된다.
  • ex) f(a)가 f(b)를 호출한 뒤 다시 f(b)가 f(a) 호출
• 반복문으로 될 것 같으면 반복문으로(함수호출에 대한 cost)

예시)

팩토리얼 n! : 그 이전의 항을 모두 곱하는 것, 비슷한 것을 곱하는 것을 반복함

• 지금까지 곱한것에 현재 원소 곱하기 1 2 6 24.. 
  • f(n) = n*f(n-1)

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

int fact(int n){
	if(n==0 || n==1) return 1; //return n 아님 
	return n*fact(n-1);
}
int main() {
	cout << fact(5)<<endl; 
}

 

피보나치: 이전 두개 더하기

0,1,1,2,3,5,8,13,21,34,55,89

• 점화식 Fn=Fn-1 + Fn-2

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

int fibo(int n){
	if(n==0||n==1) return n;
	return fibo(n-1)+fibo(n-2);
}
int main() {
	cout << fibo(4) << endl;
}

 

재귀함수는 느리다. 반복문이 더 빠르다

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

int fact_it(int n){
	int ret=1;
	for(int i=1;i<=n;i++){
		ret *=i;
	}
	return ret;
}

int main() {
	cout << fact_it(4) << endl;
}

피보나치는 반복문으로 하기 어렵다(DP사용)

순열

공식을 기억하자

‘순서에 관계있게’ 뽑기

next_permutation(시작it, 포함되지않는 끝it) : 오름차순의 배열을 기반으로 한 순열, 주로 사용

prev_permutation(시작it, 포함되지않는 끝it) :내림차순의 배열을 기반으로 한 순열

→ 함수 사용 전에 배열의 원소들이 미리 오름차순 또는 내림차순으로 정렬된 상태여야 한다.

next_permutation

#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;	
}

vector.clear() : 벡터 size를 0으로 만들어 clear한다.

c++ vector clear 함수 : size를 0으로 만들어 준다.

v.end()는 마지막 원소의 다음 위치를 가리킨다.

next_permutation시에 두번째 인자는 포함X

⇒ next_permutation(v.begin(), v.end());이면 처음부터 끝 원소까지 순열

prev_permutation

#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=2;i>=0;i--) v.push_back(a[i]); //내림차순 배열

	//순열 만든다
	do{
		printV(v);
	} while(prev_permutation(v.begin(), v.end()));
	v.clear();
	return 0;
}

v[0]부터 v[1]까지의 원소만 순열로 만든다

do{
		printV(v);
	} while(next_permutation(v.begin(), v.begin()+2));

출력:

123

213

재귀함수로 순열 만들기

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

int a[3]={1,2,3};
vector<int> v;

//벡터 출	
void printV(vector<int>&v){
	for(int i=0;i<v.size();i++){
		cout << v[i] << " ";
	}
	cout << "\\n";
}
//nPr, depth: 바꿀 원소 인덱스 
void makePermutation(int n, int r, int depth){
	if(depth==r){ //끝에 다다랐을때 
		printV(v);
		return;
	}
	//원소 위치 바꿔주기 
	for(int i=depth;i<n;i++){
		swap(v[i], v[depth]);
		makePermutation(n,r,depth+1);
		swap(v[i], v[depth]); //원 상태로 바꾸기(swap한거 다시 swap) 
	}
	return;
}

int main(){	
	for(int i=0;i<3;i++)v.push_back(a[i]);
	makePermutation(3,3,0); //depth는 0부터 시작 
	
	return 0;
}

logic

쉽게 정리

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

    int a[]={1,2,3};
    int n=3,r=3; //3P3


    void makePermutation(int n, int r, int depth){
        if(r==depth){
            //logic
            for(int e:a) cout << e << " "; //출력하기
            cout <<"\n";
            return;
        }
        //조합 만들기(원소 순서 바꾸기)
        for(int i=depth;i<n;i++){
            swap(a[depth], a[i]); //swap
            makePermutation(n,r,depth+1);
            swap(a[depth], a[i]); //복원
        }
    }
    int main(){
        makePermutation(n,r,0); //n,r,depth(0부터 시작)

        return 0;
    }

 

재귀 함수로 조합 만들기(암기)

k=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;
}

logic

중첩 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;
}

두개 뽑을때는 for문 2번 작성

인덱스 기반이므로 실제 배열 쓸때는 마지막에 배열의 인덱스로 작성하기

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

int n=5, k=3;
int a[5]={2,4,6,8,10};

void printV(vector<int> v){
	for(int i=0;i<v.size();i++){
		cout << a[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;
}

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

int n=5, k=3;
int a[5]={3,2,4,6,5};
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 << a[i] << " " << a[j] << " "<< a[k]<< "\\n";
			}
		}
	}
	
	
	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"; 
}

출력

• string::find : 찾는 문자열의 첫번째 인덱스 반환
• string::npos : 찾는 문자열이 없는 경우 npos 반환

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

int main(){
	string str = "Hello World";
	if(int ret = str.find("hello")){
		cout << "true"<<endl;
		cout << ret; //-1
	}
}

[C++] string::find / string::npos 를 이용한 단어 유무 찾기

⇒ find 함수에서 문자열 찾으면 첫번째 원소 인덱스, 못찾으면 npos 반환

• substr(첫번째 인덱스, 문자열 길이) : 첫번째 인덱스부터 문자열 길이 만큼 추출

문자열 길이 안쓸경우 npos로 인식하여 끝까지 추출

substr

 

split 함수 쉽게 쓰는 방법

문자열 파싱 함수 - istringstream, ostringstream, stringstream

https://myprivatestudy.tistory.com/48

문자열 파싱 함수 - istringstream, ostringstream, stringstream