경우없는 개발 블로그

#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 설명을 첨부한다 

#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;
}

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;
}

#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;
}

#정렬속도 비교

#머지소트

#include <iostream>
#include <vector>

// 함수 선언
std::vector<int> merge_sort(const std::vector<int>& Data);
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right);

// Merge Sort 함수 정의
std::vector<int> merge_sort(const std::vector<int>& Data) {
    if (Data.size() <= 1) {
        return Data;
    }

    int mid = Data.size() / 2;
    std::vector<int> left(Data.begin(), Data.begin() + mid);
    std::vector<int> right(Data.begin() + mid, Data.end());

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

// Merge 함수 정의
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
    std::vector<int> result;
    int i = 0, j = 0;

    while (i < left.size() && j < right.size()) {
        if (left[i] < right[j]) {
            result.push_back(left[i]);
            i++;
        } else {
            result.push_back(right[j]);
            j++;
        }
    }

    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }

    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }

    return result;
}

// 메인 함수 정의
int main() {
    std::vector<int> Data = {38, 27, 43, 3, 9, 82, 10};
    std::vector<int> sorted_Data = merge_sort(Data);

    for (int num : sorted_Data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

#퀵소트

#include <iostream>
#include <vector>

std::vector<int> Data = {3, 2, 4, 6, 9, 1, 8, 7, 5};

void Quick_sort(int _from, int _to);
int partition(int left, int right);

void Quick_sort(int _from, int _to) {
    if (_from < _to) {
        int pivot = partition(_from, _to);
        Quick_sort(_from, pivot - 1);
        Quick_sort(pivot + 1, _to);
    }
}

int partition(int left, int right) {
    int where = left;
    int pivot = Data[where];
    while (left < right) {
        while (left < Data.size() && Data[left] <= pivot) {
            left++;
        }
        while (Data[right] > pivot) {
            right--;
        }
        if (left < right) {
            std::swap(Data[left], Data[right]);
        }
    }
    std::swap(Data[where], Data[right]);
    return right;
}

int main() {
    Quick_sort(0, Data.size() - 1);
    for (int num : Data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

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

using namespace std;

int main()
{
    
    for (int T = 1; T <= 10; T++) {
        int V, E;
        cin >> V >> E;

        vector<vector<int>> graph(V + 1);
        vector<int> indegree(V + 1, 0);

        for (int i = 1; i <= E; i++) {

            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            indegree[v]++;

        }

        queue<int> q;

        cout << '#' << T << ' ';

        for (int i = 1; i <= V; i++) {
            if (indegree[i] == 0) {
                cout << i << ' ';
                q.push(i);
            }
        }


 
      
        while (!q.empty()) {
            int front = q.front();
            q.pop();

            for (auto nextNode : graph[front]) {

                indegree[nextNode] --;

                if (indegree[nextNode] == 0) {
                    cout << nextNode << ' ';
                    q.push(nextNode);
                }
            }

        }


        cout << '\n';
   }

}

#크루스칼

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

using namespace std;

const int MAX = 1001;
const int INF = 1e9;

int parent[MAX];

int Find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]); // 경로 압축 기법
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) parent[b] = a; // 부모를 갱신하여 연결
}

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

    int N, M;
    cin >> N >> M;

    vector<pair<int, pair<int, int>>> edges; // {weight, {u, v}}
    for (int i = 0; i < M; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        edges.push_back({ weight, {u, v} });
    }

    // 부모 초기화
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    // 간선을 가중치 기준으로 정렬
    sort(edges.begin(), edges.end());

    int mst_weight = 0;
    vector<pair<int, int>> mst_edges;

    for (const auto& edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (Find(u) != Find(v)) {
            Union(u, v);
            mst_weight += weight;
            mst_edges.push_back({ u, v });
        }
    }

    cout << "Minimum Spanning Tree Weight: " << mst_weight << "\n";
    cout << "Edges in the MST:\n";
    for (const auto& edge : mst_edges) {
        cout << edge.first << " - " << edge.second << "\n";
    }

    return 0;
}

#프림

#include <iostream>
#include <cstring> 
#include <climits>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 1001;
const int INF = 1e9;

vector<pair<int, int>> graph[MAX];
bool visited[MAX];

int prim(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int totalCost = 0;
    int connected = 0;

    pq.push({ 0,start });

    while (!pq.empty()) {
        int cost = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (visited[current]) continue;
        visited[current] = true;
        totalCost += cost;
        connected++;

        if (connected == MAX) break;

        for (auto& edge : graph[current]) {
            int next = edge.first;
            int nextCost = edge.second;
            if (!visited[next]) pq.push({ nextCost,next });
        }
    }
    return totalCost;
}

int main() {
    
    int N, M;
    cin >> N >> M;

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

    fill(visited, visited + MAX, false);
    
    cout << prim(1) << endl; 
    
    return 0;
}