경우없는 개발 블로그

#정렬속도 비교

#머지소트

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

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

cin.eof() 를 사용

주요 사항

1. 입력 시도 후에 확인 가능: cin.eof()는 입력 시도가 실패한 후에만 의미가 있습니다. 즉, cin >> variable과 같은 입력 시도가 먼저 이루어져야 합니다. 만약 입력 시도가 실패하고 그 이유가 파일의 끝에 도달했기 때문이라면, 그때 cin.eof()는 참이 됩니다.
2. eof 플래그: cin.eof()가 참이라는 것은 스트림이 파일의 끝에 도달했음을 의미합니다. 하지만 파일 끝에 도달했다고 해서 바로 cin.eof()가 참이 되지는 않습니다. 먼저 입력 시도가 이루어져야 하고, 그 시도가 파일 끝에 도달했음을 감지해야 합니다.

#include <iostream>
#include <vector>

using namespace std;

bool visited[10];


int main() {

    while (1) {
        int a, b;
        cin >> a >> b;

        if (cin.eof()) {
            break;
        }
    }

    
    return 0;
}

문장 입력받기

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

using namespace std;

int main() {


    // 입력 받기 (EOF까지)
    while (getline(cin, tree)) {

    }



    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 <queue>
#include <climits>

using namespace std;




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

    vector<pair<int, int>> graph[11];

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({ v, w });
        graph[v].push_back({ u, w }); 
    }

    vector<int> min_cost(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;


    min_cost[1] = 0;
    pq.push({ 0, 1 }); // 비용 ,노드

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

        if (min_cost[current] < cost) continue;

        for (auto& edge : graph[current]) {
            int next = edge.first;
            int next_cost = cost + edge.second;

            if (next_cost < min_cost[next]) {
                min_cost[next] = next_cost;
                pq.push({ next_cost, next });
            }
        }
    }

    min_cost[n] == INT_MAX ? -1 : min_cost[n];

    cout << min_cost[n];

    return 0;
}

#크루스칼

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

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

using namespace std;

vector<long long> tree;
vector<long long> a;
int N, Q;

// 세그먼트 트리 구축
void build() {
    for (int i = 0; i < N; ++i) {
        tree[N + i] = a[i];
    }
    for (int i = N - 1; i > 0; --i) {
        tree[i] = tree[i << 1] + tree[i << 1 | 1];
    }
}

// 세그먼트 트리의 특정 위치 값 업데이트
void updateTree(int where, long long value) {
    where += N;
    tree[where] = value;

    while (where > 1) {
        where >>= 1;
        tree[where] = tree[where << 1] + tree[where << 1 | 1];
    }
}

// 세그먼트 트리 구간 합 쿼리
long long query(int left, int right) {
    long long sum = 0;
    left += N;
    right += N;

    while (left <= right) {
        if (left & 1) sum += tree[left++];
        if (!(right & 1)) sum += tree[right--];
        left >>= 1;
        right >>= 1;
    }
    return sum;
}

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

    cin >> N >> Q;
    a.resize(N);
    tree.resize(2 * N);

    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    build();

    for (int i = 0; i < Q; ++i) {
        int x, y, a_idx;
        long long b;
        cin >> x >> y >> a_idx >> b;
        if (x > y) swap(x, y);
        cout << query(x - 1, y - 1) << '\n';
        updateTree(a_idx - 1, b);
    }

    return 0;
}