재귀함수

정의

• 재귀함수는 정의 단계에서 자기 자신을 호출하는 함수

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

• 큰 문제를 작게 나누어 해결하는데 사용함

예시

팩토리얼 n!

그 항까지의 수를 모두 곱하는 것

int fac(int n){
    if(n == 1 || n == 0){
        return 1;
    }
    return fac(n-1) * n;
}

피보나치 수열

전의 항과 그 전의 항을 더하여 이어나가는 수열

int fibo(int n) {
    cout << n << endl;

    if (n == 0 || n == 1) {
        return n;
    }
    return fibo(n - 1) + fibo(n - 2);
}

주의사항

• 반드시 기저사례를 사용해야함 (종료조건)

• 사이클이 있다면 사용하면 안됨
  ex) f(a)가 f(b)를 호출한 후, 다시 f(b)가 f(a)를 호출하는 경우

• 반복문으로 해결된다면 반복문으로 해결

순열 (permutation)

정의

순서와 상관이 있게 뽑음 >> 순열

순서와 상관이 없게 뽑음 >> 조합

next_permutation 함수

오름차순으로 정렬된 배열을 기반으로 배열을 만듦

사용법

next_permutation(시작부분, 끝부분);

#include <iostream>

using namespace std;

int main() {
    int arr1[] = {1, 2, 3};

    do {
        for (int i : arr1) {
            cout << i << " ";
        }
        cout << endl;
    } while (next_permutation(arr1, arr1 + 3));
}

#include <iostream>

using namespace std;

int main() {
    vector<int> arr2 = {1, 2, 3};

    do {
        for (int i : arr1) {
            cout << i << " ";
        }
        cout << endl;
    } while (next_permutation(arr2.begin(), arr2.end());
}

주의

오름차순으로 정렬이 안된 배열은 오름차순으로 정렬해주어야함

n개 중에서 r개를 뽑는 경우의 수

prev_permutation 함수

내림차순으로 정렬된 배열을 기반으로 배열을 만듦

재귀함수로 순열 구현하기

#include <iostream>

using namespace std;
vector<int> v;
void printV(vector<int> &v) {
   for (int i = 0; i < v.size(); i++) {
       cout << v[i] << " ";
   }
   cout << endl;
}
void makePermutation(int n, int r, int depth) {
   cout << n << " : " << r << " : " << depth << endl;

   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]);
   }
   return;
}
int main() {
   for (int i = 0; i <= 3; i++) {
       v.push_back(i);
   }
   makePermutation(3, 3, 0);
}

쉬우니까 외워서 쓰도록 하자...(?)

조합

정의

순서따위는 상관 쓰지 않음

그저 몇 명을 뽑아갈 때 조합을 씀

구현 (재귀함수)

4개 이상 뽑는 경우는 재귀함수를 쓰고

그 이하는 반복문 씀

#include <iostream>

using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void print(vector<int> b) {
    for (int i : b) {
        cout << i << " ";
    }
    cout << endl;
}

void combi(int start, vector<int> b) {
    if (b.size() == k) {
        print(b);
        return;
    }
    for (int i = start + 1; i < n; i++) {
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
}

int main() {
    vector<int> b;
    combi(-1, b);
}

이거도 외워서 쓰자...

구현 (반복문)

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

split() 함수

문자열을 특정 기준으로 쪼개서 배열화 시키는 함수

c++은 그런거 없어서 만들어야됨

코드

#include <iostream>

using namespace std;

vector<string> split(string input, string delimiter) {
    vector<string> ret;
    long long pos = 0;
    string token = "";
    while ((pos = input.find(delimiter)) != string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos + delimiter.length());
    }
    ret.push_back(input);
    return ret;
}

int main() {
    string s = "윤태섭 틱톡 그만 찍어, 아니 오직 '그' 만 찍어", d = " ";

    vector<string> a = split(s, d);
    for (string b : a) {
        cout << b << endl;
    }
}

아래 3줄만 외워서 쓰자...

    while ((pos = input.find(delimiter)) != string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos + delimiter.length());

중복 요소 제거

map

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

map<int, int> mp;
int main() {
   vector<int> v = {1, 1, 2, 2, 3, 3, 4, 4};

   for (int i : v) {
       if (mp[i]) {
           continue;
       } else {
           mp[i] = 1;
       }
   }
   vector<int> ret;
   for (auto it : mp) {
       ret.push_back(it.first);
   }
   for (int i : ret) {
       cout << i << endl;
   }
}

Unique()

범위 안 요소들을 앞에서부터 차례대로 서로를 비교해가며 중복된 요소를 제거함

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

vector<int> v;

int main() {
    for (int i = 1; i <= 5; i++) {
        v.push_back(i);
        v.push_back(i);
    }
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
    auto it = unique(v.begin(), v.end());
    cout << it - v.begin() << endl;

    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
}

주의

오름차순으로 정렬해서 사용할 것

시간복잡도

입력 크기에 대하여 어떤 알고리즘이 실행되는데 걸리는 시간

빅오표기법 (Big-O notation)

복잡도에 영향을 많이 미치는 항의 상수 인자를 제외하고 나머지 항을 제거하여 복잡도를 나타내는 표기법

누적합 prefix sum

이론

어떤 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이용하는 것

연습문제

답

#include <iostream>

using namespace std;

int a[100004], b, c, psum[100004], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b >> c;
        cout << psum[c] + psum[b - 1] << endl;
    }
}

마무리

1주차 내용까지