실제 코딩테스트에서 써먹으려고 미리 정리해둔 포스트

알고리즘 파트가 너무 길어져 이렇게 2편으로 분리했다.

무려 2년만의… 재포스팅!

그럼 시작해보자

🍭 자주 사용하는 알고리즘 간단 정리

🔶 I. 탐색 및 정렬

💠 Sort

STL의 sort는 quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 n log n 이다.

#include<iostream>
#include<algorithm>

int arr[10] = {3, 7, 2, 4, 1, 0, 9, 8, 5, 6};

sort(v.begin(), v.end(), greater<int>());
// 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

함수	설명
`sort(arr, arr+n)`	0 ~ n까지 오름차순으로 정렬
`sort(v.begin(), v.end())`	처음부터 끝가지 오름차순으로 정렬
`sort(v.begin(), v.end(), compare)`	사용자 정의 함수 사용해서 정렬
`sort(v.begin(), v.end(), greater<자료형>())`	내림차순 (Descending order) 정렬
`sort(v.begin(), v.end(), less<자료형>())`	오름차순 (Ascending order) 정렬

💠 Binary Serach

오름차순으로 정렬된 리스트에서 특정한 위치를 찾는 알고리즘

정렬된 리스트에서만 사용할 수 있음
검색할 떄마다 선형탐색과는 비교할 수 없는 속도 : log_2 N

binary_search(arr.begin(), arr.end(), 찾으려는값)      // 있으면 true, 없으면 false

아래는 이진탐색을 직접 구현한 코드. STL에서는 bool이지만, 내가 잘 쓰려고 int로 바꿨다.

// 못찾았으면 -1 리턴, 찾았으면 index값 리턴
int binary_search(vector<int>& arr, int len, int target){
    int low = 0, high = len - 1;
    
    while(low <= high){
        int mid = (low + high) / 2;
        
        //원하는 값을 찾았다면 true 반환
        if(target == arr[mid])    return true;
        
        // 원하는 값이 더 작다면 검사 범위를 더 낮게 잡아야 한다.
        if(target < arr[mid]){
            high = mid - 1;
        }
        // 원하는 값이 더 크다면 검사 범위를 더 크게 잡아야 한다.
        else if(target > arr[mid]){
            low = mid + 1;
        }
    }
    return false; // 마지막까지 못찾는다면 false 반환
}

재귀함수로도 구현 가능

int binary_search(vector<int>& arr, int low, int high, int target){
    if(low > end)    return -1;
    int mid = (low + high) / 2;

    if(arr[mid] == target)    return mid;

    // 찾는 수가 더 작다면, 검사 범위를 더 작게 잡아야 한다.
    if(arr[mid] > target)
        return binary_search(arr, low, mid - 1, target);

    // 찾는 수가 더 크가면, 검사 범위를 더 크게 잡아야 한다.
    else
        return binary_search(arr, mid + 1, high, target);
}

코드 출저 : [C++ Algorithm] 이분 탐색(Binary Search)

💠 Lower Bound와 Upper Bound

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는 함수

반대 상황 (찾으려는 key값을 초과하는 숫자를 찾을 때) 에서는 upper_bound사용

정렬된 리스트에서만 사용할 수 있음
검색할 떄마다 선형탐색과는 비교할 수 없는 속도 : log_2 N

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

int main() {

    vector<int> arr = { 1,2,3,4,5,6,6,6 };
    cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

    // 결과 -> lower_bound(6) : 5

    return 0;
}

코드 출저 : 알고리즘 - c++ lower_bound, upper_bound 활용하기

🔶 II. 그래프

공부하는 식빵맘님 블로그에서 아주 잘 정리된 표가 있어서, 가져왔다.

BFS	다익스트라	벨만포드	플로이드 와샬
가중치가 있는 그래프 ❌불가능 가중치가 모두 동일하거나 없어야 한다.	가중치가 모두 다른 그래프 ⭕가능	가중치가 모두 다른 그래프 ⭕가능	가중치가 모두 다른 그래프 ⭕가능
가중치 없고 모두 동일한 중요도를 가져야 함	가중치가 양의 정수일 때만 가능하다.	가중치가 음의 정수일 때도 가능하다.	가중치가 음의 정수일 때도 가능하다. (단, 음의 사이클이 없어야 한다.)
큐 사용	우선순위 큐 사용	Dynamic Programming 방식 distance[n] = min(distance[n], distance[m] + E(m, n))	Dynamic Programming 방식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]) 이차원 배열(행렬) 사용
`O(E)`	우선순위 큐를 사용할 경우 `O(ElogV)`	`O(VE)`	3중 for문을 사용하므로 `O(V^3)`
하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 `1:N`	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 `1:N`	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 `1:N`	모든 정점들간의 쌍에 대해 최단 경로를 한번에 구함 `N:N`

💠 Dijkstra

다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.

다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다.

다익스트라는 배열을 이용해 구현할 수도 있고, 우선순위 큐를 이용해 구현할 수도 있다.

정점의 개수를 V, 간선의 개수를 E라고 했을 때

배열을 이용하는 경우 시간복잡도는 O(V^2) 이고 우선순위 큐를 이용하는 경우 O(ElogV)이다.

우선순위 큐를 사용하는게 훨씬 빠르고 간단하니 우선순위 큐를 이용한 방법을 살펴보자.

#include <vector>
#include <iostream>
#include <queue>

#define MAX 100                                         // 최대 정점의 개수 
#define INF 99999999

vector<int> dijkstra(int start, int V, vector<pair<int,int> > adj[]) {
    vector<int> dist(V, INF);                           // 전부 INF로 초기화 
    priority_queue<pair<int, int> > pq;
    
    dist[start] = 0;
    pq.push(make_pair(0, start));                       // 시작 정점 방문 
 
    while (!pq.empty()) {
        int cost = -pq.top().first;                     // 방문한 정점의 dist 값 
        int cur = pq.top().second;                      // 현재 방문한 정점 
        pq.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {     // 현재 방문한 정점의 주변 정점 모두 조사 
            int next = adj[cur][i].first;               // 조사할 다음 정점 
            int nCost = cost + adj[cur][i].second;      // 현재 방문한 정점을 거쳐서 다음 정점을 갈때의 비용 
            if (nCost < dist[next] ) {                  // 기존 비용보다 현재 방문한 정점을 거친 비용이 더 싸다면 
                dist[next] = nCost;                     // 갱신 
                pq.push(make_pair(-nCost, next));       // pq에 저장 
            }
        }
    }
    
    return dist;
}
 

// 사용 예
int main()
{
    int V,E;
    vector<pair<int, int> > adj[MAX];
    cout << "정점의 개수 입력 : ";
    cin >> V;
    cout << "간선의 개수 입력 : ";
    cin >> E;
 
    for (int i = 0; i < E; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back(make_pair(to, cost));    // 양방향 그래프 
        adj[to].push_back(make_pair(from, cost));
    }
 
    printf("\n===다익스트라 결과===\n");
    vector<int> dist = dijkstra(0, V, adj);
    for (int i = 0; i < V; i++) {
        printf("0번 정점에서 %d번 정점까지 최단거리 : %d\n", i, dist[i]);
    }
    return 0;
}

코드 출저 : [알고리즘] 다익스트라(Dijkstra) 알고리즘이란? : c++ 다익스트라 구현

💠 Bellman-ford

벨만포드 알고리즘은 ‘모든 경우의 수를 다 탐색해 가면서 최소비용’을 찾게 된다.

다익스트라 알고리즘과는 달리 그리디 하지 않게 동작한다.

모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 ‘한번이라도 계산 된 정점’ 이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트 한다.

1번 과정을 반복한다.

아래 코드를 실행하기 전, 다음 두 조건을 만족해야 한다.

Dist배열의 초기상태는 모두 'INF(무한대)' 로 초기화 되어 있는 상태이다.
그리고, ‘Edge’는 간선의 정보를 저장한 vector인데, Edge에는 { 시작점, 도착점, 비용 } 이 저장되어 있다.

void Bellman_Ford()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
 
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            cout << "음의 사이클이 존재하는 그래프입니다." << endl;
            return;
        }
    }
    cout << "음의 사이클이 존재하지 않는, 정상적인 그래프 입니다." << endl;
}

코드 출저 : [ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)

💠 Floyd-warshall

플로이드-와샬 알고리즘은 ‘모든정점’에서 ‘모든정점’으로의 최단 경로를 구하는 알고리즘이다.

int INF = 1000000;

int a[4][4] = {
  { 0, 5, INF, 8 },
  { 7, 0, 9, INF },
  { 2, INF, 0, 4 },
  { INF, INF, 3, 0 }
};

// 시간복잡도 V^3
for(int k = 0; k < 4; k++)              // k 는 거쳐가는 정점
  for(int i = 0; i < 4; i++)              // i 는 행 (출발 정점)
    for(int j = 0; j < 4; j++)          // j 는 열 (도착 정점)
      if (a[i][k] + a[k][j] < a[i][j])  // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
        a[i][j] = a[i][k] + a[k][j];

코드 출저 : 24. 플로이드 와샬(Floyd Warshall) 알고리즘

💠 Prim

그래프 내 모든 정점을 포함하는 트리 (신장트리, Spanning Tree)중에서, 가장 비용이 저렴한 트리를

최소 신장 트리 (Minimum Spanning Tree)라고 한다.

아래 예시는 프로그래머스 섬 연결하기 문제를 해결한 코드

코드 해설은 이 블로그를 참고했다.

우선, 주어진 costs 벡터를 활용하여 인접 행렬을 만들어주었다.

그 후, 방문한 섬과 방문하지 않은 섬의 인덱스를 구분해주기 위해,

시작 위치인 0을 visited 벡터에 넣고, 그 외의 섬들의 인덱스를 unvisited 벡터에 넣어주었다.

while문에서는 프림 알고리즘을 활용하여 다리를 선택해주었다.

즉, 방문한 섬에서 방문하지 않은 섬으로 연결할 수 있는 다리들 중 최소 비용이 드는 다리를 선택해주었다.

선택한 다리와 연결되어 있는 섬은 방문한 섬에 추가하고, 방문하지 않은 섬에서 제거해주었다.

위의 방식을 n - 1개의 다리를 선택할 때까지 수행하여 최종적인 최소 비용을 구해주었다.

(n - 1개의 다리를 설치해야 모든 섬을 연결할 수 있다.)

#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;

	vector<vector<int>> graph(n, vector<int>(n));
	for (int i = 0; i < costs.size(); i++)
	{
		graph[costs[i][0]][costs[i][1]] = costs[i][2];
		graph[costs[i][1]][costs[i][0]] = costs[i][2];
	}

	vector<int> visited;
	vector<int> unvisited;

	visited.push_back(0);
	for (int i = 1; i < n; i++)
		unvisited.push_back(i);

	for (int i = 1; i < n; i++)
	{
		int min = INT_MAX;
		int min_index = 0;

		for (int j = 0; j < i; j++)
		{
			for (int k = 0; k < n - i; k++)
			{
				if (graph[visited[j]][unvisited[k]] > 0 && min > graph[visited[j]][unvisited[k]])
				{
					min = graph[visited[j]][unvisited[k]];
					min_index = k;
				}
			}
		}

		visited.push_back(unvisited[min_index]);
		unvisited.erase(unvisited.begin() + min_index);
		answer += min;
	}

	return answer;
}

코드 출저 : [프로그래머스][그리디][C++] 섬 연결하기

🔶 III. 문자열

💠 KMP (Knuth-Morris-Pratt)

어떤 문자열에서 원하는 문자열을 검색할 때 그 검색어의 위치를 찾아주는 알고리즘이다.

N을 텍스트의 길이, M을 검색어의 길이라고 할 때, 시간복잡도는 O(N+M)

텍스트 안에 검색하고자 하는 검색어가 하나 일 때 사용한다. ( 텍스트 : 검색어 = 1 : 1)

using namespace std;

vector<int> Fail(string pattern) {
    int m = pattern.length();
    vector<int> pi(m); // partial match table

    pi[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j])
            j = pi[j - 1];
        if (pattern[i] == pattern[j])
            pi[i] = ++j;
    }
    return pi;
}

vector<int> KMP(string pattern, string text) {
    int m = pattern.length(); 
    int n = text.length(); 
    vector<int> pos; 
    vector<int> pi = Fail(pattern); 

    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j])
            j = pi[j - 1];
        if (text[i] == pattern[j]) { 
            if (j == m - 1) { 
                pos.push_back(i - m + 1);
                j = pi[j]; 
            }
            else j++; 
        }
    }
    return pos;
}

코드 출저 : (C++) 문자열 검색 알고리즘 : KMP 알고리즘

💠 Aho-Corasick

어떤 문자열에서 여러 문자열들을 동시에 찾아야 하는 상황에서 쓰이는 알고리즘 ( 텍스트 : 검색어 = 1 : 多)

ex) “cacachefcachy” 텍스트에 { “cache”, “he”, “chef”, “archy” } 中 하나라도 부분 문자열로 포함되어 있는지 찾기.

N을 텍스트의 길이, M을 검색어의 길이,k를 검색어의 개수라고 할 때, 시간복잡도는 O(N + M1 + M2 + ... + MK)

#include <bits/stdc++.h>

using namespace std;

struct Trie {                           // 노드 객체 클래스
public:
    bool isEnd;                         // 이 노드가 한 검색어의 끝인지 아닌지를 알려줌 
    string p;                           // 이 노드까지의 접두사 (아호 코라식의 필요한 부분은 아니다.)
    map<char, Trie*> child;             // 자식 노드 링크
    Trie* fail;                         // 실패 링크 ⭐

    Trie() : isEnd(false), fail(nullptr) {}

    void Insert(string pattern) {
        Trie* now = this;
        int m = pattern.length();
        for (int i = 0; i < m; ++i) {
            if (now->child.find(pattern[i]) == now->child.end())
                now->child[pattern[i]] = new Trie;
            now = now->child[pattern[i]];

            if (i == m - 1) {
                now->p = pattern;
                now->isEnd = true;
            }
        }
    }

    void Fail() {  // BFS + KMP
        Trie* root = this;
        queue<Trie*> q;

        q.push(root);

        while (!q.empty()) {
            Trie* now = q.front();
            q.pop();

            for (auto& ch : now->child) {

                Trie* next = ch.second;
                if (now == root)
                    next->fail = root;
                else {
                    Trie* prev = now->fail;
                    while (prev != root && prev->child.find(ch.first) == prev->child.end())
                        prev = prev->fail;
                    if (prev->child.find(ch.first) != prev->child.end())
                        prev = prev->child[ch.first];
                    next->fail = prev;
                }

                if (next->fail->isEnd)
                    next->isEnd = true;

                q.push(next);
            }
        }
    }
};

vector<pair<string, int>> KMP(string text, Trie* root) {
    Trie* now = root;
    int n = text.length();
    vector<pair<string, int>> answer;
    for (int i = 0; i < n; ++i) {
        while (now != root && now->child.find(text[i]) == now->child.end())
            now = now->fail;
        if (now->child.find(text[i]) != now->child.end())
            now = now->child[text[i]];
        if (now->isEnd) {
            answer.push_back({ now->p, i });
        }
    }
    return answer;
}

int main() {
    freopen("input.txt", "r", stdin);

    int N;
    cin >> N;
    vector<string> patterns(N);
    for (int i = 0; i < N; ++i)
        cin >> patterns[i];
    Trie* root = new Trie;
    for (int i = 0; i < N; ++i)
        root->Insert(patterns[i]);
    root->Fail();

    string text;
    cin >> text;

    vector<pair<string, int>> answer = KMP(text, root);
    cout << text << "에서 검색하기" << '\n';
    for (int i = 0; i < answer.size(); ++i) 
        cout << "확인된 검색어 : " << answer[i].first << ", 위치 : " << answer[i].second << '\n';
}

자세한 설명은 아래 블로그 참조

코드 출저 : (C++) 문자열 검색 알고리즘 : 아호-코라식(Aho-Corasick) 알고리즘

🔶 IV. 기타

💠 투포인터

배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다.

여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수이다. 포인터라는 변수를 두개를 선언해서 투 포인터라고 부른다.

예를들면, 특정 연속된 구간의 합이 M이 되는 경우의 수를 구하는 코드는 아래와 같다.

#include <iostream>
using namespace std;
 
int main(){
    int N, M, arr[10000];
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
        
    int answer = 0, sum = 0, s = 0, e = 0;
    while(s<N){
        if(sum >= M){ 
            sum -= arr[s];
            s++;
        }else{
            sum += arr[e];
            e++;
        } 
        if(sum == M) answer++;
    }
    
    cout << answer;
}

코드 출저 : [알고리즘] 투 포인터 알고리즘(Two-Pointers Algorithm)이란? 백준 2003번 C++ 풀이

💠 Union Find

Disjoint Set을 표현할 때 사용하는 알고리즘

📌Disjoint Set이란

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

즉, 공통 원소가 없는, 즉 상호 배타적 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다. Disjoint Set = 서로소 집합 자료구조

참고자료 : [알고리즘] Union-Find 알고리즘

집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현한다.

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

int parent[10];
int ran[10];

int find(int u) {
    if (u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (ran[u] > ran[v]) swap(u, v);
    parent[u] = v;
    if (ran[u] == ran[v]) ran[v]++;
}

int main() {
    for (int i = 0; i <= 7; i++) {
        parent[i] = i;
        ran[i] = 1;
    }
}

코드 출저 : 유니온 파인드(Union Find) c++

🔶 V. 순열과 조합

💠 순열 (Permutation)

선택 순서가 결과에 영향을 미치는 경우! (1,2)와 (2,1)은 달라야 할 때

📌 특징

중복을 허용하지 않는다.

nPr

5P3 = 5 X 4 X 3

4P1 = 4

4P4 = 4! = 4 X 3 X 2 X 1

#include <iostream>

using namespace std;

void swap(char & a, char & b)
{
    char temp = a;
    a = b;
    b = temp;
}

void permutation(char data [], int depth, int n, int r)
{
    if (depth == r)
    {
        for(int i = 0; i < r; i++)
            cout << data[i] << " ";
        cout << endl;
        
        return;
    }
    
    for(int i = depth; i < n; i++)
    {
        swap(data[depth], data[i]);          // 스왑
        permutation(data, depth + 1, n, r);  // 재귀
        swap(data[depth], data[i]);          // 다시 원래 위치로 되돌리기
    }
}

코드 출저 : (C++) 순열(Permutation) 구현하기

STL 함수 next_permutation(vec.begin(), vec.end()) 또는 prev_permutation(vec.begin(),vec.end())를 사용하는 방법은

이 블로그참고

STL 함수를 사용하려면 다음 2가지 특징이 있다.

next_permutation, prev_permutation으로 모든 순열을 구하려면 반드시 오름 차순 정렬이 되어 있어야 한다.
중복을 제외하고 정렬이 된다.

💠 중복 순열 (Repeated Permutation)

선택 순서가 결과에 영향을 미치는 경우! (1,2)와 (2,1)은 달라야 할 때

📌 특징

중복을 허용한다.

nΠr

5Π3 = 5 X 5 X 5

#include <iostream>
#include <vector>

using namespace std;

void repeatPermutation(vector<char> vec, vector<char> perm, int depth)
{
    if (depth == perm.size())
    {
        for(int i = 0; i < perm.size(); i++)
        {
            cout << perm[i] << " ";
        }
        cout << endl;
        
        return;
    }
    
    for(int i = 0; i < vec.size(); i++)
    {
        perm[depth] = vec[i];
        repeatPermutation(vec, perm, depth + 1);
    }
}

int main()
{
    const int r = 3;
    
    vector<char> v = {'a', 'b'};
    vector<char> perm(r);
    
    repeatPermutation(v, perm, 0);  // {'a', 'b'}의 길이 3의 중복순열 모두 출력하기

    return 0;
}

코드 출저 : (C++) 중복 순열(Repeated Permutation) 구현하기

💠 조합 (Combination)

선택 순서가 결과에 영향을 주지 않는 경우! (1,2)이나 (2,1)이나 결과가 같을 때

📌 특징

중복을 허용하지 않는다.

nCr

5C3 = 5P3 / 3! = 5 X 4 X 3 / 3 X 2 X 1

#include <iostream>
#include <vector>

using namespace std;

void Combination(vector<char> arr, vector<char> comb, int index, int depth)
{
    if (depth == comb.size())
    {
        for(int i = 0; i < comb.size(); i++)
            cout << comb[i] << " ";
        cout << endl;
        
        return;
    }
    else
    {
        for(int i = index; i < arr.size(); i++)
        {
            comb[depth] = arr[i];
            Combination(arr, comb, i + 1, depth + 1);
        }
    }
}

int main()
{
    vector<char> vec = {'a', 'b', 'c', 'd', 'e'};  // n = 5
    
    int r = 3;
    vector<char> comb(r);
    
    Combination(vec, comb, 0, 0);  // {'a', 'b', 'c', 'd', 'e'}의 '5C3' 구하기 

    return 0;
}

코드 출저 : (C++) 조합(Combination) 구현하기

💠 중복 조합 (Repeated Combination)

선택 순서가 결과에 영향을 주지 않는 경우! (1,2)이나 (2,1)이나 결과가 같을 때

📌 특징

중복을 허용한다.

nCr

nHr = n-1+r C n-1 = n-1+r C r

5H3 = 5-1+3 C 3 = 7C3 = 35

#include <iostream>
#include <vector>

using namespace std;

void Combination(vector<char> arr, vector<char> comb, int index, int depth)
{
    if (depth == comb.size()) 
    {
        for(int i = 0; i < comb.size(); i++)
            cout << comb[i] << " ";
        cout << endl;
        
        return;
    }
    else
    {
        for(int i = index; i < arr.size(); i++)
        {
            comb[depth] = arr[i];
            Combination(arr, comb, i, depth + 1);
        }
    }
}

int main()
{
    vector<char> vec = {'a', 'b', 'c', 'd'};   // n = 5
    
    int r = 3;
    vector<char> comb(r);
    
    Combination(vec, comb, 0, 0);  // {'a', 'b', 'c', 'd'}의 중복조합 '4H3' 구하기 

    return 0;
}

코드 출저 : (C++) 중복 조합(Repeated Combination) 구현하기

코딩테스트 이론 공부 2편

코딩테스트 준비를 위한 알고리즘 및 자료구조 개요

2024.03.13

🍭 자주 사용하는 알고리즘 간단 정리

🔶 I. 탐색 및 정렬

💠 Sort

💠 Binary Serach

💠 Lower Bound와 Upper Bound

🔶 II. 그래프

💠 Dijkstra

💠 Bellman-ford

💠 Floyd-warshall

💠 Prim

🔶 III. 문자열

💠 KMP (Knuth-Morris-Pratt)

💠 Aho-Corasick

🔶 IV. 기타

💠 투포인터

💠 Union Find

📌Disjoint Set이란

🔶 V. 순열과 조합

💠 순열 (Permutation)

📌 특징

💠 중복 순열 (Repeated Permutation)

📌 특징

💠 조합 (Combination)

📌 특징

💠 중복 조합 (Repeated Combination)

📌 특징