Forem: dbsans

[BOJ/C++] 단계별로 풀어보기 - 스택, 큐, 덱 1

dbsans — Fri, 06 Mar 2026 08:07:06 +0000

2026.03.06일차 입니다.
개강 전 다른 토이 프로젝트 진행하느라 또 늦었습니다.
해당 토이 프로젝트는 현재 1차 완성 상태이며 2차 완성 이후 블로그에 올릴 생각입니다.
아무튼 스택, 큐, 덱 1 풀어보았습니다.

요약

제미나이를 사용한 요약본입니다.

자료구조 3종 정복: Stack(후입선출), Queue(선입선출), Deque(양방향)의 개념과 C++ STL 활용법을 완벽히 마스터함.
문제 해결 인사이트: 괄호 쌍 검사(Stack), 카드/요세푸스(Queue), 풍선 터뜨리기(Deque) 등 상황에 맞는 최적의 자료구조 선택 능력을 배양함.
구현 디테일 & 최적화: getline()의 종류별 차이 숙지, 불필요한 연산 제거(2164번), 복잡한 구조 단순화(24511번)를 통해 코드 효율성을 높임.

28278번 스택 2

문제 링크
스택을 배워보는 문제입니다. 그 전에 스택에 대하여 배워보겠습니다.

스택(Stack)

이미지 출처
스택이란 마지막에 저장한 데이터를 먼저 꺼내는 후입선출(LIFO, Last-In, First-Out) 방식의 자료구조입니다.
접시를 쌓는 것처럼 한쪽 끝에서만 입출력이 이루어지며 뒤로 가기 등에 사용되는 구조입니다.
Push 연산으로 데이터를 삽입하고 Pop 연산으로 데이터를 삭제할 수 있습니다.
Push, Pop 모두 스택 상단인 Top에서 이루어집니다.

C++에는 <stack>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 stack을 사용할 수 있습니다.

#include <stack>
stack<int> s;

다음과 같은 형태로 선언할 수 있으며 push, pop, top, empty, size 등 다양한 연산이 존재합니다.
각 연산들에 대해서는 문제를 풀며 알아보겠습니다.

해당 문제에서 등장하는 연산은 총 5가지입니다.
1 X: 정수 X를 스택에 넣는다.
push 연산입니다. 스택의 Top에 삽입 연산을 진행합니다.
2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다.
pop 연산입니다. 스택의 Top에 있는 원소를 제거하는 연산입니다.
3: 스택에 들어있는 정수의 개수를 출력한다.
size 연산으로 원소의 개수를 반환합니다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
empty 연산으로 스택 내에 원소가 존재하는지를 판단합니다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다.
top 연산입니다. 스택의 가장 위에 있는 원소를 반환합니다.

#include <iostream>
#include <stack>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    stack<int> s; int n; cin >> n; while (n--) {
        int f; cin >> f; switch (f) {
        case 1: int x; cin >> x; s.push(x); break;
        case 2:
            if (s.empty()) cout << -1 << '\n';
            else { cout << s.top() << '\n'; s.pop(); } break;
        case 3: cout << s.size() << '\n'; break;
        case 4: cout << s.empty() << '\n'; break;
        case 5: cout << (s.empty() ? -1 : s.top()) << '\n'; break;
        }
    }
}

정답 코드는 다음과 같습니다.

10773번 제로

문제 링크
0이 나오면 전에 들어간 수를 삭제합니다. 전에 들어간 수를 삭제하는 전형적인 스택 문제입니다.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
    int k; cin >> k; vector<int> v; 
    while (k--) { int n; cin >> n; if (n) v.push_back(n); else v.pop_back(); }
    cout << accumulate(v.begin(), v.end(), 0);
}

저는 이 문제를 vector의 push_back(), pop_back()을 사용하여 stack처럼 구현해보았습니다.
또한 vector에 저장된 모든 값의 합을 구하기 위해 <numeric> 헤더의 accumulate 함수를 사용하였습니다.
accumulate(시작, 끝, 초기값, [연산]) 형식으로 작성합니다.
연산은 작성하지 않으면 기본적으로 합산이 진행됩니다.

9012번 괄호

문제 링크
모든 괄호가 쌍이라면 통과입니다.

(((

이런 식으로 괄호가 쌓여있을 때

((()

닫히는 괄호가 들어오면 맨 뒤에 있던 괄호와 쌍이 되어 사라집니다.
따라서 한 곳에서만 삽입, 삭제가 이루어지는 것을 볼 수 있고 해당 문제 또한 스택을 이용하여 풀 수 있는 것을 알 수 있습니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    int t; cin >> t; while (t--) {
        string s1; stack<char> s2; cin >> s1;
        for (char c : s1) {
            if (s2.empty()) s2.push(c);
            else {
                if (s2.top() == '(' && c == ')') s2.pop();
                else s2.push(c);
            }
        } cout << (s2.empty() ? "YES" : "NO") << '\n';
    }
}

여는 괄호가 나오면 push, 닫는 괄호가 나왔고 top이 여는 괄호라면 쌍이 되어 pop을 진행합니다.
스택에 원소가 없다면 push를 진행한다는 뜻은 여는 괄호를 삽입하는 것도 있지만,
맨 처음에 닫는 괄호가 나왔을 시 짝 지어지는 괄호를 찾을 수 없으므로 스택에 삽입하여 해당 문자열이 오답으로 판단되게 합니다.

4949번 균형잡힌 세상

문제 링크
9012번 문제와 비슷한 문제이지만 괄호의 종류가 1개에서 2개로 늘었고 괄호가 아닌 문자들이 포함되어 있습니다.
하지만 위의 코드를 응용하여 쉽게 풀 수 있습니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    while (1) {
        string s; getline(cin, s); if (s == ".") break;
        stack<int> t; for (char c : s) { 
            if (c == '(' || c == '[') t.push(c);
            else if (c == ')') {
                if (t.empty() || t.top() != '(') { t.push(c); break; }
                else t.pop();
            }
            else if (c == ']') {
                if (t.empty() || t.top() != '[') { t.push(c); break; }
                else t.pop();
            } 
        } cout << (t.empty() ? "yes" : "no") << '\n';
    }
}

문자열 구분 조건은 공백이 아닌 줄바꿈입니다.
따라서 공백이 아닌 줄바꿈을 단위로 입력 받을 수 있는 getline() 함수가 필요합니다.
getline() 함수는 두 가지가 있습니다. 코드에 대한 설명 이후 아래서 설명하도록 하겠습니다.
열린 괄호라면 스택에 넣습니다.
닫힌 괄호이고 스택의 탑이 해당 괄호와 쌍이라면 pop을 진행합니다.
쌍이 아니거나 스택이 비어있다는 것은 해당 괄호와 쌍인 괄호가 존재하지 않는다는 뜻입니다.
따라서 이후 오답으로 판단하기 위해 push 합니다.

cin.getline()

char* 형의 문자열을 받을 수 있습니다.

#include <iostream>
using namespace std;
int main() { char t[10]; cin.getline(t, 10); }

cin.getline(char*, 범위)은 범위를 지정하여 입력 받습니다.
범위를 지정할 때 마지막 칸은 \n이 들어가므로 사용할 칸 + 1칸의 여유를 두고 사용해야 합니다.
char* 형의 문자열을 입력 받기 때문에 string의 경우에는 에러가 발생합니다.

getline()

<string> 헤더 내에도 getline() 함수가 존재하며 해당 코드에서 사용한 함수가 이 함수입니다.

#include <iostream>
#include <string>
using namespace std;
int main() { string t; getline(cin, t); }

string형을 받을 수 있으며 getline(cin, string) 형태로 사용합니다.
string형을 사용하기 때문에 char* 형을 사용하는 cin.getline()과는 다르게 범위를 지정하지 않아도 됩니다.
또한 \n를 구분자로 받아들인 뒤 버퍼에서 삭제해 string 내에는 \n이 남지 않습니다.

도키도키 간식드리미

문제 링크
스택에 관한 마지막 문제입니다.
스택과 배열, 두 가지 자료구조를 사용하여 풀어야 하는 문제입니다.

처음 줄을 서있는 공간은 일반 배열입니다.
번호를 입력 받아 입력 받은 순서대로 나가는데, 선입선출 방식이라 다시 보니 큐로 구현하는 것이 더 나았을 것 같습니다.
잠깐 대기할 수 있는 공간은 마지막에 들어간 사람이 먼저 나가는 선입후출의 스택입니다.
따라서 조건에 따라 배열에서 바로 나가거나, 배열에서 스택을 거친 뒤 나가는 방식으로 해당 문제를 풀 수 있겠습니다.
아래는 정답 코드입니다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
    int n, i = 0, c = 1; cin >> n;
    vector<int> v(n); for (int j = 0; j < n; ++j) cin >> v[j];
    stack<int> s; while (i < n || !s.empty()) {
        if (!s.empty() && s.top() == c) { s.pop(); c++; }
        else if (i < n) {
            if (v[i] == c) { c++; i++; }
            else s.push(v[i++]);
        } else break;
    } cout << (c - 1 == n ? "Nice" : "Sad");
}

배열은 배열 내의 원소를 직접 삭제하는 게 아닌 인덱스 i를 통해 제어하였습니다.
인덱스 i는 현재 배열의 위치를 저장합니다.
또 c는 받을 학생의 번호를 나타냅니다.
반복 조건은 배열과 스택 모두 비어있다면 모든 학생이 간식을 받았다는 뜻이므로 종료합니다.
배열을 직접 삭제하는 것이 아닌 인덱스로 제어하고 있으므로 배열이 비는 조건은 i < n으로 설정합니다.

반복문 안을 살펴보면 두 조건이 있습니다.
스택의 top이 현재 순서라면 스택을 빠져나오고 현재 순서를 증가시킵니다.
스택이 비어있는데 top에 접근하면 오류가 발생하므로 top을 가져오기 전 스택이 비어있지는 않은지 판단합니다.

!s.empty() && s.top() == c

해당 순서대로 조건을 작성했다면 스택이 비어있을 때 !s.empty()가 0을 반환하면서 && 특성상 뒤의 s.top() == c을 계산하지 않고 바로 0을 반환합니다.

i < n라면, 즉 현재 인덱스가 배열 내의 인덱스라면 배열이 아직 비어있지 않다는 뜻으로 배열을 확인해야 합니다.
배열의 맨 앞 학생이 현재 순서라면 인덱스를 증가시켜 학생이 나간 것처럼 합니다.
그리고 현재 순서를 증가시킵니다.
현재 순서가 아니라면 맨 앞 학생을 스택으로 옮깁니다. 동시에 인덱스도 진행시켜야 합니다

그 어디에도 해당하지 않는다면, 즉 배열이 비었고 스택의 top이 현재 순서가 아닌 상황입니다.
해당 상황에서는 더 진행하더라도 스택에 남은 모든 사람이 간식을 받을 수 없습니다.
따라서 반복문을 종료합니다.

반복문이 정상적으로 종료되었다면 현재 순서가 총 인원 + 1 명에 스택은 비어있을 것입니다.
총 인원 + 1인 이유는 마지막 학생이 나가며 현재 순서가 증가 되기 때문입니다.

c - 1 == n ? "Nice" : "Sad"

따라서 해당 조건으로 판단할 수 있지만

s.empty() ? "Nice" : "Sad"

이 조건으로 작성하여도 정답입니다.
제 개인적인 생각으로는 아래 조건이 좀 더 직관적으로 보입니다.

추가로 큐를 통해서도 구현해보았습니다.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main() {
    queue<int> q; int n, c= 1; cin >> n; for (int i = 0; i < n; ++i) { int t; cin >> t; q.push(t); }
    stack<int> s; while (!q.empty() || !s.empty()) {
        if (!s.empty() && s.top() == c) { s.pop(); c++; }
        else if (!q.empty()) {
            if (q.front() == c) { q.pop(); c++; }
            else { s.push(q.front()); q.pop(); }
        } else break;
    } cout << (c - 1 == n ? "Nice" : "Sad");
}

로직은 배열을 사용한 로직과 전부 동일하므로 따로 설명은 하지 않겠습니다.
큐에 대한 설명은 아래서 하도록 하겠습니다.

18258번 큐 2

문제 링크
큐를 배워보는 문제입니다. 큐에 대해서 짧게 설명을 해보자면

큐(Queue)

이미지 출처
큐란 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First-In, First-Out) 자료구조로 대기열에 주로 사용됩니다.
데이터 추가는 Enqueue라고 하며 Rear라는 맨 뒤에서 진행됩니다.
데이터 삭제는 Dequeue라고 하며 Front라는 맨 앞에서 진행됩니다.

C++에는 <queue>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 queue 사용할 수 있습니다.

#include <queue>
stack<queue> q;

다음과 같은 형태로 선언할 수 있으며 push, pop, front, back, empty, size 등 다양한 연산이 존재합니다.
각 연산들에 대해서는 문제를 풀며 알아보겠습니다.

해당 문제에 등장하는 연산은 총 6가지입니다.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

이 연산들 모두 c++의 queue의 기본 함수 이름과 동일하기 때문에 함수에 관해서는 따로 설명하지 않고 넘어가도록 하겠습니다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    queue<int> q; int n; cin >> n; while (n--) {
        string s; cin >> s; 
        if (s == "push") { int t; cin >> t; q.push(t); }
        else if (s == "pop") { 
            if (q.empty()) cout << "-1\n";
            else { cout << q.front() << '\n'; q.pop(); }
        }
        else if (s == "size") { cout << q.size() << '\n'; }
        else if (s == "empty") { cout << q.empty() << '\n'; }
        else if (s == "front") { 
            if (q.empty()) cout << "-1\n"; 
            else cout << q.front() << '\n'; 
        }
        else if (s == "back") { 
            if (q.empty()) cout << "-1\n";
            else cout << q.back() << '\n'; 
        }
    }
}

정답 코드는 다음과 같습니다.

2164번 카드2

문제 링크
큐를 다루는 문제입니다.
홀수 턴이라면 pop, 짝수턴이라면 가장 위에 있는 카드를 push, 이후 pop을 진행하는 문제입니다.

정답 코드를 소개하기 전 처음 제가 작성한 코드입니다.

while (q.size() != 1) { if (c % 2 == 0) q.push(q.front()); q.pop(); c++; }

턴을 기록하며 짝수 턴에만 push 연산을 진행합니다.
하지만 결론적으로 해당 조건문은 필요하지 않습니다.
예를 들어 보도록 하겠습니다. 만약 카드의 초기 상태가 다음과 같다면

1 2

제일 위에 있는 카드를 버리면(pop) 다음과 같습니다.

최종적으로 남은 카드는 2지만 다음 턴을 진행한다면

2 2

front의 카드를 push

이후 pop을 진행하면 해당 턴을 진행하기 전과 결과가 같습니다.
따라서

while (q.size() != 1) { q.pop(); q.push(q.front()); q.pop(); }

이렇게 작성하여도 같은 결과가 나오게 됩니다.
매 턴마다 홀수인지를 검사하지 않으므로 홀짝을 검사하는 코드보다 4s 빠릅니다.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n; cin >> n; queue<int> q; for (int i = 1; i <= n; ++i) q.push(i);
    while (q.size() != 1) { q.pop(); q.push(q.front()); q.pop(); } cout << q.front();
}

정답 코드는 다음과 같습니다.

11866번 요세푸스 문제 0

문제 링크
k번째로 계속 이동하며 그 위치에 있는 사람을 없앱니다.
k 전까지는 front를 push, pop 하다가 k번째에 출력 후 pop 해주면 됩니다.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n, k; cin >> n >> k; queue<int> q; for (int i = 1; i <= n; ++i) q.push(i);
    cout << '<'; while (!q.empty()) {
        for (int i = 0; i < k - 1; ++i) { q.push(q.front()); q.pop(); }
        cout << q.front(); if (q.size() > 1) cout << ", "; q.pop();
    } cout << '>';
}

문제에서 요구하는 출력 형식 때문에 중간 중간 , 를 출력해야 합니다.

28279번 덱 2

문제 링크
덱을 배우는 문제입니다.

덱(deque)

이미지 출처
덱 또는 데크는 Double-Ended Queue의 약자입니다.
쉽게 말해 스택과 큐를 합쳐 놓은 형태로 양방향 데이터 추가, 삭제가 가능한 유연한 구조를 하고 있습니다.

C++에는 <deque>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 deque을 사용할 수 있습니다.

#include <deque>
deque<int> s;

다음과 같은 형태로 선언할 수 있으며 push_front/back, pop_front/back, front, back, empty, size 등 다양한 연산이 존재합니다.
queue 기본 함수와 비슷하나 양방향 삽입/삭제에 대해 차이점이 존재합니다.
각 연산들에 대해서는 코드를 보면 이해될 것이므로 더 설명하지는 않겠습니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int n; cin >> n; deque<int> dq; while (n--) {
        int c; cin >> c; switch (c) {
        case 1: int x; cin >> x; dq.push_front(x); break;
        case 2: int y; cin >> y; dq.push_back(y); break;
        case 3: if (dq.empty()) cout << "-1\n"; else { cout << dq.front() << '\n'; dq.pop_front(); } break;
        case 4: if (dq.empty()) cout << "-1\n"; else { cout << dq.back() << '\n'; dq.pop_back(); } break;
        case 5: cout << dq.size() << '\n'; break;
        case 6: cout << dq.empty() << '\n'; break;
        case 7: cout << (dq.empty() ? -1 : dq.front()) << '\n'; break;
        case 8: cout << (dq.empty() ? -1 : dq.back()) << '\n'; break;
        }
    }
}

정답 코드입니다.

2346번 풍선 터뜨리기

문제 링크
앞뒤로 데이터를 움직여야 하는 문제로 덱을 사용하는 것이 적절한 문제입니다.

먼저 풍선에 적힌 숫자가 담긴 덱, 풍선의 번호가 담긴 덱 두 개를 준비합니다.

매 턴마다 맨 앞, front의 풍선을 pop 하겠습니다.
숫자는 출력하고 번호만큼 push를 진행합니다.

현재 상태입니다.
따라서 이제 4번 풍선을 pop 해야 합니다.

앞의 두 풍선을 push_back 하면 4번이 앞으로 오므로 4번을 pop 할 수 있게 됩니다.

4번이 front이므로 pop_front, 이후 해당 숫자인 -3만큼 움직이겠습니다.

음수인 경우에는 뒤의 것을 앞으로, push_front를 진행합니다.
세 개가 있으므로 세 개를 push_front 합니다.

해당 작업을 덱이 빌 때까지 반복하면 됩니다.
살펴본 과정에서 숫자가 양수라면 앞의 것 n-1개를 push_back, 음수라면 뒤의 것 n개를 push_front 하고 있다는 것을 알 수 있습니다.
이를 기반으로 구현한 코드는 다음과 같습니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    int n; cin >> n; deque<int> idx; for (int i = 1; i <= n; ++i) idx.push_back(i);
    deque<int> num; for (int i = 0; i < n; ++i) { int t; cin >> t; num.push_back(t); }
    while (1) {
        cout << idx.front() << ' '; idx.pop_front();
        int t = num.front(); num.pop_front();
        if (idx.empty()) break;
        if (t > 0) { 
            for (int i = 0; i < t - 1; ++i) {
                idx.push_back(idx.front()); idx.pop_front();
                num.push_back(num.front()); num.pop_front();
            }
        } else {
            for (int i = 0; i < -t; ++i) {
                idx.push_front(idx.back()); idx.pop_back();
                num.push_front(num.back()); num.pop_back();
            }
        }
    }
}

24511번 queuestack

문제 링크
한 구조 내에 queue의 성질을 띈 데이터, stack의 성질을 띈 데이터가 섞여 있습니다.
하지만 queue 성질을 띈 데이터만 신경 쓰면 되는 어렵지 않은 문제입니다.

queue는 선입선출으로 데이터가 들어가면 값이 교환됩니다.

하지만 stack은 후입선출으로 들어온 데이터가 다시 나갑니다.

따라서 예제의 첫 번째 원소 삽입 상태는 다음과 같은데

스택은 모두 무시하면 큐의 일반적인 삽입/삭제와 동일해집니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int n, m; cin >> n; bool* a = new bool[n]; for (int i = 0; i < n; ++i) cin >> a[i];
    deque<int> dq; for (int i = 0; i < n; ++i) { int b; cin >> b; if (!a[i]) dq.push_back(b); }
    cin >> m; for (int i = 0; i < m; ++i) {
        int c; cin >> c; dq.push_front(c); cout << dq.back() << ' '; dq.pop_back();
    }
}

따라서 큐인 경우에만 덱에 삽입하고 스택은 무시합니다.
이후 들어오는 수들을 push_front, pop_back 하면 됩니다.

[BOJ/C++] 단계별로 풀어보기 - 약수, 배수와 소수 2

dbsans — Tue, 24 Feb 2026 10:56:40 +0000

2026.02.24일차입니다.
왜 늦었냐면 번아웃 오고 방학이라 운동량이 없어서 그런가 건강도 안 좋아져서 늦었습니다.
약수, 배수와 소수 2 풀어보았습니다.

요약

유클리드 호제법, <numeric> - gcd, lcm
에라토스테네스의 체
지역변수의 스택

13241번 최소공배수

문제 링크
최소공배수를 구하는 단순한 문제입니다.
유클리드 호제법 이라는 알고리즘으로 최대공약수를 구한 뒤, 두 수의 곱을 최대공약수로 나누어 최소공배수를 구합니다.

유클리드 호제법

유클리드 호제법이란 최대공약수를 구하는 알고리즘입니다.

두 양의 정수 a, b(a > b)에 대해 a = bq + r (0 ≤ r < b)라고 하면
a, b의 최대공약수는 b, r의 최대공약수와 같다.
즉, gcd(a, b) = gcd(b, r) 이고
r = 0이라면 최대공약수는 b가 된다.

즉 gcd(a, b) = gcd(b, a % b)라는 뜻입니다.

a = bq + r, b의 공약수를 n이라고 가정해봅시다.
a = nx, b = ny로 가정할 수 있고, a = nyq + r이므로 r = n(x - yq)입니다.
따라서 r 또한 n으로 나누어 떨어집니다.
이로서 a, b의 모든 공약수가 b, r의 공약수가 될 수 있음을 알 수 있습니다.

이번에는 b, r = a - bq의 공약수를 m이라고 가정해봅시다.
b = mx, r = my로 가정할 수 있고 r = a - mxq이므로 a = m(xq + y)입니다.
따라서 a 또한 m으로 나누어 떨어집니다.
이로서 b, r의 모든 공약수가 a, b의 공약수가 될 수 있음을 알 수 있습니다.

두 증명을 합하여 봅시다.
a, b의 모든 공약수가 b, r의 공약수가 될 수 있고,
b, r의 모든 공약수가 a, b의 공약수가 될 수 있습니다.
이는 즉 필요충분조건으로 두 공약수의 집합이 완전히 일치함을 알 수 있습니다.
따라서 gcd(a, b) = gcd(b, r)은 일치합니다.

그런데 gcd의 결과는 왜 최대공약수일 수 있는 걸까요?
gcd(a, b)는 최종적으로 gcd(n, 0)이 됩니다.
모든 정수는 0을 나누어 떨어뜨리므로 n과 0의 최대공약수는 n 입니다.
따라서 유클리드 호제법을 통해 최대공약수를 구할 수 있습니다.

유클리드 호제법을 이용한 정답 코드는 아래와 같습니다.

#include <iostream>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main() {
    long long int a, b; cin >> a >> b; cout << a / gcd(a, b) * b;
}

해당 코드를 작성하며 배운 것은 두 가지 입니다.

gcd 함수

우리가 위에서 보았던 유클리드 호제법 gcd 함수의 조건은 a > b였습니다.
그런데 해당 코드에는 a > b인지 검사를 하지 않을 뿐더러 해당 문제의 예시 입력 대부분이 a < b입니다.
하지만 해당 코드는 정답 코드입니다.

gcd(a, b)가 대입되었고, 0 < a < b라고 가정해봅시다.
b != 0 이므로 gcd(b, a % b)가 반환됩니다.
이 때 a = b * 0 + a 이므로 a % b = a 입니다.

따라서 gcd(a, b) = gcd(b, a)가 됩니다.
a > b 검사를 할 필요 없이 a < b가 입력되면 나머지 연산자의 특성에 의해 gcd 함수 내에서 자동으로 두 값이 스왑 되는 것을 볼 수 있습니다.

long long int

최대 입력은 10⁸은 약 21억 = 2 * 10⁹까지 담을 수 있는 int형으로 충분히 담을 수 있는 크기입니다.
하지만 a * b를 진행할 경우 10¹⁶까지 커질 수 있고 이는 int형을 초과하므로 해당 문제는 long long int형을 사용하기를 권장합니다.

a * b / gcd(a, b)가 우리가 알고 있는 최소공배수를 구하는 식입니다.
하지만 해당 코드에서는 a / gcd(a, b) * b로 작성하였습니다.
두 식의 결과는 완전히 같지만 차이점은 중간 단계 a * b와 a / gcd(a, b)에서 있습니다.
만약 a, b가 매우 큰 수이고 int형일 때 이 둘을 먼저 곱하게 되면 int형의 범위를 초과하여 오버플로우가 발생할 수 있습니다.
하지만 나눗셈을 먼저 진행한다면 중간 계산값이 작게 유지되어 오버플로우를 방지할 수 있습니다.

이러한 방식을 사용했음에도 a, b를 int로 선언하면 오답입니다.
그 이유는 a, b가 매우 큰 수이면서 동시에 서로소일 수 있기 때문입니다.
해당 경우에는 위에서 설명한 오버플로우 방지 수법을 사용하여도 a / 1 * b가 되어 int를 초과하기 때문에 long long int를 사용해야 합니다.

그럼 오버플로우 방지를 안 써도 되는 게 아닌가? 하면
실제로 a * b / gcd(a, b) 또한 정답입니다.
a * b / gcd(a, b)의 최대이자 최악의 경우는 10⁸ * 10⁸ / 1은 10¹⁶입니다.
long long int의 범위는 약 2⁶³ 즉, 약 10¹⁸으로 최악의 경우를 수용할 수 있습니다.
그냥 이런 식으로도 오버플로우를 방지할 수 있구나 하여 사용해보았습니다.

+ 추가

다시 복습을 하며 c++17부터 <numeric> 헤더에 gcd 함수, 심지어는 최소공배수를 구하는 함수인 lcm까지 내장되어 있다는 것을 알았습니다.
해당 코드는 다음과 같습니다.

#include <iostream>
#include <numeric>
using namespace std;
int main() {
    long long int a, b; cin >> a >> b; cout << lcm(a, b);
}

이런 게 있었다니

1735번 분수 합

문제 링크
이번에도 유클리드 호제법을 이용한 문제입니다.
두 분수의 합을 기약 분수로 나타내는 간단한 문제로 분자와 분모를 최대공약수로 나누어 주면 되겠습니다.
아래는 정답 코드입니다.

#include <iostream>
using namespace std;
int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
int main() {
    int a, b, c, d, m, s, g; cin >> a >> b >> c >> d;
    m = b * d; s = a * d + b * c; g = gcd(m, s); cout << s / g << ' ' << m / g;
}

이번에는 gcd 함수를 재귀 함수가 아닌 반복문으로 나타내어 보았습니다.
(a, b) = (b, a % b)로 갱신해나가다 b가 0이 되면 반복문을 종료하고 a를 반환합니다.

2485번 가로수

문제 링크
최대공약수 문제입니다.
여러 수의 최대공약수를 구하여 수들 간의 간격을 구하는 문제입니다.
아래는 정답 코드입니다.

#include <iostream>
using namespace std;
int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
int main() {
    int n; cin >> n; int* a = new int[n], * b = new int[n - 1]; for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) b[i] = a[i + 1] - a[i];
    int temp = gcd(b[1], b[0]), r = 0; for (int i = 2; i < n - 1; ++i) temp = gcd(b[i], temp);
    for (int i = 0; i < n - 1; ++i) r += (b[i] / temp - 1); cout << r;
}

배열 a는 가로수의 위치를 저장하고 배열 b는 가로수의 간격을 저장합니다.
배열 b를 통해 간격들의 최대공약수를 계산합니다.
계산된 최대공약수를 통해 각 가로수 사이에 들어갈 수 있는 가로수의 개수를 계산합니다.

다음과 같이 가로수 사이에 들어갈 수 있는 가로수의 개수는 b[i] / temp - 1이라는 것을 알 수 있습니다.

4134번 다음 소수

문제 링크
소수를 판별하는 간단한 문제입니다.
정답 코드입니다.

#include <iostream>
using namespace std;
bool is_prime(long long n) { 
    if (n == 2) return 1; else if (n == 1 || n %2==0) return 0;
    for (long long i = 3; i * i <= n; i+=2) if (n % i == 0) return 0; 
    return 1;
}
int main() {
    int t; cin >> t; while (t--) { long long n; cin >> n; while (is_prime(n)==0) ++n; cout << n<<'\n'; }
}

소수 판단은 브루트포스 방식으로 하나 하나 나누어가며 확인해야 합니다.
여기서 약수의 대칭성을 이용하면 테스트 케이스를 크게 줄일 수 있습니다.
약수의 대칭성에 대해서는 해당 글의 1978번 소수 찾기에서 설명해두었습니다.
또한 2일 경우에는 소수, 1 또는 짝수일 경우에는 소수가 아님을 미리 판단하여 테스트 케이스를 줄였습니다.
짝수일 경우를 제외하지 않고 2부터 판단하면 시간 초과로 오답 처리가 됩니다.

1929번 소수 구하기

문제 링크
두 수 사이에 존재하는 소수를 출력하는 문제입니다.
위 문제에서 사용한 방법 또는 에라토스테네스의 체를 이용하여 풀 수 있습니다.

소수 판정

정답 코드입니다.

#include <iostream>
using namespace std;
bool is_prime(int n) {
    if (n == 2) return 1; else if (n == 1 || n % 2 == 0) return 0;
    for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return 0; return 1;
}
int main() {
    int m, n; cin >> m >> n; for (int i = m; i <= n; ++i) if (is_prime(i)) cout << i << '\n';
}

위 문제에서 설명한 방법이므로 딱히 설명을 더 하진 않겠습니다.

에라토스테네스의 체

에라토스테네스의 체란 소수를 찾는 알고리즘으로 마치 체로 치듯 수를 걸러낸다고 하여 에라토스테네스의 체라고 합니다.
임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 방법으로 한정된 구간이 매우 크지 않으면 매우 빠른 속도를 내는 알고리즘 입니다.
시간복잡도는 O(N log(log N))으로 O(N)에 근접한 효율을 보입니다.

1부터 자연수 n까지의 수의 배열을 만듭니다.
1은 소수가 아니므로 제거합니다.
2를 제외한 2의 배수를 모두 제거합니다.
3을 제외한 3의 배수를 모두 제거합니다.
4와 4의 배수는 2의 배수를 제거하며 모두 제거되었으므로 넘어갑니다.
5를 제외한 5의 배수를 모두 제거합니다.
해당 배열을 순회하며 제거되지 않았다면 해당 수를 제외한 해당 수의 배수를 모두 제거하고, 이미 제거되었다면 넘어갑니다.
끝까지 순회하였다면 최종적으로 배열에는 소수만 남아있게 됩니다.

정답 코드는 아래와 같습니다.

#include <iostream>
using namespace std;
int a[1000001] = { 0, 1 };
int main() {
    int m, n; 
    for (int i = 2; i <= 1000001; ++i) for (int j = 2; i*j <= 1000001; ++j) a[i * j] = 1;
    cin >> m >> n; for (int i = m; i <= n; ++i) if (!a[i]) cout << i << '\n';
}

에라토스테네스의 체를 진행하기 위해 배열을 생성합니다.
1,000,000까지 입력될 수 있으므로 +1 까지의 배열을 생성하고 이렇게 크기가 큰 배열은 전역으로 선언하여야 합니다.
지역 변수는 함수가 호출될 때 임시로 사용하는 스택 영역에 할당되어 크기가 매우 작게 제한되어 있기 때문입니다.

1을 먼저 제외한 뒤 에라토스테네스의 체를 진행합니다.

int a[] = {0, 1}

배열을 이렇게 선언한 이상 기본값은 0입니다.
따라서 소수라면 0, 소수가 아니라면 1을 저장할 것입니다.
2부터 임의의 수를 제외한 그 수의 배수를 모두 1로 저장합니다.

for (int i = 2; i <= 1000001; ++i) {
    if (a[i]) continue;
    for (int j = 2; i * j <= 1000001; ++j) a[i * j] = 1;
}

이렇게 작성할 경우 이미 삭제되었다고 판단된 수는 넘어갑니다.
해당 if문을 추가하면 더 빠르게 계산할 수 있습니다.

소수를 일일이 판단하는 첫 번째 코드의 성능은 메모리 2020 KB, 80 ms 입니다.
에라토스테네스의 체의 성능은 5928 KB, 40 ms로 속도는 위의 if문 추가를 통해 16 ms까지 향상시킬 수 있습니다.
에라토스테네스의 체는 미리 계산하여 배열에 저장해둬야 하기 때문에 더 많은 메모리를 소요합니다.
하지만 그 때 그 때 계산해야 하는 첫 번째 코드에 비해 에라토스테네스의 체는 미리 계산해둔 것을 꺼내오기 때문에 더 적은 시간이 소요됩니다.

17103번 골드바흐 파티션

문제 링크
에라토스테네스의 체로 소수를 모두 구한 뒤 합이 n인 한 쌍의 수가 모두 소수인지 확인하는 문제입니다.
아래는 정답 코드입니다.

#include <iostream>
using namespace std;
int a[1000001] = { 0, 1 };
int main() {
    for (int i = 2; i < 1000001; ++i) for (int j = 2; i * j < 1000001; ++j) a[i * j] = 1;
    int t; cin >> t; while (t--) {
        int n, s = 0; cin >> n; 
        for (int i = 2; i <= n / 2; ++i) if (!a[i] && !a[n - i]) ++s; cout << s << '\n';
    }
}

합은 한 쌍으로 이루어지므로 약수의 대칭성처럼 대칭성을 가집니다.

따라서 n/2까지만 판단하면 됩니다.

소수는 0, 소수가 아니면 1로 저장되어 있으므로 a[i], a[n - i]가 모두 0일 경우에만 출력하여야 합니다.
따라서 조건문은 다음과 같은데

!(a[i] || a[n - i])

이 조건과

!a[i] && !a[n - i]

이 조건 둘 다 드 모르간에 의해 같은 결과입니다.
하지만 후자는 !a[i]가 0인 경우, 소수가 아닌 경우 뒤까지 계산하지 않고 바로 끝내기 때문에 아래의 조건이 조금 더 낫습니다.

13909번 창문 닫기

문제 링크
창문이 닫혀있으면 열고 열려있으면 닫는 문제입니다.
6개의 창문이 있다고 가정해봅시다.

1 ~ 6 창문을 연다. (1, 1, 1, 1, 1, 1)
2의 배수 창문을 닫는다. (1, 0, 1, 0, 1, 0)
3의 배수 창문이 닫혀있으면 열고, 열려있으면 닫는다. (1, 0, 0, 0, 1, 1)
4의 배수 창문이 닫혀있으므로 연다. (1, 0, 0, 1, 1, 1)
5의 배수 창문을 닫는다. (1, 0, 0, 1, 0, 1)
6의 배수 창문이 닫혀있으므로 연다. (1, 0, 0, 1, 0, 0)

따라서 열려있는 창문의 개수는 2개입니다.

1의 배수는 모든 수이므로 첫 번째에서 모든 창문이 열리게 됩니다.
배수로서 한 번 더, 즉 두 번 등장하면 창문이 닫히고, 배수로서 세 번 등장하면 닫힌 창문이 다시 열립니다.
배수로서 네 번 등장하면 열린 창문이 다시 닫히고, 배수로서 다섯 번 등장하면 닫힌 창문이 다시 열립니다.
따라서 창문이 배수로서 홀수 번 등장한다면, 즉 약수가 홀수 개라면 창문이 최종적으로 열려 있게 됩니다.

약수의 개수가 홀수 개가 되기 위해서는 해당 수가 제곱수여야 합니다.

n이 제곱수라면 n의 제곱근이 자연수로 약수에 포함되어 약수가 홀수 개가 됩니다.
제곱수가 아니라면 n의 제곱근이 자연수가 아니게 되어 약수에 포함되지 않아 약수가 짝수 개가 됩니다.

따라서 해당 수 내에 존재하는 제곱수의 개수가 열려 있는 창문의 개수가 되고
이는 그 수의 제곱근의 정수 부분... 가우스 기호라고 볼 수 있겠습니다.

아래는 정답 코드입니다.

#include <iostream>
#include <cmath>
using namespace std;
int main() { int n; cin >> n; cout << (int)sqrt(n); }

[BOJ/C++] 단계별로 풀어보기 - 집합과 맵

dbsans — Thu, 22 Jan 2026 08:21:35 +0000

2026.01.22일차입니다.
많이 늦었습니다. 좀 힘들었어서
아무튼 집합과 맵 풀어보았습니다.

요약

binary search
<map> - at
<algorithm> - 교집합 set_intersection / back_inserter / upper_bound / lower_bound / 대칭 차집합 set_symmetric_difference
<set> - erase / rbegin / rend
<string> - stoi / 문자열 일부 추출 substr
isdigit

10815번 숫자 카드

문제 링크
빠른 탐색을 필요로 하는 문제입니다. 이진 탐색(Binary search) 또는 map을 이용하여 풀 수 있습니다.

Binary search

이진 탐색(Binary search)이란 탐색 범위를 절반 씩 줄여 나가는 효율적인 탐색 알고리즘입니다.
선형 탐색에 비해 빠르지만 배열이 정렬되어 있어야 동작합니다.
시간 복잡도는 O(log n) 입니다.

이미지 출처

주어진 범위 내에서 찾는 값이 중간 값보다 크다면 중간 값 + 1 ~ 끝 범위 내에서 다시 탐색합니다.
찾는 값이 중간 값보다 작다면 처음 ~ 중간 값 - 1 범위 내에서 탐색합니다.
이를 계속 반복하며 탐색 범위를 줄여나갑니다.
중간 값과 찾는 값이 일치한다면 탐색에 성공한 것이고 처음 범위가 끝 범위보다 커졌다면 해당 배열 내에 찾는 값이 없다는 뜻이 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

bool binary_search(int a[], int s, int k) {
    int l = 0, h = s - 1;
    while (l <= h) {
        int m = (l + h) / 2; if (k == a[m]) return 1;
        if (k < a[m]) h = m - 1; else l = m + 1;
    } return 0;
}

int main() {
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N); cin >> M; int* r = new int[M]; for (int i = 0; i < M; ++i) cin >> r[i];
    for (int i = 0; i < M; ++i) cout << binary_search(a, N, r[i]) << ' ';
}

코드로 구현하면 다음과 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i]; 
    cin >> M; int* r = new int[M]; for (int i = 0; i < M; ++i) cin >> r[i];
    sort(a, a + N); for (int i = 0; i < M; ++i) cout << binary_search(a, a + N, r[i]) << ' ';
}

하지만 <algorithm> 태그에서 binary_search 함수로 지원하기 때문에 직접 구현할 필요는 없습니다.

map

map이란 <map> 헤더 내에 포함된 C++ STL 연관 컨테이너 중 하나입니다.
자가 균형 이진 탐색 트리라는 레드-블랙 트리를 자료구조를 사용하며 탐색, 삽입, 삭제 연산 시 균형을 유지하여 최악의 경우에도 O(log n)의 빠른 속도를 보장합니다.
map<key, value> 의 형태로 이루어져 있으며 map[key] = value 형태로 작성이 가능합니다.

코드는 다음과 같이 작성할 수 있습니다.

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<int, int> m; cin >> N; for (int i = 0; i < N; ++i) { int t; cin >> t; m[t] = 1; }
    cin >> M; for (int i = 0; i < M; ++i) { int t; cin >> t; cout << m[t] << ' '; }
}

key와 value 모두 int형으로 선언합니다.
map에서 map[key]을 호출하였을 때 해당 key가 존재하지 않는다면 새로운 요소를 생성합니다.
만약 map[key] = value처럼 대입 연산자를 통하여 값을 대입하면 <key, value> 형태의 새로운 요소를 생성하지만 map[key]만을 작성한다면 value의 디폴트 값에는 0이 들어가 <key, 0>이 저장됩니다.
따라서 map을 사용한 해당 코드는 저장되지 않았어도 0을 출력할 수 있는 것입니다.
또한 해당 코드는 ios::sync_with_stdio(false); cin.tie(NULL);를 생략하면 시간 초과가 발생합니다.

Binary search vs map

두 방식 모두 시간 복잡도는 O(log n)으로 같습니다.
그런데 ios::sync_with_stdio(false); cin.tie(NULL);를 포함했을 때 Binary search 방식은 208ms, map은 444ms가 소요되었습니다.
배열과 벡터가 map보다 더 빠른 속도를 보여줍니다.
따라서 둘의 시간 복잡도가 같음에도 binary search가 더 빠른 속도를 보입니다.

14425번 문자열 집합

문제 링크
map을 사용하여 <요소, 등장 여부> 형태로 저장합니다. 등장한다면 1, 아니라면 0입니다. 해당 여부는 [key] 방식 또는 count 메소드를 통해 알 수 있습니다.

[key]

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, s = 0; map<string, int> mp; cin >> N >> M; while (N--) { string t; cin >> t; mp[t] = 1; }
    while (M--) { string t; cin >> t; s += mp[t]; } cout << s;
}

요소를 저장했다면 map[key]의 결과는 1, 아니라면 디폴트 값인 0이 저장됩니다.
9924 KB, 64 ms가 소요됩니다.

count

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, s = 0; map<string, int> mp; cin >> N >> M; while (N--) { string t; cin >> t; mp[t] = 1; }
    while (M--) { string t; cin >> t; s += mp.count(t); } cout << s;
}

count 메소드는 key 값의 개수를 반환합니다. (하지만 map에서는 key가 중복되지 않으므로 1 또는 0 밖에 반환하지 않습니다.)
[key] 방식과의 차이점이 있다면 [key] 방식은 해당 요소가 없다면 새로운 메모리를 할당하여 생성해야 하지만, count 방식은 0만을 반환하면 됩니다.
따라서 [key] 방식보다 사용 메모리가 낮고 빠른 7944 KB, 56 ms가 소요됩니다.

교집합?

다른 풀이가 있는지 고민하던 중 교집합을 사용하여 풀 수 있지 않을까 하는 생각을 해봤습니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v1(N), v2(M), r;
    for (int i = 0; i < N; ++i) cin >> v1[i]; for (int i = 0; i < M; ++i) cin >> v2[i]; sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end());
    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(r)); cout << r.size();
}

두 배열을 생성하여 N개의 문자열, M개의 검사할 문자열을 저장하였습니다.
교집합을 진행하기 위해 두 배열을 각각 오름차순 정렬 후 <algorithm> 헤더 내에 포함되어 있는 set_intersection 함수를 사용하여 두 배열의 교집합을 계산할 수 있습니다. 해당 함수의 형태는 위의 코드를 참고 바랍니다.
그런데 back_inserter라는 함수가 있습니다. back_inserter는 공간을 계산하지 않고 넣는 횟수만큼 push_back을 호출하는 함수입니다.

vector<int> v = {1, 2, 3}, res;
copy(v.begin(), v.end(), res.begin());

이러한 상황에서 res vector는 크기가 0으로 공간이 할당되지 않아 덮어쓸 메모리가 없어 오류가 발생합니다.
이 때 back_inserter를 사용하면 해당 배열에 자동으로 push_back을 호출하며 안전하게 요소를 대입할 수 있습니다.

하지만 결과적으로 오답이었습니다.

입력
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

문제 설명이며 집합 S에는 중복이 없다고 주어져 있지만 검사할 문자열에 중복이 없다는 말은 없습니다.
따라서 검사할 문자열에 중복이 있을 경우 교집합 결과가 다르게 나올 수 있어 교집합을 사용한 코드는 오답입니다.

7785번 회사에 있는 사람

문제 링크
set을 이용한 문제입니다.
set은 <set> 헤더 내에 포함된 C++ STL 연관 컨테이너로 map과 같이 레드-블랙 트리로 이루어져 있습니다.
set은 중복을 허용하지 않으며, 삽입 순서에 상관없이 자동 정렬이 됩니다.
set<자료형> 변수 형태로 선언 가능합니다.

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
    int n; set<string> s; cin >> n;
    while (n --> 0) { 
        string t, b; cin >> t >> b;
        if (b == "enter") s.insert(t); else s.erase(t);
    } for (auto i = s.rbegin(); i != s.rend(); ++i) cout << *i << '\n';
}

"enter"가 입력되면 삽입, "leave"가 입력되면 삭제합니다.
set.erase(value)는 값을 토대로 삭제하기 때문에 set을 사용합니다.
또한 사전 순의 역순으로 출력해야 하기 때문에 자동 정렬되는 set을 역순으로 출력해야 합니다.

이미지 출처
rbegin과 rend를 사용하여 역순을 만들 수 있습니다.

--> 문법에 대한 내용은 다음 영상을 참고 바랍니다.

1620번 나는야 포켓몬 마스터 이다솜

문제 링크
숫자를 입력 받으면 번호에 대응하는 이름, 문자를 입력 받으면 이름에 대응하는 번호를 반환해야 합니다.
따라서 <이름, 번호>, <번호, 이름> 두 가지의 map을 만들어야 합니다.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<int, string> mp1; map<string, int> mp2; cin >> N >> M; for (int i = 1; i <= N; ++i) { cin >> mp1[i]; mp2[mp1[i]] = i; }
    while (M--) {
        string t; cin >> t; 
        try { cout << mp2.at(t) << '\n'; } catch (out_of_range) { cout << mp1.at(stoi(t)) << '\n'; }
    }
}

at 메소드에 Key를 넘기면 Value를 받을 수 있습니다. 그런데 해당 key가 존재하지 않으면 예외를 발생합니다. 해당 방법을 이용하여 문제를 풀어봅니다.
먼저 <이름, 번호> map에 at을 이용하여 접근하고 해당 부분을 try로 묶어줍니다.
해당 부분에서 예외가 발생하였다면 값이 존재하지 않는다는 뜻이고 이는 곧 숫자를 입력 받았으므로 <번호, 이름> map에서 접근해야 한다는 뜻입니다.
stoi 함수를 이용하여 입력 받은 string형을 int형으로 변환하고 <번호, 이름> map에서 접근하도록 합니다.
25528 KB, 360 ms가 소요되었습니다.

<번호, 이름> map의 경우에는 배열로 선언 가능하며 앞에서 설명했듯 배열이 map보다 빠른 속도를 보여줍니다.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M; string* a = new string[N + 1]; map<string, int> m;
    for (int i = 1; i <= N; ++i) { cin >> a[i]; m[a[i]] = i; }
    while (M--) {
        string t; cin >> t;
        if (isdigit(t[0])) cout << a[stoi(t)] << '\n'; else cout << m[t] << '\n';
    }
}

<배열, 이름> map을 배열로 선언한 코드이며 해당 코드는 입력값이 숫자인지 판단하는 방법으로 isdigit 함수를 사용하였습니다.
isdigit 함수는 char값이 숫자인지 문자인지를 판단하는 함수입니다.
첫 번째 요소가 숫자라면 해당 문자열은 숫자입니다.
20864 KB, 144 ms가 소요되며 두 개의 map을 사용한 코드보다 효율적입니다.

10816번 숫자 카드 2

문제 링크
숫자를 입력 받고 해당 숫자가 몇 번 등장하는지 세는 문제입니다.
map으로도 구현이 가능하며 배열로도 구현이 가능합니다.

map

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N; map<int, int> m; cin >> N; while (N--) { int t; cin >> t; m[t] += 1; }
    cin >> N; while (N--) { int t; cin >> t; cout << m[t] << ' '; }
}

입력 받은 요소를 Key로 하여 입력 받을 때마다 값을 1씩 증가시킵니다.
이후 입력 받은 Key에 대응하는 Value를 출력하는 평범한 map 문제입니다.

배열

map을 사용하지 않고 어떻게 풀 수 있을지 고민을 많이 했습니다.
입력 받은 요소를 배열에 저장한 뒤 오름차순 정렬합니다.
이후 배열 내에서 그 요소가 등장한 마지막 위치 - 첫 위치가 그 요소의 등장 개수입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    cin >> M; sort(a, a + N); while (M--) { int t; cin >> t; cout << upper_bound(a, a + N, t) - lower_bound(a, a + N, t) << ' '; }
}

upper_bound는 해당 요소를 초과하는 숫자가 배열 어디에서 처음 등장하는 지를 반환합니다. 이는 정렬된 배열에서 해당 요소가 마지막으로 등장하는 위치 + 1과 같습니다.
lower_bound는 찾으려는 요소가 처음 등장하는 위치를 반환합니다.
따라서 upper_bound - lower_bound는 해당 요소의 개수가 됩니다.

1764번 듣보잡

문제 링크
교집합 문제이며 교집합, map, binary search 세 가지 방법을 사용하여 풀 수 있습니다.

교집합

14425번 문자열 집합에서 오답으로 사용했던 set_intersection을 사용하여 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v1(N), v2(M); 
    for (int i = 0; i < N; ++i) cin >> v1[i]; for (int i = 0; i < M; ++i) cin >> v2[i]; 
    sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end());
    vector<string> r; auto t = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(r));
    cout << r.size() << '\n'; for (string n : r) cout << n << '\n';
}

map

<이름, 등장 횟수> map을 생성하여 등장 횟수가 1보다 크면(즉, 2번) 두 집합에 모두 등장했다는 뜻이므로 교집합에 들어갑니다.
따라서 이러한 요소들을 결과 vector에 대입합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<string, int> m; vector<string> v; cin >> N >> M;
    for (int i = 0; i < N + M; ++i) {
        string t; cin >> t; m[t]++;
        if (m[t] > 1) v.push_back(t);
    } sort(v.begin(), v.end()); cout << v.size() << '\n'; for (string t : v) cout << t << '\n';
}

binary search

첫 번째 집합을 모두 배열에 저장합니다.
이후 두 번째 배열의 요소는 입력받으면 해당 요소가 첫 번째 배열에 존재하는지 binary search를 통해 확인합니다.
존재한다면 교집합에 포함되므로 결과 배열 내에 저장합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v(N), r; for (int i = 0; i < N; ++i) cin >> v[i];
    sort(v.begin(), v.end()); while (M--) { string t; cin >> t; if (binary_search(v.begin(), v.end(), t)) r.push_back(t); }
    sort(r.begin(), r.end()); cout << r.size() << '\n'; for (string t : r) cout << t << '\n';
}

교집합 vs map vs binary search

세 코드의 성능 차이는 다음과 같습니다.

구분	교집합	map	binary search
메모리	9912 KB	12992 KB	5972 KB
시간	32 ms	72 ms	24 ms

map 특성상 map을 사용한 코드가 배열의 사용한 코드보다 느린 속도로 나타납니다.
또한 교집합 코드는 사용한 배열이 총 세 개, binary search 코드는 사용한 배열이 총 2개였기 때문에 binary search 코드가 더 적은 메모리를 사용했습니다.
해당 지표에서는 binary search 코드가 가장 효율적인 것으로 나타났습니다.

1269번 대칭 차집합

문제 링크
A-B와 B-A의 합집합을 대칭 차집합이라고 합니다. 합집합에서 교집합을 제외한 것과 같습니다.
대칭 차집합 함수를 사용하거나 map을 사용하여 풀 수 있습니다.

대칭 차집합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int a, b; cin >> a >> b; vector<int> A(a), B(b), v; 
    for (int i = 0; i < a; ++i) cin >> A[i]; for (int i = 0; i < b; ++i) cin >> B[i]; sort(A.begin(), A.end()); sort(B.begin(), B.end()); 
    set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(v)); cout << v.size();
}

set_symmetric_difference 함수를 사용할 수 있으며 set_intersection과 사용법이 같습니다.
6792 KB, 64 ms를 소요합니다.

map

대칭 차집합은 결국 모두 입력 받아 중복된 값들은 제거하면 됩니다.
따라서 값을 입력 받아 map에 대입하는데, 이미 존재한다면 삭제합니다.

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; map<int, bool> mp; cin >> N >> M;
    for (int i = 0; i < N + M; ++i) { int t; cin >> t; if (mp[t]) mp.erase(t); else mp[t] = 1; } cout << mp.size();
}

20768 KB, 244 ms를 소요합니다.
map을 사용하여 배열을 사용한 대칭 차집합 함수 코드보다 더 오래 걸립니다.

11478번 서로 다른 부분 문자열의 개수

문제 링크
중복되지 않은 요소의 개수를 도출해야 하므로 set을 사용합니다.

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    string s; cin >> s; int l = s.length(); set<string> r;
    for (int i = 0; i < l; ++i) for (int j = 1; j < l - i + 1; ++j) r.insert(s.substr(i, j)); cout << r.size();
}

substr(start, length) 함수를 이용하여 문자열의 일부를 추출할 수 있습니다.
시작 위치부터 해당 길이만큼의 문자열을 반환합니다.
따라서 중첩반복문으로 구현하며 안쪽 반복문의 반복 조건은 j <= l - i로 설정합니다.

[BOJ/C++] 단계별로 풀어보기 - 정렬(2)

dbsans — Mon, 12 Jan 2026 12:22:00 +0000

2026.01.12일차입니다. 정렬 풀어보았습니다.

요약

내림차순/오름차순 정렬: <functional> - greater<>()/less<>()
<vector> - pair
<algorithm> - sort - cmp / stable_sort / unique / erase / lower_bound

2587번 대표값2

문제 링크
평균과 중앙값을 구하는 문제입니다. 5개의 값을 정렬 후 중앙값인 a[2]를 출력하면 되는 간단한 문제입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[5], t = 0; for (int i = 0; i < 5; ++i) { cin >> a[i]; t += a[i]; }
    sort(a, a + 5); cout << t / 5 << '\n' << a[2];
}

전 글에서 말했다시피 여러 문제에서 정렬 알고리즘을 구현하긴 귀찮기도 하고 실제 코테에서도 내장 함수를 사용하므로 저도 내장 함수를 사용했습니다.

커트라인

문제 링크
커트라인의 점수는 내림차순에서 k번째인 학생의 점수입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, k; cin >> N >> k; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N); cout << a[N - k];
}

다음과 같이 오름차순 정렬 후 뒤에서 k번째 원소라고 하여도 정답입니다.

10989번 수 정렬하기 3

문제 링크
카운팅 정렬을 이용하는 문제입니다.
카운팅 정렬(Counting sort)이란 배열 내에 각각의 원소가 몇 개가 있는지 세어 원소들을 순서대로 그 개수만큼 채워 배열을 완성하는 알고리즘입니다.

카운팅 정렬을 이해하는 데에는 해당 글을 읽어보는 것을 추천드립니다.
저 또한 1~2년 전 즈음에 해당 글을 보고 공부했던 기억이 있습니다.

하지만 카운팅 정렬을 그대로 구현하게 되면 메모리 초과가 발생하여 카운팅 정렬의 일부 특성만을 이용하여 풀도록 합니다.

다음과 같은 배열이 있다면 배열 내의 원소가 각각 몇 개 있는지 카운팅 합니다.

다음과 같은 배열을 얻을 수 있고 해당 문제에서는 정렬 결과를 출력하기 만을 요구하고 있습니다.
따라서 0부터 최댓값까지 해당 배열을 순회하며 해당 요소의 개수만큼 출력하기만 하면 됩니다.

#include <iostream>
using namespace std;
int main() {
    int N, m = 0; cin >> N; int c[10001] = { 0, };
    for (int i = 0; i < N; ++i) { int t; cin >> t; ++c[t]; m = t > m ? t : m; }
    for (int i = 1; i <= m; ++i) for (int j = 0; j < c[i]; ++j) cout << i << '\n';
}

배열을 입력 받는 과정에서 동시에 최댓값을 추출합니다.
이렇게 최댓값을 얻어내면 1부터 10001까지 훑을 필요 없이 최댓값까지만 훑으면 됩니다.
i<=m이 아닌 i<10001로 적어도 정답이지만 시간은 전자가 조금 더 빠릅니다.

1427번 소트인사이드

문제 링크
각 자리수를 내림차순으로 정렬하는 문제입니다. string 문자열을 사용하면 쉽게 풀 수 있습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
    string N; cin >> N; sort(N.begin(), N.end(), greater<>()); cout << N;
}

sort 함수의 세 번째 인자는 입력하지 않으면 기본값은 오름차순 정렬입니다.
내림차순 정렬을 위해서는 세 번째 인자에 내림차순 정렬을 가능하게 하는 함수 포인터를 대입해주어야 합니다.
<functional> 헤더의 greater<>()를 사용하면 함수를 구현하지 않고도 쉽게 내림차순 정렬을 할 수 있습니다.
오름차순 정렬의 경우에는 less<>()를 사용합니다.

11650번 좌표 정렬하기

문제 링크
x좌표를 기준으로 오름차순, x좌표가 같다면 y좌표를 기준으로 오름차순 정렬을 진행합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N; cin >> N; vector<pair<int, int>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end()); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

두 좌표쌍은 vector 배열의 pair을 이용하여 쉽게 정의할 수 있습니다.
첫 번째 값은 .first로 접근하며 두 번째 값은 .second를 통해 접근합니다.
sort 함수의 세 번째 인자를 설정하지 않으면 자동으로 오름차순 정렬을 진행합니다.
pair의 경우에도 .first 오름차순 > .second 오름차순으로 정렬이 이루어집니다.

11651번 좌표 정렬하기 2

문제 링크
두 번째 문제는 y좌표를 기준으로 오름차순, y좌표가 같다면 x좌표를 기준으로 오름차순 정렬을 진행합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int>& v1, pair<int, int>& v2) { if (v1.second == v2.second) return v1.first < v2.first; else return v1.second < v2.second; }
int main() {
    int N; cin >> N; vector<pair<int, int>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), cmp); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

.second가 1순위가 되어야 하므로 비교 함수를 따로 작성해야 합니다.
해당 코드처럼 bool을 반환하는 cmp 함수가 그 역할을 합니다.

1181번 단어 정렬

문제 링크
해당 문제 또한 비교 함수를 작성하는 문제라 크게 어려운 것이 없습니다.
길이 오름차순 이후 사전순(오름차순) 정렬을 진행합니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string s1, string s2) { if (s1.length() == s2.length()) return s1 < s2; else return s1.length() < s2.length(); }
int main() {
    int N; cin >> N; string* a = new string[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N, cmp); 
    for (int i = 0; i < N; ++i) if (i == 0 || a[i] != a[i - 1]) cout << a[i] << '\n';
}

10814번 나이순 정렬

문제 링크
나이를 기준으로 정렬하되, 나이가 같다면 입력 순서는 유지되어야 합니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(pair<int, string>p1, pair<int, string>p2) { return p1.first < p2.first; }
int main() {
    int N; cin >> N; vector<pair<int, string>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    stable_sort(v.begin(), v.end(), cmp); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

따라서 stable_sort 함수를 사용해야 합니다.
해당 함수는 이름 그대로 안정 정렬을 수행합니다.
그냥 sort를 사용할 경우 오답처리 됩니다.

18870번 좌표 압축

문제 링크
해당 원소보다 서로 다른 작은 원소가 몇 개 있는지를 출력하는 문제입니다.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
    int N; cin >> N; vector<long long> v1(N); vector<long long> v2(N); for (int i = 0; i < N; ++i) { cin >> v1[i]; v2[i] = v1[i]; }
    sort(v2.begin(), v2.end()); v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (int i = 0; i < N; ++i) cout << lower_bound(v2.begin(), v2.end(), v1[i]) - v2.begin() << ' ';
}

사용해야 할 함수가 많아 조금 당황했던 문제입니다.
unique 함수는 <algorithm> 헤더 내에 존재하며 중복되는 원소들을 뒤로 밀어낸 뒤 중복되지 않은 데이터들이 끝나는 지점을 반환합니다.
erase 함수는 지정 범위를 삭제하는 함수입니다.
따라서 중복되는 부분을 모두 삭제합니다.
lower_bound 함수는 해당 원소가 범위 내에서 처음 등장하는 위치를 찾습니다.
해당 위치에서 배열의 시작 부분을 빼면 해당 원소의 인덱스, 즉 해당 원소 앞에 있는 원소의 개수가 됩니다.

[BOJ/C++] 단계별로 풀어보기 - 정렬(1)

dbsans — Mon, 12 Jan 2026 11:13:04 +0000

2026.01.12일차 입니다.
알바하고 어쩌고 하느라 좀 많이 밀렸습니다.
어제는 시간이 꽤 있었는데 지쳤는지 기운이 안 나서 좀 쉬었습니다.
요즘 잡생각이나 괜한 걱정도 많아지고 좋아하던 게임을 해봐도 오히려 더 지치는게 상태가 많이 안 좋은 거 같습니다.
그래도 오늘은 락 수혈하니까 좀 괜찮은 거 같아요.

아무튼 정렬 풀어보았습니다.
알고리즘만 정리해도 글이 너무 길어져 글을 두 개로 나누었습니다.
정렬(1)에서는 알고리즘에 대해 설명하고 정렬(2)에서는 정렬 내장 함수를 이용해 코테 문제들을 풀어보았습니다.

요약

<queue> - 우선순위 큐 priority_queue greater로 선언하게 되면 오름차순으로 설정되며 이는 최소 힙 / heapify 함수를 통해 배열을 최대 힙

2750번 수 정렬하기

문제 링크
시간 복잡도 O(n²)인 정렬 알고리즘을 사용하는 문제입니다. 버블 정렬, 선택 정렬, 삽입 정렬 등이 있습니다.
정렬 알고리즘을 공부하며 해당 블로그를 많이 참고하였습니다.

버블 정렬(Bubble sort)

인접한 두 수를 비교/정렬하는 알고리즘 입니다.

이미지 출처

첫 번째 원소와 두 번째 원소를 비교/정렬, 두 번째 원소와 세 번째 원소를 비교/정렬, ..., n-1 번째 원소와 n 번째 원소를 비교/정렬합니다.
가장 큰 원소가 맨 뒤로 이동했으므로 다시 처음부터 n-2 번째 원소와 n-1 번째 원소까지 비교/정렬하고 정렬 안된 원소 중 가장 큰 원소를 맨 뒤로 보내는 것을 모두 정렬될 때까지 반복합니다.

실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n²)의 시간복잡도를 가집니다.
또한 최선의 경우든 최악의 경우든 어떠한 상황에서도 O(n²)의 복잡도를 가집니다.

가장 구현이 쉽지만 인접 원소를 일일이 비교하며 불필요한 비교 반복이 자주 일어나 매우 비효율적인 알고리즘입니다.

#include <iostream>
using namespace std;

void bubble_sort(int a[], int n) {
    for (int i = n - 1; i > 0; --i) for (int j = 0; j < i; ++j) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}

int main() {
    int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    bubble_sort(a, N); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}

다음과 같이 구현하며 인접 원소의 대소를 비교 후 정렬합니다.

선택 정렬(Selection sort)

최솟값/최댓값을 찾아 맨 앞으로 정렬하는 알고리즘입니다.

이미지 출처

처음부터 끝까지 훑으며 최솟값/최댓값을 찾아냅니다. 찾아낸 최댓값/최솟값을 맨 앞의 값과 교환합니다.
최댓값/최솟값이 맨 앞으로 이동했으므로 두 번째 원소부터 끝까지 훑으며 정렬이 안된 원소 중 최댓값/최솟값을 찾아 두 번째 원소와 교환합니다.
해당 방법을 모두 정렬될 때까지 계속 반복합니다.

실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n²)의 시간복잡도를 가집니다.
또한 최선의 경우든 최악의 경우든 어떠한 상황에서도 O(n²)의 복잡도를 가집니다.
버블 정렬과 동일한 시간복잡도를 가지지만 선택 정렬은 불필요한 교환이 일어나지 않아 버블 정렬보다 조금 더 빠릅니다.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void selection_sort(vector<int>& v) {
    const int n = v.size();
    for (int i = 0; i < n - 1; ++i) {
        int m = i; for (int j = i + 1; j < n; ++j) {
            if (v[j] < v[m]) m = j;
        } if (i != m) swap(v[i], v[m]);
    }
}

int main() {
    int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
    selection_sort(v); for (int n : v) cout << n << '\n';
}

다음과 같이 작성할 수 있으며 배열을 훑으며 최솟값의 인덱스를 갱신합니다.
교환은 맨 마지막에 한 번 일어납니다.

삽입 정렬(Insertion sort)

요소를 이미 정렬된 부분과 비교하여 해당하는 위치를 찾아 삽입하는 알고리즘입니다.

이미지 출처

두 번째 원소부터 시작하며 앞의 원소는 정렬된 부분으로 간주합니다.
앞의 원소와 비교하며 해당하는 위치가 발견되면 루프를 종료하며 해당 위치에 원소를 삽입합니다.

실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n²)의 시간복잡도를 가집니다.
하지만 해당 위치가 발견되면 앞은 검사하지 않고 종료하는 특성 때문에 삽입 정렬은 최선의 경우에는 n-1번으로 O(n)의 시간복잡도를 가질 수 있습니다.

#include <iostream>
using namespace std;

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int k = a[i], j = i - 1; while (j >= 0 && a[j] > k) { a[j + 1] = a[j]; j--; } a[j + 1] = k;
    }
}

int main() {
    int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    insertion_sort(a, N); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}

다음과 같이 작성할 수 있으며 정렬된 부분 뒤에서부터 비교하며 해당 위치가 발견되기 전까지 원소를 차례 차례 뒤로 옮깁니다.
위치가 발견되면 루프가 종료되며 해당 위치에 원소를 삽입합니다.

수 정렬하기 2

문제 링크
시간 복잡도 O(n log n)인 정렬 알고리즘을 사용하는 문제입니다. 병합 정렬, 힙 정렬, 퀵 정렬 등이 있습니다.

병합 정렬(Merge sort)

배열을 반으로 쪼갠 후 정렬 한 후 합쳐나가는 알고리즘 입니다.

이미지 출처

이미지 출처

어떠한 상황에서도 O(n log n)의 시간복잡도를 가지지만 정렬된 데이터를 담을 배열이 추가적으로 필요하기에 메모리 사용이 비효율적입니다.

#include <iostream>
using namespace std;
int s[1000001];

// O(n)
void merge(int a[], int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) s[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    if (i > m) for (int n = j; n <= r; ++n) s[k++] = a[n];
    else for (int n = i; n <= m; ++n) s[k++] = a[n];
    for (int n = l; n <= r; ++n) a[n] = s[n];
}

// O(n log n)
void merge_sort(int a[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(a, l, m); merge_sort(a, m + 1, r); merge(a, l, m, r);
    }
}

int main() {
    int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    merge_sort(a, 0, N - 1); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}

배열을 분할하고 분할한 배열 내에서 또 분할하기를 반복하기 때문에 재귀 함수를 통해 구현합니다.
나누어진 두 배열을 합치며 정렬을 진행합니다.
여기서 a[i] <= a[j] ? a[i++] : a[j++]; 값이 크거나 같다면 a[i++] 왼쪽 배열의 값이 앞으로 정렬됩니다.
값이 같을 때 왼쪽에 있던 것을 먼저 배치함으로써 입력 순서가 유지되고 이러한 정렬을 안정 정렬(stable sort)이라고 합니다.

힙 정렬(Heap sort)

최대힙/최소힙을 이용한 정렬 알고리즘입니다. 힙이란 완전 이진트리 형태의 자료구조로 부모 노드가 자식 노드보다 큰 구조를 최대 힙, 작으면 최소 힙이라고 합니다.
최대힙/최소힙은 단계별로 풀어보기 우선순위 큐에서 자세히 설명하도록 하겠습니다.

이미지 출처

최대힙/최소힙을 사용하면 최댓값/최솟값이 배열의 맨 앞에 위치하게 되므로 배열의 최댓값/최솟값을 빠르게 찾을 수 있습니다.
힙 정렬은 최대힙/최소힙으로 찾은 최댓값/최솟값을 맨 앞에 위치시키며 배열을 정렬해나가는 방식입니다.
선택 정렬에서 최댓값/최솟값을 찾는 방식을 힙으로 사용한 것이라고도 볼 수 있습니다.

전체를 훑으며 최솟값을 찾기 때문에 O(n)이 소요되며 힙 정렬을 사용하며 O(log n)이 소요되어 총 O(n log n)이 소요됩니다.
힙 정렬은 어떠한 상황에서도 O(n log n)의 시간복잡도가 소요됩니다.

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

void heap_sort(vector<int>& v) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int n : v) pq.push(n);
    v.clear();
    while (!pq.empty()) { v.push_back(pq.top()); pq.pop(); }
}

int main() {
    int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
    heap_sort(v); for (int n : v) cout << n << '\n';
}

<queue> 헤더를 사용하여 다음과 같이 풀 수 있습니다.
priority_queue를 선언하여 우선순위 큐를 만듭니다. greater<int>로 선언하게 되면 오름차순으로 설정되며 이는 최소 힙이 됩니다.
이 우선순위 큐에 정렬할 배열의 원소들을 넣으면 가장 작은 값이 맨 위에 위치하는 최소 힙이 만들어집니다.
최소 힙의 가장 위에 위치한 값, 즉 최솟값을 차례 차례 배열로 옮기며 정렬을 완성합니다.

우선순위 큐를 직접 구현할 수도 있습니다.
코드를 설명하기에 앞서 우리는 해당 사실을 짚고 넘어가야 합니다.

이미지 출처

힙을 배열으로 표현하게 되면

왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
부모 노드 인덱스 = 자식 노드 인덱스 / 2

로 표현할 수 있습니다.
코드는 다음과 같습니다.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void heapify(vector <int>& v, int n, int i) {
    int m = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l<n && v[l]>v[m]) m = l;
    if (r<n && v[r]>v[m]) m = r;
    if (m != i) { swap(v[i], v[m]); heapify(v, n, m); }
}

void heap_sort(vector<int>& v) {
    int n = v.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(v, n, i);
    for (int i = n - 1; i > 0; --i) { swap(v[0], v[i]); heapify(v, i, 0); }
}

int main() {
    int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
    heap_sort(v); for (int n : v) cout << n << '\n';
}

heapify 함수를 통해 배열을 최대 힙으로 반환하고 heap_sort 함수에서 최대 힙의 맨 앞의 값, 즉 최댓값을 뒤로 보내며 정렬합니다.
뒤에서부터 정렬하며 정렬되지 않은 부분을 계속 최대 힙으로 반환하며 최댓값을 찾아 뒤로 보냅니다.

오름차순 정렬인데 최대 힙을 사용한 이유는 제자리 정렬(In-place)을 하기 위함입니다.
최대 힙의 맨 앞의 값, 즉 루트(v[0])에 최댓값이 있으므로 이를 뒤로 보내기만 하면 정렬이 이루어집니다.
추가적인 메모리 공간이 필요하지 않고 정렬되지 않은 부분만 힙 정렬을 진행하면 되므로 이는 제자리 정렬에 해당합니다.

퀵 정렬(Quick sort)

피벗(pivot)이라는 한 원소를 설정하여 피벗을 기준으로 왼쪽에는 작은 원소, 오른쪽에는 큰 원소를 배치시킵니다.
이 과정에서 떨어진 원소끼리의 교환이 일어나 입력 순서를 보장 받지 못해 불안정 정렬 알고리즘에 해당합니다.

이미지 출처

평균적으로 퀵 정렬의 시간복잡도는 O(n log n)이지만 최악의 상황에서는 O(n²)의 시간복잡도가 소요될 수도 있습니다.
이거 때문인지 제출하니까 시간 초과 뜨더라고요.

#include <iostream>
using namespace std;

void quick_sort(int a[], int i, int j) {
    if (i >= j) return;
    int p = a[(i + j) / 2]; int l = i, r = j;
    while (l <= r) {
        while (a[l] < p) ++l; while (a[r] > p) --r;
        if (l <= r) { swap(a[l], a[r]); ++l; --r; }
    } quick_sort(a, i, r); quick_sort(a, l, j);
}

int main() {
    int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    quick_sort(a, 0, N - 1); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}

피벗을 중간값으로 설정하여 피벗의 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값을 위치시킵니다.
이후 왼쪽과 오른쪽으로 나누어 그 속에서 피벗을 설정하고 배치하기를 반복합니다.

사실 백준에서는 해당 문제를 내장 함수를 이용하여 푸는 것을 추천하고 있습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n, tmp; cin >> n;
    vector<int> arr;

    for (int i = 0; i < n; i++) {
        cin >> tmp; arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n; i++) cout << arr[i] << '\n';
}

1년 전에 작성한 코드라 그런지 많이 기네요.

하지만 다양한 정렬 알고리즘을 직접 타이핑 하고 블로그를 작성하며 정렬 알고리즘에 대해 이해할 수 있었습니다.
정렬 알고리즘에 이해가 부족했던 1년 전에 비하면 꽤나 성장한 것 같다는 생각이 듭니다.
근데 다른 문제들은 그냥 내장 함수 쓰겠습니다.
구현해서 쓰고 하려면 귀찮아서

[BOJ/C++] 단계별로 풀어보기 - 브루트 포스

dbsans — Thu, 08 Jan 2026 09:39:39 +0000

2026.01.08일차 입니다. 브루트 포스 풀어보았습니다.

요약

string - to_string

브루트 포스란?

브루트 포스(Brute Force)란 무차별 대입이라고도 부르며 모든 경우의 수를 대입하여 답을 찾는 방법입니다.
모든 경우의 수를 탐색하므로 정확성은 높으나 복잡도에 매우 민감하다는 치명적인 단점이 있습니다.
주로 반복문과 조건문을 통하여 답을 도출합니다.

2798번 블랙잭

문제 링크
^NC³ 문제이므로 세 개의 반복문을 통해 구현해야 합니다.

중복 없는 세 장을 구하기 위해서 0≤i＜N-2, i+1≤j＜N-1, j+1≤k＜N의 인덱스로 구성해야 합니다.

#include <iostream>
using namespace std;
int main() {
    int N, M, r = 0; cin >> N >> M; int* arr = new int[N]; for (int i = 0; i < N; ++i) cin >> arr[i];
    for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            for (int k = j + 1; k < N; ++k) { int t = arr[i] + arr[j] + arr[k]; r = t > r && t <= M ? t : r; }
        }
    } cout << r;
}

서로 다른 세 장의 카드를 더한 값이 M 이하인 값 중 최댓값을 도출하면 됩니다.