C++ 알고리즘 총 정리

C++ 에서는 iostream 의 cin, cout 을 사용하여 입출력 합니다.

 

TIP 1

C의 표준 입출력 stdio 와 동기화 되어있어서 속도가 느린편. 다음 두 줄을 통해 scanf 보다 빨라질 수 있음

ios_base::sync_with_stdio(false);
cin.tie(NULL);

 

TIP 2

매번 #include<iostream>, #include<vector> 등을 따로 쓰기 귀찮다면 모든 표준 라이브러리 포함하는

#include<bits/stdc++.h> 헤더를 사용

TIP 3

endl 은 단순히 줄바꿈 뿐만아니라 출력 버퍼 비우기(flush) 작업까지 수행하므로 매우 느림

따라서 습관적으로 \n 을 사용하도록 함.

#include <bits/stdc++.h> // 코딩테스트의 치트키!
using namespace std;

int main() {
    // 입출력 가속화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 입력
    cout << n << "\n"; // 출력 (endl 대신 "\n"을 쓰는 게 훨씬 빨라요!)
    
    return 0;
}

 

 

STL

vector

int a[100] 처럼 고정된 크기의 배열과 달리 vector 는 데이터 들어오는 대로 크기가 늘어나는 동적 배열입니다.

- 선언: vector<int> v;

- 접근: v[0]

1. 데이터 넣고 빼기

• v.push_back(val): 맨 뒤에 val을 추가합니다. (가장 많이 씀!)
• v.pop_back(): 맨 뒤의 요소를 제거합니다. (반환값은 없으니 주의!)
• v.insert(it, val): it이 가리키는 위치에 val을 삽입합니다. ($O(N)$이라 느려요!)
• v.erase(it): it이 가리키는 위치의 요소를 제거합니다. ($O(N)$)

2. 크기 및 상태 확인

• v.size(): 현재 들어있는 요소의 개수를 반환합니다.
• v.empty(): 비어있으면 true, 아니면 false를 반환합니다.
• v.clear(): 모든 요소를 제거합니다. (메모리는 그대로 유지될 수 있음)
• v.resize(n): 크기를 n으로 변경합니다. 커지면 0(기본값)으로 채워져요.

if (!v.empty()) {
    cout << v[0];
}

if (v.size() > 0) {
    v[0] = 100;
}

3. 접근 및 위치 (반복자)

• v.front() / v.back(): 첫 번째와 마지막 요소를 참조합니다.
• v.begin(): 첫 번째 요소를 가리키는 **반복자(iterator)**를 반환합니다.
• v.end(): 마지막 요소 다음을 가리키는 반복자를 반환합니다. (중요: 마지막 요소 자체가 아님!

TIP: 초기화와 정렬

// 10개의 칸을 만들고 모두 -1로 채우기 (DP 테이블 만들 때 최고!)
vector<int> v(10, -1); 

// 오름차순 정렬 (algorithm 헤더 필요)
sort(v.begin(), v.end());

 

 

📚 1. Stack (LIFO: Last-In, First-Out)

"나중에 들어간 녀석이 먼저 나온다!" 마치 차곡차곡 쌓인 접시 더미와 같습니다.

• 헤더: #include <stack>
• 선언: stack<int> s;
• 동작:
  • s.push(val) : 값을 위에 쌓음
  • s.pop() : 가장 위에 있는 값을 제거 (반환 안 함!)
  • s.top() : 가장 위에 있는 값을 확인 (가장 최근에 넣은 값)
  • s.size() / s.empty() : 크기 확인 및 비었는지 체크

---

🏃 2. Queue (FIFO: First-In, First-Out)

"먼저 온 사람이 먼저 나간다!" 맛집 줄 서기를 생각하시면 됩니다.

• 헤더: #include <queue>
• 선언: queue<int> q;
• 동작:
  • q.push(val) : 줄의 맨 뒤에 추가
  • q.pop() : 줄의 맨 앞에 있는(가장 오래된) 값을 제거
  • q.front() : 맨 앞의 값 확인 (가장 먼저 나갈 사람)
  • q.back() : 맨 뒤의 값 확인 (방금 들어온 사람)
  • q.size() / q.empty() : 크기 확인 및 비었는지 체크

 

그런데 만약에 vector 로만 구현해야한다는 제약 조건이 있다면?

Stack 은 vector 의 push_back(), pop_back(), back() 으로 구현가능.

Queue 는 vector 의 push_back() 으로 요소를 넣은 다음에 맨 앞의 요소를 빼야하는데

그러면 뒤의 인덱스를 다 한 칸씩 땡겨야해서 O(N)시간복잡도 걸립니다.

그래서 두 개의 포인터로 구현하는 전략이 있습니다.

1. 삽입시 rear 위치(맨 뒤)에 push_back 으로 데이터 넣고 rear 를 한칸 뒤로 이동.
    (단순한 구현에서는 size() 로 맨 뒤의 인덱스를 구할 수 있으니 필요 없을 수도 있음)

2. 삭제시 front 포인터 위치의 값을 반환하고 front 는 한 칸 뒤로 이동.
    (front 에 있던 것이 빠져나갔다고 생각)

 

 

우선순위 큐: 힙(Heap)

이진 힙(바이너리 힙)이라는 완전 이진 트리 구조를 사용.

최대 힙: 부모 노드의 값 >= 자식 노드 (큰 순)

최소 힙: 부모 노드의 값 <= 자식 노드 (작은 순)

 

vector + 매번 정렬 방식으로 구현하면 정렬시 O(N log N) 이 걸립니다.

우선순위 큐 구조는 데이터 삽입 삭제에 O(log N) 이 걸려서 효율적입니다.

#include <queue>
using namespace std;

// 1. 기본 설정 (최대 힙: 큰 숫자가 먼저 나옴)
priority_queue<int> pq;

// 2. 최소 힙 설정 (작은 숫자가 먼저 나옴)
priority_queue<int, vector<int>, greater<int>> min_pq;

pq.push(10);
pq.push(30);
pq.push(20);

// 가장 큰 값 확인 (top)
cout << pq.top(); // 30 출력

// 가장 큰 값 삭제 (pop)
pq.pop();

 

실전 문제 유형 (우선순위 큐는 언제 쓸까?)

우선순위 큐는 보통 이런 상황에서 '치트키'처럼 쓰여요.

1. 다익스트라(Dijkstra) 알고리즘: 최단 경로를 찾을 때 "거리가 가장 짧은 노드"를 먼저 방문해야 하므로 필수입니다.
2. Greedy(탐욕법): 매 순간 최선의 선택(가장 크거나 작은 값)을 해야 할 때 사용해요.
3. 데이터 스트림의 중앙값/최댓값 관리: 실시간으로 숫자가 들어올 때 정렬 상태를 유지하고 싶을 때 유용하죠.

"계속해서 데이터가 들어오는 상황에서 정렬 순서를 유지하며 가장 큰 또는 가장 작은 값을 연속적으로 뽑는 상황"

입니다.

 

🛠 실전 팁: "레벨이 같으면 가입 순서대로?" (사용자 정의 정렬)

단순히 값 하나로만 판단하는게 아니라 예를 들어 레벨이 높은 순, 레벨이 같다면 가입한 지 오래된 순과 같이

여러 값으로 판단해야한다면 struct, operator() 를 사용해 정렬 기준을 만들어야 합니다.

struct User {
    int level;
    int joinOrder; // 가입 순서 (작을수록 먼저 가입)
};

struct Compare {
    bool operator()(User a, User b) {
        if (a.level == b.level) {
            return a.joinOrder > b.joinOrder; // 오름차순 (큰 게 뒤로 = 작은 게 우선순위 높음)
        }
        return a.level < b.level; // 내림차순 (작은 게 뒤로 = 큰 게 우선순위 높음)
    }
};

priority_queue<User, vector<User>, Compare> pq;

 

C++ priority_queue의 정렬 기준은 std::sort와 반대라고 생각하면 편해요!

priority_queue는 true를 반환하면 해당 원소를 "뒤로(우선순위 낮게)" 보냅니다.

그래서 '최소 힙'을 만들 때 greater<int>를 쓰는 이유도 그것 때문이에요.

• std::sort의 true: "이 순서가 좋아! (바꾸지 마)"
• priority_queue의 true: "너(a)는 우선순위가 낮아! (뒤/아래로 가)"

 

std::sort의 핵심 원리: "True면 그대로!"

std::sort의 비교 함수(또는 람다식)에서 true를 반환한다는 것은

"지금 이 순서(A, B)가 내가 원하는 순서가 맞으니 바꾸지 마!"라는 뜻입니다.

• return a < b; (오름차순): "A가 B보다 작으면 true를 줘. 즉, 작은 게 앞에 오는 게 맞아!"
• return a > b; (내림차순): "A가 B보다 크면 true를 줘. 즉, 큰 게 앞에 오는 게 맞아!"

문자 그대로 a < b (커지는 모양) 이면 오름차순 형태라고 기억!

 

vector 정렬

vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end()); // 1, 1, 3, 4, 5

// 내림차순 greator<T> 활용
sort(v.begin(), v.end(), greater<int>()); // 5, 4, 3, 1, 1

// 람다 방식 (최신 스타일!)
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

// 사용자 정의 정렬 성적 높은 순, 번호 낮은 순
struct Student {
    string name;
    int score;
    int id;
};

bool compareStudents(const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score; // 1순위: 성적 높은 순(내림차순)
    }
    return a.id < b.id; // 2순위: 성적이 같으면 번호 낮은 순(오름차순)
}

sort(students.begin(), students.end(), compareStudents);

• std::sort는 함수(또는 함수처럼 행동하는 것)"를 인자로 받습니다.
• std::priority_queue는 "타입(클래스나 구조체 그 자체)"을 인자로 받습니다.

 

---

 

🗺️ 알고리즘 정복 학습 계획

1. 하위 주제 1: 탐욕법(Greedy) & 구현/시뮬레이션
   • 가장 직관적이지만 실수가 많은 기초 체력 구간.
2. 하위 주제 2: 탐색의 기초 (BFS/DFS)
   • 그래프와 트리를 종횡무진 누비는 방법.
3. 하위 주제 3: 깊이 있는 전략 (그래프 & DP)
   • 최단 경로를 찾고, 큰 문제를 쪼개서 푸는 고난도 기술.

 

탐욕법(Greedy) 

지금 당장 가장 좋은 것만 골라!

사용 시점: 매 순간 최선의 선택이 결국 전체의 최선이 된다는 보장이 있을때 사용한다.

문제: "어떤 모험가가 $N$개의 공포도를 가지고 있습니다. 공포도가 $X$인 모험가는 반드시 $X$명 이상으로 구성된 그룹에 참여해야 여행을 떠날 수 있습니다. $N$명의 모험가 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하세요."

공포도 X=1 이면 혼자 떠나도 되고, X=10 이면 10명 이상이어야 함.
 따라서 X를 차례로 정렬해놓고 X=1 인 개수를 따로 구해놓고 X=2 이상 부터는 탐욕적으로 짝을 지어서 그룹 개수를 구해나가면 됨.

이와 같이 탐욕법은 보통 "정렬"과 함께 움직이는 매커니즘을 가지고 있음.

 

구현/시뮬레이션 (Implementation

 

문제에서 시키는 대로, 토씨 하나 안 틀리고 코드로 옮겨!"

2차원 배열에서의 이동(상하좌우), 테트리스 블록 회전, 게임 규칙 구현 등.

vector, struct 활용하여 예외 케이스 고려하여 깔끔하게 짜는게 관건.

 

문제를 읽고

1. 데이터 크기(N)를 확인 -> N이 매우 크다면 정렬, 그리디 가능성 높음

2. N이(20) 과 같이 작으면 브루트포스 가능성 높음

 

DFS (Depth-First Search, 깊이 우선 탐색)

갈 수 있는 데까지 최대한 깊이 가보고, 막히면 되돌아와서 다른 길을 찾자!

재귀 함수나 Stack 으로 구현합니다. Stack 은 터질 위험성이 있기에 재귀 함수로 구현해야 합니다.

언제 쓸까?

• 모든 노드를 방문해야 할 때.
• 경로의 특징을 저장해야 할 때 (예: 경로에 특정 숫자가 포함되면 안 됨).
• 백트래킹(Backtracking): 가능한 모든 조합을 다 시도해 봐야 할 때.

보통 NxN 배열에서 어떤 제약 조건(방문 못함, 방문시 무언가 해야함) 주어지고 모든 노드를 탐색하면서

무언가를 찾거나, 모든 곳을 방문하거나 해야하는 문제가 나옵니다.

또는 모든 조합을 다 만들어야하는 조합, 순열이나 깊이가 매우 깊어지는 경우 DFS 를 선택 

 

BFS (Breadth-First Search, 너비 우선 탐색)

내 주변(인접한 노드)부터 골고루 다 가본 다음에, 그다음으로 넘어가자!"

Queue 자료구조로 구현합니다.

언제 쓸까?

• 최단 거리(Shortest Path) 찾기: 처음으로 목적지에 도달하는 순간이 무조건 최단 거리임을 보장합니다.
• 미로 찾기, 네트워크 거리 측정 등.

 

DFS 와 BFS 모두 탐색을 하기는 하지만, 최단 거리를 구해야하는 상황에서는

DFS? BFS? 고민할 필요 없이 BFS 입니다.

그 이유는 탐색하는 순서 때문이고, 목적지를 발견하는 순간 종료되는 BFS 가 유리합니다.

DFS 는 모든 경로를 다 확인 하고나서야 목적지를 확신할 수 있기 때문입니다.

 

우선순위 큐 BFS (다익스트라)

BFS 에 우선순위 큐를 결합하면, "가까운 순서" 가 아닌 "비용이 가장 작은 순서" 로 탐색이 가능합니다.

이것이 바로 다익스트라 알고리즘의 핵심 원리입니다.

 

일반 BFS 는 모든 길의 거리가 1로 똑같고 인접한 위치로 가는게 최단 거리인데

우선순위 큐 BFS 는 어떤 간선은 비용이 1 인데 어떤 간선은 비용이 10이 드는 그런 가중치가 다른 그래프에서

가장 비용이 적은 간선을 차례로 택해서 가져오기 위해 사용됩니다.

#include <vector>
#include <queue>

using namespace std;

#define INF 1e9 // 무한대 값을 설정 (아직 방문 안 함)

// 1번에서 2번으로 가는 비용 5라면: adj[1].push_back({2, 5});
vector<pair<int, int>> adj[10001]; 
int dist[10001]; // 각 노드까지의 "최단 거리"를 기록하는 메모지

void dijkstra(int start) {
    // 1. 모든 거리를 무한대로 초기화 (아직 아무데도 못 가봤으니까!)
    fill(dist, dist + 10001, INF);

    // 2. 우선순위 큐 생성 (비용이 '작은' 것부터 꺼내기 위해 greater 사용)
    // {비용, 노드번호} 쌍으로 넣을 거예요.
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 3. 시작점 설정
    dist[start] = 0;
    pq.push({0, start}); // {비용, 노드} 순서로 넣어야 비용 기준으로 정렬됨!

    while (!pq.empty()) {
        int d = pq.top().first;    // 현재까지의 누적 비용
        int curr = pq.top().second; // 현재 위치한 노드
        pq.pop();

        // 4. [최적화] 이미 기록된 거리보다 지금 가져온 비용이 더 크면 무시!
        if (dist[curr] < d) continue;

        // 5. 현재 노드와 연결된 이웃 노드들을 하나씩 확인
        for (auto next : adj[curr]) {
            int next_node = next.first;
            int next_cost = d + next.second; // 현재까지 비용 + 다음 노드까지 비용

            // 6. 만약 방금 계산한 비용이 기존에 알고 있던 비용보다 저렴하다면?
            if (next_cost < dist[next_node]) {
                dist[next_node] = next_cost; // 메모지 갱신!
                pq.push({next_cost, next_node}); // 큐에 넣어서 이 길로 계속 가보기
            }
        }
    }
}

 

 

 

 

우선순위 큐를 쓰지 않으면 새 경로마다 이게 지금까지 제일 싼가?
확인해가 위해 이미 방문한 곳들을 여러 번 다시 계산해야 할 수 있습니다.

우선순위 큐는 차례로 가장 비용이 적은 경로를 가져오기 때문에 효율적으로 최단거리 계산이 가능합니다.

 

 

실전 코딩 테스트에서는 코드가 짧은 게 유리할 때가 많아요.

만약 priority_queue<Node, vector<Node>, greater<Node>>를 쓰고 싶다면,

C++의 greater라는 기본 기계는 내부적으로 > 연산자를 사용하도록 설계되어 있습니다.

그래서 greater 기계를 쓰려면 Node 안에 **"나 > 연산 할 줄 알아!"**라고 operator>를 정의해줘야 하는 것이죠.

---

TIP

fill(시작_주소, 끝_주소, 채울_값);

int dist[100];
// dist 배열의 처음부터 끝까지 987,654,321로 채우기
fill(dist, dist + 100, 987654321);

// 1차원 배열을 모두 -1로 채우기
vector<int> v(10);
fill(v.begin(), v.end(), -1);

// 2차원 배열을 모두 0으로 채우기
int board[10][10];
for(int i = 0; i < 10; i++) {
    fill(board[i], board[i] + 10, 0); // 값이 아니라 메모리 상에서 +10칸을 옮긴거라 마지막 위치를 가리킴
}​

 

 

DP의 핵심: 메모이제이션(Memoization)

우리가 아주 잘 아는 피보나치 수열(1, 1, 2, 3, 5, 8, ...)을 예로 들어볼게요.

피보나치의 규칙은 f(n) = f(n-1) + f(n-2) 입니다.

• 그냥 재귀로 풀면?
  • f(5)를 구하기 위해 f(4)와 f(3)을 부릅니다.
  • f(4)는 또 다시 f(3)과 f(2)를 부릅니다.
  • 어라? f(3)을 벌써 두 번이나 계산하고 있네요! 숫자가 커질수록 이런 중복 계산은 기하급수적으로 늘어나서 컴퓨터가 비명을 지르게 됩니다.
• DP로 풀면?
  • f(3)을 처음 계산했을 때 배열(memo[3])에 결과를 딱 적어둡니다.
  • 나중에 f(3)이 또 필요하면? 계산하지 않고 memo[3]에 적힌 값을 바로 꺼내 씁니다.

① 탑다운 (Top-Down, 위에서 아래로)

• 방식: 큰 문제부터 시작해서 작은 문제로 내려가는 방식입니다. 주로 재귀 함수를 사용해요.
• 도구: memo 배열 + 재귀.

② 바텀업 (Bottom-Up, 아래에서 위로)

• 방식: 작은 문제(기초값)부터 차근차근 답을 구해나가는 방식입니다. 주로 **반복문(for)**을 사용해요.
• 도구: dp 테이블 + 반복문. (실전 코딩 테스트에서 가장 선호되는 방식입니다!)

DP 문제를 만났을 때 당황하지 않으려면 이 순서를 따르세요.

1. 상태 정의하기: dp[i]가 무엇을 의미하는지 문장으로 정한다. (예: dp[i]는 i번째 계단까지 가는 최소 비용)
2. 점화식 세우기: dp[i]를 구하기 위해 이전 단계(dp[i-1], dp[i-2])들을 어떻게 조합할지 식을 만든다.
3. 초기값 설정: 가장 작은 문제(dp[0], dp[1])의 답을 미리 적어준다.

문제: 계단을 한 번에 1칸 또는 2칸씩 올라갈 수 있습니다. 총 N개의 계단이 있을 때, 맨 위까지 올라가는 방법의 수는 몇 가지일까요?

점화식을 세워볼까요?

• 1번째 계단에 오는 방법: (0->1) 1가지
• 2번째 계단에 오는 방법: (0->2) 또는 (1->2) 2가지
• i번째 계단에 오는 방법은?
  • 바로 전 칸(i-1)에서 1칸 올라오거나,
  • 전전 칸(i-2)에서 2칸 올라오는 방법뿐입니다!

그렇다면 점화식은 dp[i] = dp[i-1] + dp[i-2] 가 되겠네요! (와, 피보나치랑 똑같죠?)

 

 

탐색 + DP 가 결합된 복합 중상급 난이도 문제가 나올 수 있는데

이는 메모이제이션을 활용한 DFS 라고 불리는 단골 문제입니다. 

• 탐색(DFS)의 한계: 모든 경로를 다 가보다 보니, 이미 계산했던 지점을 또 방문해서 계산하는 중복이 발생해요. (시간 초과 발생!)
• DP의 한계: 단순 반복문(Bottom-Up)으로 풀기에는 계산 순서가 복잡하거나 지도상의 경로가 얽혀 있을 때 점화식을 세우기 어려워요.

문제: 격자 모양의 지도가 있고 각 칸에 높이가 적혀 있습니다. "현재 칸보다 낮은 칸으로만 이동해서 목적지까지 가는 경로의 수"를 구해야 합니다.

 

1. 방문 확인: dp[y][x]를 "-1"로 초기화합니다. (0은 경로가 0개일 수도 있으니, 미방문 표시로 -1을 써요!)
2. DFS 수행: 현재 위치에서 상하좌우를 살피며 나보다 낮은 곳으로 이동합니다.
3. 메모이제이션:
   • 만약 목적지에 도착하면? 1을 반환합니다.
   • 만약 이미 dp[y][x]에 값이 있다면? (즉, -1이 아니라면) 계산하지 않고 그 값을 즉시 반환합니다.
   • 처음 방문하는 곳이라면? 상하좌우에서 돌아온 결과값들을 모두 더해 dp[y][x]에 저장합니다.

💡 이 유형을 알아보는 팁!

1. 지도가 주어짐: 2차원 배열 형태의 지도가 나옵니다.
2. 경로의 개수나 최댓값/최솟값: "도착점까지 가는 방법의 수"나 "가장 많이 얻을 수 있는 점수" 등을 묻습니다.
3. 이동 규칙이 까다로움: 단순히 for문으로 돌리기엔 어느 칸을 먼저 계산해야 할지 순서가 모호할 때 이 방식을 씁니다.

지도상의 한 지점(y, x) 에 도달하는 경로가 여러 개라고 가정했을때

그냥 DFS 로 풀면 (y, x)에 도달할 때마다, 거기서 부터 목적지로 가는 길을 매번 새롭게 다시 갑니다.

A 지점으로 오는 길이 100가지이면, A 에서 목적지 까지 경로를 똑같이 100 반복하게 됩니다. 
근데 "A 지점에서 목적지까지 5가지 길이 있어" 라고 기록해두면 바로 5를 반환해버리면 되겠죠.

 

최단거리를 구할 때는 BFS 를 써야하지만, "경로의 개수" 를 구할 땐 어렵습니다.

BFS는 현재 층의 정보만 알 뿐이고, 이전에 어떤 경로로 왔는지를 알 수 없기 때문입니다.

그래서 DFS 의 재귀 구조를 통해 목적지에서 거꾸로 되돌아 올라오는 과정에서 값을 기록해두면 재활용할 수 있게 되는 것입니다.

'방문 처리'의 차이

일반적인 DFS/BFS는 visited 배열을 써서 "한 번 가본 곳은 다시 안 가!"라고 막아버립니다.

하지만 내리막길 문제처럼 경로의 수를 구할 때는, 다른 길로 와서 똑같은 지점을 방문하는 것을 막으면 안 됩니다.

단지 "거기서부터의 결과값만 빌려오는 것"이죠.

"다시 방문은 하되, 다시 계산은 하지 않는다!" > 이것이 탐색+DP의 핵심 철학입니다.

 

즉, NxN 문제를 봤을때

단순 최단거리 구하기 -> BFS

거리마다 비용이 다른 최단거리 ->다익스트라 (우선순위큐 + BFS)

 

완전 탐색 (모든 경우 확인) -> DFS

도착지 까지 최소/최대 비용, 경로 개수, 복잡한 이동규칙 -> DFS + DP

 

 

문제를 읽고 나서 바로 코드를 타이핑하기 전에, 메모장에 딱 세 줄만 적어보세요.

1. 유형: (예: BFS)
2. 이유: (예: 최단 거리이고 가중치가 일정함)
3. 시간 복잡도: (예: O(N^2)니까 1초 안에 가능!)

 

MST: '최소' + '신장' + '트리'

모든 지점을 최소 비용으로 연결하는 방법을 찾는 것입니다. "모든 정점을 다 잇는 전체 네트워크의 총합 비용"이 중요.

 

• 신장 (Spanning): 그래프의 모든 정점(Vertex)을 포함해야 합니다. (낙오자가 있으면 안 돼요!)
• 트리 (Tree): 모든 정점이 연결되어 있되, 사이클(Cycle)이 없어야 합니다. (빙글빙글 도는 루프가 생기면 이미 트리가 아니죠.)
• 최소 (Minimum): 연결된 간선(Edge)들의 가중치 합이 최소여야 합니다.

"가장 저렴한 통신망 구축"이나 "최소 비용의 도로 건설" 문제에 해당합니다.

• 다익스트라: "특정 시작점에서 특정 도착점까지 가는 한 경로의 최단 거리"가 중요.
• MST: "모든 정점을 다 잇는 전체 네트워크의 총합 비용"이 중요.

 

두 가지 핵심 무기가 있어요.

① 크루스칼 알고리즘 (Kruskal's Algorithm) - 간선 중심

• 철학: "가장 싼 다리부터 일단 건설하자!" (그리디 방식)
• 방법: 1. 모든 간선을 비용 순으로 오름차순 정렬합니다. 2. 가장 싼 간선부터 하나씩 선택합니다. 3. 단, 선택했을 때 사이클이 생기면 버립니다. (이때 사이클 확인을 위해 Union-Find라는 자료구조를 씁니다.)
• 언제 쓸까? 간선의 개수가 적을 때 유리해요.

② 프림 알고리즘 (Prim's Algorithm) - 정점 중심

• 철학: "한 곳에서 시작해서, 옆집 중 가장 가까운 곳부터 확장하자!" (다익스트라와 비슷함)
• 방법:
  1. 시작 정점을 정합니다.
  2. 현재 연결된 정점들과 연결되지 않은 정점들 사이의 간선 중 가장 저렴한 것을 선택합니다. (이때 우선순위 큐를 씁니다!)
  3. 모든 정점이 연결될 때까지 반복합니다.
• 언제 쓸까? 간선이 아주 많을 때 유리해요.

 

1. 문자열 자르기 (Substring & Split)

① substr() 함수 (부분 문자열 추출)

원하는 위치에서 원하는 길이만큼 싹둑 잘라낼 때 씁니다.

• 사용법: s.substr(시작인덱스, 길이)

string s = "C++Programming";
string sub = s.substr(3, 7); // 인덱스 3부터 7글자 -> "Program"

② stringstream으로 자르기 (Split)

공백이나 특정 구분자를 기준으로 단어를 분리할 때 아주 유용해요.

string s = "apple banana orange";
stringstream ss(s);
string word;
while (ss >> word) { // 공백 기준으로 하나씩 추출
    cout << word << endl;
}

---

2. 문자열 붙이기 및 수정 (Append & Replace)

① 붙이기 (+ vs append)

• + 연산자: 직관적이지만 아까 말씀드린 대로 남용하면 복사 비용이 듭니다.
• push_back() / +=: 문자열 뒤에 문자나 문자열을 추가할 때 효율적입니다.

② 수정하기 (replace)

특정 범위를 다른 문자열로 갈아끼울 때 씁니다.

• 사용법: s.replace(시작위치, 길이, 바꿀문자열)

string s = "I love Python";
s.replace(7, 6, "C++"); // "I love C++"

---

3. 문자열 찾기 및 검사 (Find)

① find() 함수

특정 단어가 어디 있는지 찾을 때 씁니다. 못 찾으면 string::npos라는 특수한 값을 반환해요.

 

string s = "Hello World";
if (s.find("World") != string::npos) {
    cout << "찾았다! 위치: " << s.find("World") << endl;
}

---

4. 문자열 변환 (Conversion)

① 숫자 ↔ 문자열

가장 빈번하게 일어나는 변환이죠.

• 숫자 → 문자열: to_string(123)
• 문자열 → 숫자: stoi("123") (int), stoll (long long), stod (double)

② 대소문자 변환 (toupper, tolower)

std::transform과 결합하면 문자열 전체를 한 번에 바꿀 수 있어요.

#include <bits/stdc++.h>

using namespace std;

string solution(string myString) {
    // 어떤 값을 반환하지 않고 원본을 업데이트 합니다!
    transform(myString.begin(), myString.end(), myString.begin(), ::toupper);

    return myString;
}


예시
string s = "Hello";
transform(s.begin(), s.end(), s.begin(), ::toupper); // "HELLO"

---

💡 알고리즘 고수의 메타 인지 전략: string::npos

find 함수를 쓸 때 많은 분이 if (s.find("A") == -1) 처럼 쓰시는데, C++ 표준에서는 string::npos와 비교하는 것이 정석이에요. npos는 시스템에서 가질 수 있는 가장 큰 size_t 값이라서 -1처럼 보일 수 있지만, 의미상 "찾을 수 없음"을 명확히 나타냅니다.

 

&(참조자, Reference)

자료형이 int, string, vector 무엇이든 상관없이 실제 값을 수정하려면 &(참조자, Reference)를 붙여야 합니다.

---

1. &가 없을 때 (복사본 방식)

for (auto c : myString)이라고 쓰면, myString에 있는 각 문자를 복사해서 새로운 변수 c에 담습니다.

• 특징: c의 값을 아무리 바꿔도 원본인 myString은 꿈쩍도 하지 않습니다.
• 비유: 문서 원본은 서랍에 두고, 복사본을 꺼내서 거기에 형광펜을 칠하는 것과 같아요. 원본은 깨끗하겠죠?

2. &가 있을 때 (참조 방식)

for (auto &c : myString)이라고 쓰면, c는 myString 내부의 각 문자를 직접 가리키는 별명이 됩니다.

• 특징: c를 수정하면 곧바로 원본 myString이 수정됩니다.
• 비유: 서랍을 열고 문서 원본에 직접 형광펜을 칠하는 것과 같습니다.

---

💡 수정을 안 하더라도 &를 쓰는 이유 (성능 최적화)

실제 값을 바꾸지 않더라도, 자료형이 큰 경우(string, vector, struct)에는 관습적으로 &를 붙입니다.

단, 이때는 실수로 값을 바꾸지 않도록 const를 함께 붙여주는 게 국룰(표준)이에요!

vector<string> largeData = {"매우 긴 문자열...", "또 다른 긴 문자열..."};

// 복사 방식: 매번 긴 문자열을 복사하느라 컴퓨터가 힘들어함 (느림)
for (auto s : largeData) { ... }

// 참조 방식: 복사하지 않고 주소만 가져와서 쳐다봄 (빠름)
// 값을 바꾸지 않을 거라면 const를 붙여서 안전하게!
for (const auto &s : largeData) { ... }

 

표기법	의미	수정 가능 여부	성능
auto x	복사본 생성	원본 수정 불가	작으면 빠름, 크면 느림
auto &x	원본 참조	원본 수정 가능	언제나 빠름
const auto &x	원본 참조 (읽기 전용)	원본 수정 불가	언제나 빠름 (가장 추천)