[C/C++] C++ Algorithm Note (~ing)

.정렬

---

.선택 정렬

-- selection sort

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void selectionSort(vector<int>& v, int n)
{
    int i, j, idx, tmp;
 
    for (i = 0; i < n - 1; i++) {
        idx = i;
 
        for (j = i + 1; j < n; j++)
            if (v[j] < v[idx]) 
                idx = j;
 
        tmp = v[i];
        v[i] = v[idx];
        v[idx] = tmp;
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i;
 
    scanf("%d", &n);
    vector<int> v(n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    selectionSort(v, n);
 
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
 
    return 0;
}

--

.버블 정렬

-- bubble sort

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void bubbleSort(vector<int>& v, int n)
{
    int i, j, tmp;
 
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (v[j] > v[j + 1]) {
                tmp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = tmp;
            }
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i;
 
    scanf("%d", &n);
    vector<int> v(n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    bubbleSort(v, n);
 
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
 
    return 0;
}

--

.삽입 정렬

-- insertion sort

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void insertionSort(vector<int>& v, int n)
{
    int i, j, key;
 
    for (i = 1; i < n; i++)
    {
        j = i - 1;
        key = v[i];
 
        while (j >= 0 && v[j] > key)
        {
            v[j + 1] = v[j];
            j--;
        }
 
        v[j + 1] = key;
    }
}
 
void insertionSort2(vector<int>& v, int n)
{
    int i, j, key;
 
    for (i = 1; i < n; i++) {
        key = v[i];
 
        for (j = i - 1; j >= 0; j--) {
            if (v[j] > key) v[j + 1] = v[j];
            else break;
        }
 
        v[j + 1] = key;
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i;
 
    scanf("%d", &n);
    vector<int> v(n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    insertionSort2(v, n);
 
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
 
    return 0;
}

--

.병합정렬

- merge sort

- 참고

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int a[101], tmp[101];
 
void divide(int lt, int rt){
    int mid;
    int p1, p2, p3;
 
    if(lt<rt){
        mid=(lt+rt)/2;
        divide(lt, mid);
        divide(mid+1, rt);
 
        p1=lt;
        p2=mid+1;
        p3=lt;
 
        while(p1<=mid && p2<=rt){
            if(a[p1]<a[p2]) tmp[p3++]=a[p1++];
            else tmp[p3++]=a[p2++];
        }
        while(p1<=mid) tmp[p3++]=a[p1++];
        while(p2<=rt) tmp[p3++]=a[p2++];
 
        for(int i=lt; i<=rt; i++)
            a[i]=tmp[i];
    }
}
 
int main() {
    int n, i;
 
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        scanf("%d", &a[i]);
    
    divide(1, n);
 
    for(i=1; i<=n; i++)
        printf("%d ", a[i]);
    
    return 0;
}

.

-- 

--

.

-- 

--

.탐색

---

.투포인트(Two Point) 알고리즘

-- 말 그대로 두 개의 포인트를 이용하여 문제를 해결해나가는 알고리즘이다.

이걸 탐색이라고 하는게 맞나 모르겠지만.. 

어쨌든 두 개의 배열의 요소들을 각 포인터로 탐색하며 문제를 해결해나아가는 알고리즘이므로!

투포인트 문제의 일부를 발췌해보자면

int an, bn, ap = 0, bp = 0, i;
...
while (ap < an && bp < bn)
{
    if (a[ap] == b[bp])
    {
        printf("%d ", a[ap]);   
        ap++, bp++;
    }
    else if (a[ap] < b[bp])
        ap++;
    else
        bp++;
}
 
return 0;

위 코드를 보면 ap, bp 라는 변수 포인터를 이용하여 배열 a, b 를 탐색한다.

이 과정에서 포인터의 위치는 증감연산을 통해 증가되거나 감소될 수 있다.

C언어의 꽃 pointer와는 다른 개념이다.

--

.이분검색(Binary Search)

-- 이분검색은 일렬로 나열되어있는 데이터를 정렬해서 특정 숫자를 찾는 알고리즘이라고 생각하면 되겠다.

즉, 이분검색을 사용하기 위해서는 데이터가 정렬되어있어야 한다는 말쌈!

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, i, key, lt=0, rt, mid, tmp;
 
    scanf("%d %d", &n, &key);
    vector<int> a;
    for(i=0; i<n; i++){
        scanf("%d", &tmp);
        a.push_back(tmp);    
    }
 
    sort(a.begin(), a.end());
    rt=n-1;
 
    while(lt<=rt){
        mid=(lt+rt)/2;
 
        if(a[mid]==key){
            printf("%d\n", mid+1);
 
            return 0;
        }
        else if(a[mid]>key) rt=mid-1;
        else lt=mid+1;
    }
 
    return 0;
}

-- 

.재귀함수(recurrence)

-- 재귀함수는 stack 자료구조를 사용한다.

   종료지점에 도달했을 때 return 처리를 해주고 

   그렇지 않을 경우는 계속 재귀호출해주는 루틴이 제일 무난하다.

   재귀함수분석

void DFS(int x){
    if(x==0) return;
    else{    
        DFS(x-1);
        printf("%d ", x);
    }
}

--

.이진트리 순회(DFS)

-- 참고

-- 더 많은 문제는 블로그 검색창에 DFS 라고 검색!

--

.인접행렬

- 링크

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int map[21][21];
 
int main() {
    int n, m, a, b, c, i, j;
 
    scanf("%d %d", &n, &m);
 
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a ,&b, &c);
        map[a][b]=c;
    }
 
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            printf("%d ", map[i][j]);
        }
        printf("\n");    
    }
 
    return 0;
}

--

.인접리스트

- 링크

#include<stdio.h>
#include<vector>
 
using namespace std;
 
int ch[30], cnt=0, n;        
vector<int> map[30];
 
void DFS(int v){
    int i;
    if(v==n){
        cnt++;
    }
    else{
        for(i=0; i<map[v].size(); i++){
            if(ch[map[v][i]]==0){
                ch[map[v][i]]=1;
                DFS(map[v][i]);
                ch[map[v][i]]=0;
            }
        }
    }
}
    
int main(){
    int m, i, a, b;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
    }
    ch[1]=1;
    DFS(1);
    printf("%d\n", cnt);
    return 0;
}

--

.가중치 인접리스트

-- 문제

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m, rst = 2147000000;
int ch[21];
vector<pair<int, int> > map[21];
 
void DFS(int v, int sum)
{
    int i;
 
    if (v == n)
    {
        if (rst > sum)
            rst = sum;
    }
    else
    {
        for (i = 0; i < map[v].size(); i++)
        {
            if (ch[map[v][i].first] == 0)
            {
                ch[map[v][i].first] = 1;
                DFS(map[v][i].first, sum + map[v][i].second);
                ch[map[v][i].first] = 0;
            }
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int i, a, b, w;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &w);
 
        map[a].push_back({ b, w });
    }
 
    ch[1] = 1;
 
    DFS(1, 0);
 
    printf("%d\n", rst);
 
    return 0;
}

--

.DFS (깊이우선탐색)

-- 문제 1

-- 문제 2

-- 더 많은 문제는 블로그 검색창에 DFS 라고 검색!

-- Recursion or Stack 사용

1. 재귀함수 종료조건 설정

2. 어떤 값을 level로 사용할지 정하기

ㅇ C++

#include<stdio.h>
 
int n, a[11], total=0;
bool flag=false;
 
void DFS(int L, int sum){
    if(sum>(total/2)) return;
    if(flag==true) return;
    if(L==n+1){
        if(sum==(total-sum)){
            flag=true;
        }        
    }
    else{
        DFS(L+1, sum+a[L]);
        DFS(L+1, sum);
    }
}
 
int main(){
    int i;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        total+=a[i];
    }
 
    DFS(1, 0);
 
    if(flag) printf("YES\n");
    else printf("NO\n");
 
    return 0;
}

ㅇ Python

import sys
sys.setrecursionlimit(10000)
 
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
grd, ck = [], []
T = int(input())
 
def dfs(x, y):
    global grd, ck
    if ck[x][y] == 1:
        return
    ck[x][y] = 1
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if grd[xx][yy] == 1 and ck[xx][yy] == 0:
            dfs(xx, yy)
 
def process():
    global grd, ck;
    M, N, K = map(int, input().split())
    grd = [[0 for i in range(M + 2)] for j in range(N + 2)]
    ck = [[0 for i in range(M + 2)] for j in range(N + 2)]
    for _ in range(K):
        X, Y = map(int, input().split())
        grd[Y+1][X+1] = 1
    rst = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            if grd[i][j] == 1 and ck[i][j] == 0:
                dfs(i, j)
                rst += 1
    print(rst)
 
for _ in range(T):
    process()

--

.BFS (너비우선탐색)

-- 문제 1

-- 더 많은 문제는 블로그 검색창에 BFS 라고 검색!

1. Queue 사용

2. 이전 까지의 거리를 활용하여 현재까지의 거리를 연산

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int dst[21];
vector<int> map[21];
queue<int> q;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, m, a, b, i, x;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
 
        map[a].push_back(b);
    }
 
    q.push(1);
 
    while (!q.empty())
    {
        x = q.front();
        q.pop();
 
        for (i = 0; i < map[x].size(); i++)
        {
            if (dst[map[x][i]] == 0)
            {
                q.push(map[x][i]);
                dst[map[x][i]] = dst[x] + 1;
            }
        }
    }
 
    for (i = 2; i <= n; i++)
        printf("%d : %d\n", i, dst[i]);
 
    return 0;
}

* 참고로 python에서 queue를 사용하려면,

   따로 호출해줘야하므로 왠만하면 DFS를 사용한다고 한다.

--

.DFS, BFS 기본

- 문제

.동적계획법

---

 .메모이제이션((memoization)

-- 

int dy[21][21];
 
int C(int n, int r){
    if(dy[n][r]>0) return dy[n][r];
    if(n==r || r==0) return 1;
    else return dy[n][r]=C(n-1, r)+C(n-1, r-1);
}

--

.트리(tree), 그래프(graph)

---

 .Union & Find

-- 문제

int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}
 
void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}

--

 .크루스칼(Kruskal MST, Union & Find)

-- 문제

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int unf[10001];
 
struct Edge{
    int s;
    int e;
    int val;
    Edge(int a, int b, int c){
        s=a;
        e=b;
        val=c;
    }
    bool operator<(const Edge &b)const{
        return val<b.val;
    }
};
 
int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}
 
void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}
 
int main(){
    vector<Edge> Ed;
    int i, n, m, a, b, c, cnt=0, res=0;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        unf[i]=i;
    }
 
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &c);
        Ed.push_back(Edge(a, b, c));    
    }
 
    sort(Ed.begin(), Ed.end());
    for(i=0; i<m; i++){
        int fa=Find(Ed[i].s);
        int fb=Find(Ed[i].e);
        if(fa!=fb){
            res+=Ed[i].val;
            Union(Ed[i].s, Ed[i].e);
        }
    }
    printf("%d\n", res);
 
    return 0;
}

--

 .프림(Prim MST(최소스패닝트리), priority_queue 활용)

-- 문제

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int ch[30];
 
struct Edge{
    int e;
    int val;
    Edge(int a, int b){
        e=a;
        val=b;
    }
    bool operator<(const Edge &b)const{
        return val>b.val;
    }
};
 
int main(){
    priority_queue<Edge> Q;
    vector<pair<int, int> > map[30];
    int i, n, m, a, b, c, res=0;
 
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &c);
        map[a].push_back(make_pair(b, c));    
        map[b].push_back(make_pair(a, c));
    }
 
    Q.push(Edge(1, 0));
    while(!Q.empty()){
        Edge tmp=Q.top();
        Q.pop();
        int v=tmp.e;
        int cost=tmp.val;
        if(ch[v]==0){
            res+=cost;
            ch[v]=1;
            for(i=0; i<map[v].size(); i++){
                if(ch[map[v][i].first]==0){
                    Q.push(Edge(map[v][i].first, map[v][i].second));
                }
            }
        }
        
    }
 
    printf("%d\n", res);
 
    return 0;
}

--

 .다익스트라 알고리즘(priority_queue 적용)

-- 문제

#include<stdio.h>
#include<vector>
#include <queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
 
struct Edge
{
    int vex;
    int dis;
    Edge(int a, int b)
    {
        vex = a;
        dis = b;
    }
    bool operator<(const Edge& b) const
    {
        return dis > b.dis;
    }
};
 
int main() {
    freopen("input.txt", "rt", stdin);
    priority_queue<Edge> Q;
    vector<pair<int, int> > graph[30];
    int i, n, m, a, b, c;
 
    scanf("%d %d", &n, &m);
    vector<int > dist(n + 1, 2147000000);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
 
    Q.push(Edge(1, 0));
    dist[1] = 0;
    
    while (!Q.empty())
    {
        int now = Q.top().vex;
        int cost = Q.top().dis;
        Q.pop();
 
        if (cost > dist[now]) continue;
        for (i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            int nextDis = cost + graph[now][i].second;
            if (dist[next] > nextDis)
            {
                dist[next] = nextDis;
                Q.push(Edge(next, nextDis));
            }
        }
 
    }
 
    for (i = 2; i <= n; i++) {
        if (dist[i] != 2147000000) printf("%d : %d\n", i, dist[i]);
        else printf("%d : impossible\n", i);
    }
    return 0;
}

.수학

---

.기본

--  링크

.요세푸스(Josephus problem)

--  n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다. (wikipedia)

관련 문제 1

.에라토스테네스의 소수 구하기

-- N ~ sqrt(N) 까지 수로 나누어지지 않는지 확인

#include<stdio.h>            
 
int main(){
    int n, i, j, flag, cnt=0;
 
    scanf("%d", &n);
 
    for(i=2; i<=n; i++){
        flag=1;
 
        for(j=2; j*j<=i; j++){
            if(i%j==0){
                flag=0;
 
                break;
            }
        }
 
        if(flag==1) cnt++;
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

.조합(nCr) 구하기

-- 문제

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, r, cnt = 0, ch[20];
 
void DFS(int s, int L)
{
    int i;
 
    if (L == r)
    {
        for (i = 0; i < r; i++)
        {
            printf("%d ", ch[i]);
        }
 
        puts("");
        cnt++;
    }
    else
    {
        for (i = s; i < n; i++)
        {
            ch[L] = i;
            DFS(i + 1, L + 1);
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    scanf("%d %d", &n, &r);
    
    DFS(0, 0);
 
    printf("%d\n", cnt);
 
    return 0;
}