경우없는 개발 블로그

#include <iostream>
using namespace std;

// CCW 함수: 세 점의 방향성을 판단합니다.
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    // 벡터 AB와 벡터 AC의 외적 계산
    int crossProduct = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

    // 방향성 판단
    if (crossProduct > 0) {
        return 1; // 반시계 방향 (Counter ClockWise)
    } else if (crossProduct < 0) {
        return -1; // 시계 방향 (ClockWise)
    } else {
        return 0; // 일직선 상 (Collinear)
    }
}

// 메인 함수
int main() {
    // 테스트 데이터 입력
    int x1, y1, x2, y2, x3, y3;
    cout << "세 점의 좌표를 입력하세요 (x1 y1 x2 y2 x3 y3): ";
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    // CCW 결과 확인
    int result = ccw(x1, y1, x2, y2, x3, y3);

    // 결과 출력
    if (result == 1) {
        cout << "반시계 방향 (Counter ClockWise)" << endl;
    } else if (result == -1) {
        cout << "시계 방향 (ClockWise)" << endl;
    } else {
        cout << "세 점이 일직선 상에 있습니다 (Collinear)" << endl;
    }

    return 0;
}

기본적으로 세개의 점이면 두개의 벡터를 만들수 있는데

이 두개의 벡터를 단위벡터로 사용하는 행렬식을 만들어서 이 행렬식이 0인지 음수인지 양수인지로

시계 반시계 일직선을 알 수 있다  

https://www.youtube.com/watch?v=15VOaSeHYeY&pp=ygUQI-2cmOyWtOynhOqzoeyEoA%3D%3D

행렬식에 관해서 이 강의를 한번 시청해봐도 좋을것이다.

나는 행렬식으로 ccw를 이해했기때문에 행렬식에대한 gpt 설명을 첨부한다 

• 중복 부분 문제 (Overlapping Subproblems):
  • 동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.
  • DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.
• 최적 부분 구조 (Optimal Substructure):
  • 최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성입니다. 다시 말해, 전체 문제를 해결하는 최적의 해답이 하위 문제들의 최적해로 이루어져 있다는 것입니다.
  • 예를 들어, 최단 경로 문제에서는 특정 노드까지의 최단 경로가 그 이전 경로들의 최단 경로들로 이루어져 있습니다.

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

const int INF = 1e9;

bool bellmanFord(int start, int n, vector<tuple<int, int, int>>& edges, vector<int>& dist) {
    dist[start] = 0;

    // 모든 간선을 최대 (V-1)번 반복
    for (int i = 0; i < n - 1; i++) {
        for (auto& edge : edges) {
            int u, v, weight;
            tie(u, v, weight) = edge;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 음수 사이클 체크
    for (auto& edge : edges) {
        int u, v, weight;
        tie(u, v, weight) = edge;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            return false; // 음수 사이클이 존재
        }
    }

    return true; // 음수 사이클이 없음
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int start;
    cin >> start;

    vector<int> dist(n, INF);
    bool noNegativeCycle = bellmanFord(start, n, edges, dist);

    if (noNegativeCycle) {
        for (int i = 0; i < n; i++) {
            if (dist[i] == INF) {
                cout << "Node " << i << ": Unreachable" << endl;
            } else {
                cout << "Node " << i << ": " << dist[i] << endl;
            }
        }
    } else {
        cout << "Negative cycle detected in the graph." << endl;
    }

    return 0;
}

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

using namespace std;

const int INF = 1e9; // 무한을 나타내기 위해 사용

vector<int> dijkstra(int start, int n, vector<vector<pair<int, int>>>& graph) {
    vector<int> dist(n, INF); // 최단 거리 테이블을 무한으로 초기화
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start}); // 시작 노드로 가기 위한 비용은 0으로 설정

    while (!pq.empty()) {
        int cost = pq.top().first;    // 현재 노드까지의 비용
        int u = pq.top().second;      // 현재 노드
        pq.pop();

        if (cost > dist[u]) continue; // 이미 처리된 노드라면 무시

        for (auto& edge : graph[u]) {
            int v = edge.first;       // 인접 노드
            int weight = edge.second; // 가중치

            if (dist[u] + weight < dist[v]) { // 더 짧은 경로 발견 시 업데이트
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist; // 각 노드로의 최단 거리 반환
}

int main() {
    int n, m; // n: 노드 개수, m: 간선 개수
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    for (int i = 0; i < m; i++) {
        int u, v, w; // u에서 v로 가는 가중치 w인 간선
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w}); // 무방향 그래프일 경우에만 추가
    }

    int start;
    cin >> start; // 시작 노드 입력

    vector<int> shortest_paths = dijkstra(start, n, graph);

    for (int i = 0; i < n; i++) {
        if (shortest_paths[i] == INF)
            cout << "Node " << i << ": Unreachable" << endl;
        else
            cout << "Node " << i << ": " << shortest_paths[i] << endl;
    }

    return 0;
}

#동적 계획법(DP)이란?

DP의 두 가지 핵심 특성

1. 중복되는 부분 문제(Overlapping Subproblems):
   • 동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.
2. 최적 부분 구조(Optimal Substructure):
   • 최적 부분 구조란, 큰 문제의 해답이 그 문제를 구성하는 작은 문제들의 최적 해답으로부터 도출될 수 있다는 특성입니다. 즉, 작은 문제의 최적 해가 변하지 않고 그대로 전체 문제의 최적 해를 이루는 데 기여한다는 것입니다.
   • 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)로 계산할 수 있듯이, 작은 문제들의 최적해를 통해 큰 문제의 답을 구할 수 있습니다.

동적 계획법의 활용 예

• 피보나치 수열: 피보나치 수열을 재귀적으로 구할 때, 각 숫자의 결과를 저장하여 중복된 계산을 방지합니다.
• 배낭 문제: 배낭 문제에서 최대 가치를 구할 때, 각 부분 문제(작은 용량의 배낭에서 최대 가치를 구하는 문제)가 전체 문제의 해답을 구성합니다.

즉 DP 는 동일한 부분문제가 반복되면서 그 부분문제로 전체의 큰 문제를 풀 수 있으며

작은 문제의 최적 해가 바뀌지 않을 때 라고 할 수 있다.

#분할 정복(Divide and Conquer)이란?

**분할 정복(Divide and Conquer)**은 문제를 더 작은 부분 문제로 나눈 후, 각 부분 문제를 독립적으로 해결하고, 이들의 해답을 합쳐서 전체 문제를 해결하는 방식입니다. 분할 정복에서는 중복된 부분 문제가 발생하지 않으며, 각 부분 문제의 결과가 전체 문제의 최적 해답을 직접적으로 보장하지는 않습니다.

분할 정복의 특징

1. 최적 부분 구조가 없다:
   • 분할 정복에서는 각 부분 문제의 해답이 전체 문제의 최적 해답을 바로 보장하지 않습니다. 작은 문제들을 해결한 후, 이를 병합하는 과정에서 전체 문제의 해답이 달라질 수 있습니다.
   • 예를 들어, 병합 정렬(Merge Sort)에서 부분 배열이 정렬되었다고 해서 바로 전체 배열이 정렬되는 것은 아닙니다. 부분 배열들을 병합해야 최종적으로 전체 배열이 정렬됩니다.
2. 중복되는 부분 문제가 없다:
   • 분할 정복에서 각 부분 문제는 독립적입니다. 동일한 부분 문제가 여러 번 반복되지 않으며, 한 번 계산한 부분 문제는 다른 문제에서 다시 계산되지 않습니다.
   • 이는 동적 계획법과의 큰 차이점 중 하나입니다. 예를 들어, 병합 정렬에서 배열을 두 부분으로 나누어 정렬할 때, 같은 부분 문제를 반복해서 계산하지 않으며, 각 부분 문제는 독립적으로 처리됩니다.

분할 정복의 활용 예

• 병합 정렬(Merge Sort): 배열을 반으로 나누어 각각을 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 알고리즘입니다. 작은 문제들이 해결된 후에도 병합 과정에서 전체 해답이 결정됩니다.
• 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누어 각각을 정렬하고, 그 결과를 합쳐서 전체 배열을 정렬하는 알고리즘입니다.

동적 계획법 (DP)                                                                               분할 정복 (Divide and Conquer)

# 쉽게 생각해서..

예를들어서 병합정렬을 생각해보도록하자

병합정렬은 부분으로 나눠서 정렬하는데

결국에는 합쳐서 모두 정렬을 해야 되기 때문에

부분적으로 정렬한것이 그대로 최적해가 보장되지 않는다고 할 수 있다.

(부분 정렬한거 그대로 사용 안하니까)

때문에  부분 문제의 답이 최적해가 아니라고 볼 수 있고

그리고 또한

**병합 정렬(Merge Sort)**에서는 부분 배열을 계속해서 더 작은 부분으로 나눠도, 이미 처리된 부분 문제를 다시 처리하지 않는다. 이게 바로 중복되는 부분 문제가 없다는 의미이다

더 설명해보자면

병합정렬을 위해서 부분을 쪼개서 합치게 된다면

그 합쳐진 부분문제는 "다른문제" 라고 할 수 있다.

왜냐면 그 다른 문제를 풀때는 이전의 부분문제를 요구하지 않기 때문이다.

 때문에 이전문제를 메모리제이션 할 필요가 없으니 중복되는 부분문제라 볼수 없다

LIS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int LIS(const vector<int>& arr) {
    if (arr.empty()) return 0;

    vector<int> lis;
    
    for (int i = 0; i < arr.size(); ++i) {
        auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (it == lis.end()) {
            lis.push_back(arr[i]);
        } else {
            *it = arr[i];
        }
    }

    return lis.size();
}

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << "LIS의 길이: " << LIS(arr) << endl;
    return 0;
}

LCS

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int LCS(const string& X, const string& Y) {
    int m = X.size();
    int k = Y.size();
    vector<vector<int>> lcs(m + 1, vector<int>(k + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }

    return lcs[m][k];
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCAB";
    cout << "LCS의 길이: " << LCS(X, Y) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm> // std::min 사용

using namespace std; // std 네임스페이스를 전역적으로 사용

const int INF = 1e9; // 무한대를 의미하는 큰 값

void floydWarshall(vector<vector<int>>& dist, int V) {
    // 모든 정점 쌍 (i, j)에 대해 i에서 j로의 최단 경로 계산
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][k] < INF && dist[k][j] < INF) { // 두 값이 모두 유효한 경우에만 갱신
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    int V; // 정점의 개수
    cout << "정점의 개수를 입력하세요: ";
    cin >> V;

    // 거리 행렬 초기화
    vector<vector<int>> dist(V, vector<int>(V));

    cout << "거리 행렬을 입력하세요 (직접 연결되지 않은 경우 " << INF << "을 입력하세요):\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cin >> dist[i][j];
        }
    }

    // 플로이드-워셜 알고리즘 수행
    floydWarshall(dist, V);

    // 결과 출력
    cout << "최단 거리 행렬:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

https://www.acmicpc.net/problem/2960

#include <iostream>
#include <string>
#include <istream>
#include <vector>
#include <algorithm>
using namespace std;
bool check[1000001];



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    int count = -1;

    for (int i = 2; i <= n; i++) {

        if (check[i] == false) {

            for (int j = i; j <= n; j += i) {
                if (check[j] == false) {
                    check[j] = true;
                    k--;
                    count = j;

                }
                if (k == 0) {
                    cout << count;
                    break;
                }
            }
        }
        
    }




    return 0;
}

1) substr 함수

substr 함수는 문자열의 특정 부분을 잘라내는 데 사용됩니다.

기본 사용법

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(2, 5); // subs1 = "23456"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(5); // subs2 = "56789"
    cout << "subs2: " << subs2 << endl;

    string subs3 = s.substr(); // subs3 = "0123456789"
    cout << "subs3: " << subs3 << endl;

    return 0;
}

• 시작 위치와 길이를 지정하여 문자열을 자릅니다.
• 시작 위치만 지정하면 해당 위치부터 끝까지 문자열을 자릅니다.
• 아무 것도 지정하지 않으면 문자열 전체를 복사합니다.

find 함수와 함께 사용하기

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(s.find('6')); // subs1 = "6789"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(s.find('6'), 2); // subs2 = "67"
    cout << "subs2: " << subs2 << endl;

    return 0;
}​

• find 함수를 이용해 특정 문자나 문자열을 찾고, 그 위치부터 잘라낼 수 있습니다.

추가 팁:

• substr 함수는 범위가 문자열의 길이를 초과할 경우 자동으로 문자열 끝까지 자릅니다.
• 인덱스가 음수거나 범위를 벗어나면 out_of_range 예외가 발생할 수 있으므로 주의가 필요합니다.

2) sstream을 이용한 쪼개기

sstream을 이용하면 문자열을 특정 구분자로 쉽게 쪼갤 수 있습니다.

기본 사용법

#include <sstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main() {
    string s = "012 34567 89";
    istringstream ss(s);
    string subs1; // 임시 변수
    vector<string> v;

    while (getline(ss, subs1, ' ')) {
        v.push_back(subs1); // v = {"012", "34567", "89"}
    }

    // 결과 출력
    for (const auto& str : v) {
        cout << str << " ";
    }

    return 0;
}​

• getline 함수를 이용하여 구분자로 문자열을 쪼개고, 이를 벡터에 저장합니다.

추가 팁:

• getline 함수는 구분자를 지정하지 않으면 기본적으로 줄바꿈 문자(\n)를 구분자로 사용합니다.
• 문자열을 여러 번 쪼개야 할 경우 istringstream을 반복 사용하여 처리할 수 있습니다.

3) C의 strtok 함수 사용

strtok 함수는 C 스타일 문자열을 특정 구분자로 쪼갤 때 사용됩니다.

기본 사용법

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str[] = "a b c d e f";
    char* p_str = strtok(str, " ");
    
    while (p_str != NULL) {
        cout << p_str << ' ';
        p_str = strtok(NULL, " ");
    }

    return 0;
}

• 첫 번째 인자에 자를 문자열을, 두 번째 인자에 구분자를 넣어 사용합니다.

여러 구분자 사용하기

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str2[] = "a-b,c:d e-f";
    char* p_str2 = strtok(str2, ",- :");

    while (p_str2 != NULL) {
        cout << p_str2 << ' ';
        p_str2 = strtok(NULL, ",- :");
    }

    return 0;
}

• 여러 구분자를 설정하여 문자열을 쪼갤 수 있습니다.

추가 팁:

• strtok 함수는 원본 문자열을 변경합니다. 따라서 원본 문자열을 보존해야 할 경우 복사본을 사용해야 합니다.
• strtok 함수는 스레드 안전하지 않으므로 멀티스레딩 환경에서는 사용을 피하거나 대체 함수(strtok_r)를 사용하는 것이 좋습니다.

마무리

위에서 다룬 substr, sstream, strtok 함수는 각각의 장점과 단점을 가지고 있습니다. 상황에 맞게 적절한 방법을 사용하여 문자열을 효율적으로 다뤄보세요. 이 글이 여러분의 C++ 프로그래밍에 도움이 되길 바랍니다.

코드 예제

substr 함수

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(2, 5); // subs1 = "23456"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(5); // subs2 = "56789"
    cout << "subs2: " << subs2 << endl;

    string subs3 = s.substr(); // subs3 = "0123456789"
    cout << "subs3: " << subs3 << endl;

    return 0;
}

sstream을 이용한 쪼개기

#include <sstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main() {
    string s = "012 34567 89";
    istringstream ss(s);
    string subs1; // 임시 변수
    vector<string> v;

    while (getline(ss, subs1, ' ')) {
        v.push_back(subs1); // v = {"012", "34567", "89"}
    }

    // 결과 출력
    for (const auto& str : v) {
        cout << str << " ";
    }

    return 0;
}

strtok 함수 사용

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str[] = "a b c d e f";
    char* p_str = strtok(str, " ");
    
    while (p_str != NULL) {
        cout << p_str << ' ';
        p_str = strtok(NULL, " ");
    }

    return 0;
}

여러 구분자 사용하기

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str2[] = "a-b,c:d e-f";
    char* p_str2 = strtok(str2, ",- :");

    while (p_str2 != NULL) {
        cout << p_str2 << ' ';
        p_str2 = strtok(NULL, ",- :");
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> makePI(const string& pattern) {
    int m = pattern.size();
    vector<int> PI(m, 0);
    int k = 0;

    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[k] != pattern[i])
            k = PI[k - 1];
        if (pattern[k] == pattern[i])
            k++;
        PI[i] = k;
    }

    return PI;
}

void KMP(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> PI = makePI(pattern);
    int k = 0;

    // 디버깅을 위한 출력
    cout << "텍스트: " << text << endl;
    cout << "패턴: " << pattern << endl;
    cout << "PI 배열: ";
    for (int val : PI) {
        cout << val << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        while (k > 0 && pattern[k] != text[i])
            k = PI[k - 1];
        if (pattern[k] == text[i])
            k++;
        if (k == m) {
            cout << "매칭 위치: " << i - m + 1 << endl;
            k = PI[k - 1];
        }
    }
}

int main() {
    string text, pattern;

    getline(cin, text);
    getline(cin, pattern);

    KMP(text, pattern);

    return 0;
}