Muji

정렬정렬은 그 자체로는 의미를 가지기 어렵지만 면접에서 가볍게 물어볼 수 있는 문제이기도 하다. 또한, 병합 정렬과 퀵 정렬은 코드 자체로 분할 정복 알고리즘을 명확하게 표현할 수 있어서 의미가 크다.버블 정렬버블 정렬은 맨 처음 인덱스부터 가장 큰 인덱스까지 다음 인덱스와 비교하며 더 클 경우 교환하는 알고리즘이다.교체를 한 후에 다음 칸으로 넘어가면 그 중 첫번째 원소가 이전 비교 중에서 큰 값이다.귀납법적으로 생각하면 마지막까지 수행했을 때 마지막 원소가 모든 원소 중에서 가장 큰 값이다.한 번 수행했을 때 현재 이터레이션에서 가장 큰 값으로 정렬이 되므로 이전보다 1회 더 적게 수행하면 된다.void bubble_sort(vector& arr) { int n = arr.size(); f..

DAG(Directed Acyclic Graph, 유향 비순환 그래프)는 유향 그래프 중에서 사이클이 없는 그래프를 의마한다. 사이클이 존재하지 않으므로 어떠한 정점도 자기 자신으로 돌아오지 않는다. 이러한 특성으로 인해서 각 정점들 사이에 순서 관계가 성립할 수 있고 이러한 순서를 정렬하는 것을 위상 정렬이라고 한다.위상 정렬이 가능하다.사이클이 없다. 순서대로 처리하거나 의존 관계를 명확하게 표현 가능트리 구조적이지만 루트가 하나로 정의되어 있지는 않다.위상 정렬(Topological Sort)정점들을 방향성에 따라 선형적인 순서로 나열하는 방법이다. 정점을 차례대로 방문할 때 이전의 정점에서 다음 정점 순서로 방문을 할 수는 있어도 반대 방향으로는 정렬될 수 없다. 이러한 순서로 배열이 되기 때문에..

차량 기지 알고리즘은 다익스트라가 고안한 알고리즘으로서 중위 표기법 수기을 후위 표기법 수식으로 바꾸는 알고리즘이다. 중위 표기법보다 후위 표기법이 처리하기 쉽기 때문에 종종 사용해야 할 필요가 있다.중위 표기법, 후위 표기법중위 표기법은 일반적인 수식을 표기하는 방법으로 연산자가 숫자 사이에 들어가는 표기법이다. 중위 표기법에서 연산자들은 우선 순위가 존재하고 괄호에 따라서도 우선 순위가 결정된다. 쉽게 말하면 덧셈, 뺼셈과 곱셉, 나누기의 우선 순위를 생각해보면 곱셉, 나눗셈이 우선 순위가 더 높기 때문에 먼저 계산이 되어야 한다.후위 표기법은 연산자가 숫자 뒤에 나타나는 것을 의미한다. 숫자 다음에 나오는 연산자는 바로 앞에 있는 숫자들의 연산자를 의미하고 차례대로 앞으로 대응이 된다. 후위 표기법..

순열과 조합은 집합에서 특정한 원소를 나열하는 방법을 의미한다. 순열의 경우 나열할 때 순서가 다르면 다른 경우가 되는 것이고 조합은 순서를 상관하지 않는다. 순열과 조합은 문제들 중에서 경우의 수를 셀 때 유용하게 사용할 수 있다.순열n개의 원소 중에서 r개를 선택해서 순서대로 배열하는 경우의 수이다. 순서가 다르면 다른 경우의 수이다.경우의 수를 계산할 경우는 익히 알려진대로 첫번째 자리에 n의 경우의 수, 그 다음이 n - 1의 경우의 수, ... 이런 식으로 되어서 n - r + 1까지 경우의 수를 곱하면 된다.조합n개의 원소 중에서 r개를 선택하는 경우의 수이다.조합은 순서가 상관 없다. 이럴 경우 P(n, r)을 나열하면 순서가 상관 없을 경우 중복인 수열이 존재하게 된다. r개의 원소가 나열..

프로젝트를 진행하면서 문자열을 치환할 필요가 있었다. 반복적인 치환이 필요했고 Key값을 이용해서 값을 치환했다. 기본적인 로직을 간소화시켜서 일반적인 치환에도 사용할 수 있다.std::wstring FormatTextWithPlaceholder(const std::wstring& Text, const std::unordered_map& PlaceHolders){ // 치환 결과값 std::wstring Result; size_t Start = 0; // 반복적인 치환 로직에 따라 PlaceHolder를 치환 while (Start

stringstreamstringstream은 데이터를 파싱할 때도 유용한 클래스이다. split을 사용할 때도 유용하게 사용할 수 있다.#include vector answer;string token;stringstream ss(my_string);while(ss >> token){ answer.push_back(token);}stringstream, getlinegetline을 쓸 경우는 empty string이 들어오므로 확인을 해야 한다. getline을 이용하면 delimeter를 직접 설정할 수 있으므로 다른 delimeter를 사용하는 시점에서 유용하다.#include vector answer;string token;stringstream ss(my_string);while(getlin..

소인수 분해소인수는 자연수를 나누는 자연수 중에서 소수인 약수를 의미한다. 기본적인 방식은 약수를 구하는 알고리즘과 같다.방법 1: 처음부터 숫자를 늘려서 찾기vector factors;while(n % 2 == 0) { factors.push_back(2); n /= 2;}// sqrt를 사용하기 보다는 제곱을 이용하자.// 소수는 2를 제외하고는 반드시 홀수이므로 제외한다.for(int i = 3; i * i n : 5// i * i(9) > n(5)// n > 2인데 n : 5가 남았으므로 이를 추가한다.if(n > 2) { factors.push_back(n);}vector factors;int num = 2;while(n != 1) { if(n % num == 0) { ..

두 수의 최대 공약수를 구하는 방법이다. a, b의 수가 있을 때 a, b의 나머지 r도 최대 공약수가 같다. 여기서 r = 0일 경우에는 a, b의 최대 공약수는 b가 된다.이 성질을 반복적으로 적용하면 다음과 같다.따라서 이를 반복적으로 적용해서 몫이 0이 된다면 그 때의 rn이 최대 공약수이다.증명1 : 나머지도 최대 공약수가 같다a, b의 최대 공약수를 G라고 하자. 그럴 경우 A, B는 서로소이다.따라서 r과 b는 공약수 G를 가진다. 만약, 여기서 A - qB와 B가 서로소임을 증명한다면, G는 최대 공약수이다. 이는 귀류법을 통해서 증명할 수 있다. 서로소가 아니라고 가정한다면 다른 최대 공약수 t가 존재한다고 할 수 있다.A, B는 공약수 t를 가지게 되므로 서로소가 아니게 된다. 하지만 ..

MST는 최소 신장 트리란 의미로써 가중치 그래프 중에서 최소의 가중치 합을 가지는 신장 트리를 의미한다. 신장 트리는 모든 노드가 사이클 없이 연결된 그래프를 의미한다. 최소 신장 트리는 결과적으로는 모든 정점이 최소 간선의 합으로 연결된 그래프이다. 실사례로는 네트워크 구성에서 최소 거리로 이루어진 네트워크를 생성하는데 사용한다고 하지만 알고리즘 문제적으로는 단순하게 최소 신장 그래프의 가중치 합을 구하는 정도로만 나온 듯 하다.최소 신장 트리의 경우 대표적으로 2가지 방법이 존재하고 각각 간선을 중심으로 하거나 아니면 정점을 중심으로 처리할 수 있다. 상황에 맞추어서 적절한 알고리즘을 사용해서 해결하면 충분하다.크루스칼 알고리즘크루스칼 알고리즘은 간선 기준으로 정렬한 다음에 사이클을 만들지 않는 간..

Union Find 알고리즘은 서로소 집합 자료 구조를 구현할 때 사용한다. 여러 개의 집합을 관리하고 두 원소가 같은 집합에 속하는 여부를 빠르게 확인하거나 병합할 수 있다.구조집합을 트리 형식으로 한다. 트리에 속한 모든 원소의 루트를 찾게 되면 같은 집합이라면 같은 루트를 가지게 되고 다른 집합이라면 다른 루트를 가지게 된다.Union Find에서는 트리를 구성할 때 시간 복잡도를 간소화할 수 있도록 2가지 방법을 사용한다. 하나는 매 번 루트 노드를 찾는 것이 아니라 루트 노드를 찾으면 루트 노드에 직접 연결해서 경로를 최소화하는 경로 단축이다. 두번째는 랭크 기반 병합이다. 트리가 연결될 때 깊이가 최소한으로 늘어나기 위해서 level이 낮은 트리를 높은 트리에 연결한다.주요 연산Find(찾기)..