알고리즘을 위한 C++
알고리즘을 위한 C++ 기초
목차
1. 기본 입출력
2. STL 이란?
3. 자주 쓰는 테크닉
1. 기본 입출력
헤더파일
c++
#include <iostream>C++에서는 기본 입출력 헤더파일이 C 언어와 다르다. C++은 iostream이라는 헤더파일을 기본적으로 사용한다. 또한 네임 스페이스라는 새로운 개념이 등장한다.
네임스페이스란?
식별자들의 이름이 충돌하지 않고 고유함을 보장하는 코드 영역을 말한다. 우리가 사용할 기본 입출력은 모두 std 라는 네임스페이스 안에 들어있기 때문에 헤더파일 아래에
c++
using namespace std;라는 std 라는 네임스페이스를 사용하겠다는 선언을 해준다.
아래는 네임스페이스를 사용할 경우와 사용하지 않을 경우의 차이이다.
c++
std::cin>>a>>std::endl;
//네임스페이스를 사용하지 않을 경우
cin>>a>>endl;
//네임스페이스를 사용할 경우보다시피 네임스페이스를 사용하면 코드의 길이가 확연히 줄어들게 된다.
c++
#include <iostream>
using namespace std;이 두 줄을 적게되면 C++를 사용할 준비가 완료된 것이다.
또한 아래는 우리가 자주 사용할 추가적인 헤더 파일들이다.
c++
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
...
#include <bits/stdc++.h>
//웬만하면 사용 추천 안함, but 거의 모든 헤더파일을 포함하고있음입출력 속도 최적화
알고리즘 문제를 풀 때 입출력 데이터가 많으면 시간 초과가 발생할 수 있다. 이를 방지하기 위해 아래 코드를 main 함수 시작 부분에 추가한다.
c++
ios::sync_with_stdio(false);
cin.tie(NULL);ios::sync_with_stdio(false): C와 C++의 입출력 버퍼를 분리하여 속도를 높인다. 단, 이후scanf/printf와cin/cout을 혼용하면 안 된다.cin.tie(NULL): cin과 cout의 묶음을 풀어 출력 버퍼를 매번 비우지 않게 한다.
endl vs '\n'
c++
cout << "Hello" << endl; // 버퍼를 flush하여 느림
cout << "Hello" << '\n'; // 단순 개행, 빠름endl은 개행과 함께 버퍼를 비우는(flush) 작업을 수행하므로 느리다. 알고리즘 문제에서는'\n'을 사용하는 것이 좋다.
2. STL 이란?
STL은 Standard Template Library의 약자로, 여러 자료구조, 함수, 알고리즘 등을 쓰기 쉽게 라이브러리화 해둔 것이다.
STL은 컨테이너, 반복자, 알고리즘 총 3가지로 나눌 수 있다.
2.1. 컨테이너
컨테이너는 자료를 저장하는 클래스들의 집합이다.
c++
pair
vector
deque
list
map
set
stack
queue
priority queue등이 있다.
| 컨테이너 | 설명 |
|---|---|
| pair | 두 개의 값을 묶어 저장 |
| vector | 동적 배열 |
| deque | 양방향 큐 |
| list | 연결 리스트 |
| stack | 스택 (LIFO) |
| queue | 큐 (FIFO) |
| priority_queue | 우선순위 큐 (힙) |
| set | 정렬된 집합 (중복 X) |
| map | 키-값 쌍 저장 |
2.1.1. pair
pair 자료구조는 first와 second, 즉 자료 2개를 묶어서 저장하는 자료형이다. 주로 좌표를 저장할 때 많이 사용된다.
사용 방법은 아래와 같다.
c++
pair<int,int> p;
// 선언
p = {a, b}; // 1
p = make_pair(a,b); // 2
// 저장 (1과 2는 정확히 같은 동작)
x = p.first; y = p.second;
// 접근선언할 때에는 pair 옆의 꺽쇠 안에 자료형 2개를 쉼표로 구분하여 넣어주면 된다. 두 자료형은 같을 필요가 없다. 즉 string과 int를 함께 저장할 수도 있는 것이다.
값을 저장할 때에는 직접 중괄호로 묶어서 저장해도 되고, make_pair 함수를 사용해도 좋다.
접근은 왼쪽 자료는 .first, 오른쪽 자료는 .second 로 접근한다.
2.1.2. vector
vector 자료구조는 기본적으로는 배열과 같다. 하지만 값이 새로 들어올 때마다 공간을 할당하는 동적 할당을 사용하여 메모리를 절약한다는 장점이 있다.
사용 방법은 아래와 같다.
- 선언과 초기화
c++
vector<int> v; // 빈 벡터
vector<int> v(n); // 크기 n, 모든 원소 0으로 초기화
vector<int> v(n, val); // 크기 n, 모든 원소 val로 초기화
vector<int> v = {1, 2, 3, 4, 5}; // 초기값 지정
// 2차원 벡터
vector<vector<int>> v2; // 빈 2차원 벡터
vector<vector<int>> v2(n, vector<int>(m)); // n×m, 0으로 초기화
vector<vector<int>> v2(n, vector<int>(m, val)); // n×m, val로 초기화- 주요 메서드
c++
v.push_back(val); // 맨 뒤에 val 추가, O(1)
v.pop_back(); // 맨 뒤 원소 제거, O(1)
v.front(); // 맨 앞 원소 반환
v.back(); // 맨 뒤 원소 반환
v.size(); // 원소 개수 반환
v.empty(); // 비어있으면 true
v.clear(); // 모든 원소 제거
v.resize(n); // 크기를 n으로 변경
v.resize(n, val); // 크기를 n으로 변경, 새 원소는 val로 초기화- 접근과 수정
c++
v[i] = 3; // i번째 원소 수정 (범위 체크 X)
v.at(i) = 3; // i번째 원소 수정 (범위 체크 O, 느림)- 2차원 벡터 사용
c++
vector<vector<int>> v2;
v2.push_back(vector<int>()); // 새로운 행 추가
v2[0].push_back(1); // 0행의 맨 뒤에 1 추가
v2[0][0] = 5; // 0행 0열의 값 수정- vector + pair 조합 : 좌표를 저장하기 위해 많이 사용한다.
c++
vector<pair<int, int>> vp;
vp.push_back({1, 2}); // (1, 2) 추가
vp.emplace_back(3, 4); // (3, 4) 추가 (더 효율적)
vp[0].first = 10; // 첫 번째 원소의 first 수정2.1.3. string
string은 문자열을 다루는 컨테이너이다. vector와 유사하게 작동한다.
- 선언과 초기화
c++
string s; // 빈 문자열
string s = "Hello"; // 초기값 지정
string s(5, 'a'); // "aaaaa"- 주요 메서드
c++
s.length(); // 문자열 길이 (size()와 동일)
s.empty(); // 비어있으면 true
s.substr(pos, len); // pos부터 len개의 문자 반환
s.find("str"); // "str"의 시작 위치 반환, 없으면 string::npos
s.append("str"); // 뒤에 "str" 추가
s += "str"; // 뒤에 "str" 추가 (더 간단)- 문자열 비교와 연산, 변환
c++
string a = "abc";
string b = "abd";
// a < b (사전순 비교)
string c = a + b; // "abcabd" (문자열 연결)
int num = 123;
string s = to_string(num); // "123"
string s = "456";
int num = stoi(s); // 456
long long num2 = stoll(s); // long long으로 변환
2.1.4. stack
LIFO(Last In First Out) 구조의 자료구조이다. DFS, 괄호검사 등에 사용된다. 자세한 내용은 제목 클릭
2.1.5. queue
FIFO(First In First Out) 구조의 자료구조이다. BFS에서 필수적으로 사용된다.
자세한 내용은 제목 클릭
2.1.6. priority_queue
우선순위 큐(힙) 이다. 기본적으로 최대 힙으로 동작한다. 다익스트라 알고리즘 등에 사용된다.
자세한 내용은 제목 클릭
2.1.7 set
정렬된 상태를 유지하는 집합이다. 중복을 허용하지 않는다. 내부적으로 레드-블랙 트리로 구현되어있다.
c++
set<int> s;
s.insert(val); // val 추가, O(log n)
s.erase(val); // val 제거, O(log n)
s.find(val); // val의 iterator 반환, 없으면 s.end()
s.count(val); // val의 개수 (0 또는 1)
s.size(); // 원소 개수
s.empty(); // 비어있으면 true
s.clear(); // 모든 원소 제거2.2. 반복자
반복자는 컨테이너의 원소를 가리키는 포인터와 유사한 객체이다. STL 알고리즘 함수들과 함께 사용된다.
기본 사용법
c++
vector<int> v = {1, 2, 3, 4, 5};
vector<int>::iterator it = v.begin(); // 첫 번째 원소를 가리킴
auto it = v.begin(); // auto 사용 (더 간단)
*it; // 현재 가리키는 원소의 값
it++; // 다음 원소로 이동
it--; // 이전 원소로 이동
it + n; // n칸 뒤의 iterator (vector, deque만 가능)begin() 과 end()
c++
v.begin(); // 첫 번째 원소를 가리키는 iterator
v.end(); // 마지막 원소의 **다음**을 가리키는 iterator
// [begin, end) 형태의 반열린 구간3. 자주 쓰는 테크닉
3.1 무한대 표현
c++
const int INF = 1e9; // 10억 (int 범위 내 안전)
const int INF = 0x3f3f3f3f; // 약 10억, INF + INF도 오버플로우 안 남
const long long INF = 1e18; // long long용 무한대memset과 함께 사용
c++
int dist[1000];
memset(dist, 0x3f, sizeof(dist)); // 모든 원소를 INF로 초기화
// 0x3f3f3f3f가 됨 (0x3f가 4번 반복)3.2 방향 배열 (dx, dy)
2차원 그래프 탐색(BFS, DFS)에서 4방향 또는 8방향 이동에 사용한다.
c++
// 4방향 (상하좌우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 8방향 (대각선 포함)
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// 사용 예시
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위 체크
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 방문 체크 등...
}3.3 2차원 배열 입력
c++
int n, m;
cin >> n >> m;
// 방법 1: 일반 배열
int arr[100][100];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
// 방법 2: vector
vector<vector<int>> v(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> v[i][j];
}
}
// 방법 3: 문자열로 입력받기 (공백 없이 붙어있는 경우)
// 예: 110010
vector<string> grid(n);
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
// grid[i][j]로 접근 (char 타입)
// '0'과 '1' 등 문자로 비교3.4 구조적 바인딩 (C++17)
pair나 tuple의 원소를 편리하게 분리할 수 있다.
c++
pair<int, int> p = {1, 2};
// 기존 방식
int x = p.first;
int y = p.second;
// 구조적 바인딩 (C++17)
auto [x, y] = p;
// BFS에서 활용
queue<pair<int, int>> q;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
// x, y 바로 사용 가능
}3.5 자주 쓰는 매크로
c++
#define fastio ios::sync_with_stdio(false); cin.tie(NULL);
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()
// 사용 예시
int main() {
fastio
vector<int> v = {3, 1, 2};
sort(all(v)); // sort(v.begin(), v.end())
for (int i = 0; i < sz(v); i++) { // size() 경고 방지
cout << v[i] << ' ';
}
}3.6 비트 연산
c++
// 기본 비트 연산
a & b // AND
a | b // OR
a ^ b // XOR
~a // NOT
a << n // 왼쪽 시프트 (a * 2^n)
a >> n // 오른쪽 시프트 (a / 2^n)
// 비트마스킹 테크닉
(1 << n) // 2^n
(x & (1 << i)) // x의 i번째 비트가 1인지 확인
(x | (1 << i)) // x의 i번째 비트를 1로 설정
(x & ~(1 << i)) // x의 i번째 비트를 0으로 설정
(x ^ (1 << i)) // x의 i번째 비트를 토글
__builtin_popcount(x) // x의 1인 비트 개수 (gcc)3.7 기본 알고리즘 템플릿
BFS 템플릿
c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
int arr[100][100];
bool visited[100][100];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void bfs(int startX, int startY) {
queue<pair<int, int>> q;
q.push({startX, startY});
visited[startX][startY] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny]) continue;
if (arr[nx][ny] == 0) continue; // 벽 등 조건
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}DFS 템플릿
c++
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int arr[100][100];
bool visited[100][100];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny]) continue;
if (arr[nx][ny] == 0) continue;
dfs(nx, ny);
}
}