기록 블로그

가장 빠르게 도달 하는 방법

그리디 알고리즘 및 다이나믹 알고리즘의 한 유형

가장 짧은 경로를 찾는 알고리즘

예 )

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

종류

• 다익스트라 최단경로 알고리즘
• 플로이드 워셜
• 벨만 포드 알고리즘

다익스트라 최단 경로 알고리즘

각 노드에서 현재까지의 최단거리 정보를 항상 1 차원 리스트에 저장하며 리스트를 계속 갱신

• 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로 구해주는 알고리즘
• 음의 간선이 없을 때 사용 가능
• **가장 비용이 적은 노드**를 선택해 임의의 과정 반복
• 원리
  1. 출발 노드를 정함
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 위 과정에서 3,4 반복

다익스트라 알고리즘 구현방법

1. 구현하기 쉽지만 느림
2. 구현하기 조금 까다롭지만 빠름

1.
시간 복잡도 - O(V^2)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 10001
#define INF 1e9 

using namespace std;

int N, cnt, start;
vector<pair<int, int>> v[MAX];
bool visit[MAX];
int ans[MAX];
int findSmallN() {
    int tmpN = INF; // 가장 작은 수
    int index; // 가장 작은 수 index
    for (int i = 1; i <= N; i++) {
        if (ans[i] < tmpN && !visit[i]) {
            tmpN = ans[i];
            index = i;
        }
    }
    return index;
}
void func(int n) {
    visit[n] = true;
    // 배열 초기화
    for (int i = 0; i < v[n].size(); i++) {
        ans[v[n][i].first] = v[n][i].second;
    }
    // 노드들 중에서 가장 작은수 선택
    int smallN = findSmallN();

    for (int i = 0; i < N - 1; i++) {
        visit[smallN] = true;
        for (int j = 0; j < v[smallN].size(); j++) {
            ans[v[smallN][j].first] = min(ans[v[smallN][j].first], ans[smallN] + v[smallN][j].second);
        }
        smallN = findSmallN();
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    // 배열 가장 큰수로 초기화
    fill_n(ans, MAX, INF);

    cin >> N >> cnt >> start;
    ans[start] = 0;

    for (int i = 0; i < cnt; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
    }

    func(start);
    for (int i = 1; i <= N; i++) {
        cout << ans[i]<<"\n;
    }

}

2.

시간복잡도 - O(ElogV)

(E - 간선 갯수, V - 노드 갯수)

힙 자료구조 이용

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}

cf ) 힙이란?

• 우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제

• 데이터를 우선순위에 따라 처리하고 싶을 때 사용

• 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선시함 (최소힙)

최소 힙을 최대 힙 처럼 사용하기
일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 음수 부호(-) 를 붙여서 원래의 값으로 돌려놓는 방식

• C++ 최소힙/ 최대힙

    priority_queue<int, vector<int>, greater<int>> q; // 최소힙
    priority_queue<int, vector<int>> q;   // 최대힙

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

다익스트라 알고리즘과 비교하면 구현 과정에서 어려움을 겪지 않을 것이지만핵심아이디어가 중요하다

시간 복잡도 - O(N^3)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}

스택

• 박스 쌓기에 비유
• 선입후출 구조 혹은 후입 선출 구조

큐

• 놀이공원 줄서기 비유
• 선입선출 구조

queue 보다는 deque 구조 사용
스택과 큐의 장점을 택한것이고 데이터를 넣고 뺴는 속도가 리스트 자료형에 디배 효율적이며 queue라이브러리를 사용하는 것 보다 간단하다

재귀함수

• 자기자신을 호출하는 함수
• 재귀함수 사용시 스택 자료 구조 이용
• 함수를 계속 호출했을 때 가장 마지막에 호출함 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨

재귀 함수 사용시 재귀함수가 언제 끝나고, 종료할지 꼭 명시

팩토리얼 예제

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
int answer = 0;
int factorial(int n) {
    // n = 1 인경우 재귀함수 멈춤
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int num;
    cin >> num;

    cout<<factorial(num);

}

DFS 스택 자료구조

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드를 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리,
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

cf ) 방문 처리 - 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것

BFS

• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 선입선출 방식인 큐 자료구조 사용
• 인접한 노드를 반복적으로 큐에 놓도록 알고리즘 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게됨

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함
2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

너비 우선 탐색은 DFS보다 수행시간이 좋음

순차 탐색

최악의 시간 복잡도: O(N)

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num;
    vector<string> str;
    string target;
    int ans;
    cin >> num >> target;

    for (int i = 0; i < num; i++) {
        string strTmp;
        cin >> strTmp;
        str.push_back(strTmp);
    }
    for (ans = 0; ans < num; ans++) {
        if (str[ans] == target) {
            break;
        }
    }
    cout << ans+1;
}

이진탐색 : 반으로 쪼개면서 탐색하기

시간복잡도: O(logN)

배열 내부가 정렬되어있어야만 사용가능

#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;

int cnt;
vector<int> num;
int target;

int func(int left, int right) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (num[mid] == target) {
        return mid;
    }
    else if (num[mid] > target) {
        return func(left, mid - 1);
    }
    else {
        return func(mid + 1, right);
    }

}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> cnt >> target;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    int ans = func(0, cnt-1);
    if (ans == -1) {
        cout << "원소가 존재하지 않습니다.";
        return 0;
    }
    cout << ans+1;

}

Parametric Search (파라메트릭 서치)

최적화 문제를 결정하는 문제로 바꿔서 해결하는 기법

⇒ 결정하는 문제 = '예' '아니오'로 대답

ex ) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으려는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다

떡볶이 떡 자르기 문제

• '떡볶이 떡 자르기' 문제를 예로 하면 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복적으로 조정한다
• 현재 이 높이로 자르면 조건을 만족할 수 있는가 → 예 vs 아니오
• 범위로 좁힐 때는 이진 탐색 원리를 이용해 절반찍 좁혀나간다

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt;
    int etc;
    vector<int> rice;
    cin >> cnt >> etc;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        rice.push_back(tmp);
    }
    int left, right;
    sort(rice.begin(), rice.end());
    left = 0;
    right = rice.back();
    int ans, mid;

    while (left < right) {
        ans = 0;
        mid = (left + right) / 2;
        for (int i = 0; i < cnt; i++) {
            int tmp = rice[i] - mid < 0 ? 0 : rice[i] - mid;
            ans += tmp;
        }
        if (ans == etc)  break;
        else if (ans < etc) {
            right = mid - 1;
        }
        else {
            // 적어도 M만큼의 떡을 얻기 위해
            result = mid;
            left = mid + 1;
        }
    }
    cout << result;

}