알고리즘 wrap up
알고리즘 강의를 들은 내용들을 기억하기 위해 전반적인 내용을 정리하였습니다.
STL
https://velog.io/@khg04202/STL-%EC%B4%9D%EC%A0%95%EB%A6%AC
-
시간 복잡도 요구 사항 파악
- 삽입/삭제/탐색을 자주 하는 경우
map/set또는unordered_map/unordered_setunordered_map/unordered_set
- 가장 큰/작은 값 추출
priority_queue
- 앞에서 빼고 뒤로 넣기
- 한쪽 방향만 필요하다면 →
queue - 양쪽 모두 필요하다면 →
deque
- 한쪽 방향만 필요하다면 →
- 시간 복잡도에 대한 제한 사항 확인하기
- 삽입/삭제/탐색을 자주 하는 경우
-
정렬의 필요성
- 결과적으로 정렬 상태가 필요한가?
map,set, 혹은sort함수 사용
- 특정 값의 범위를 찾을 때 (정렬 필요)
lower_bound,upper_bound
- “K번째 원소”에 집중
nth_element
- 결과적으로 정렬 상태가 필요한가?
-
중복 제거 & 효율적 관리
unique+erase패턴 (정렬 필요)- 혹은
set/unordered_set
우선순위 큐
- 힙(Heap) 자료구조 사용
- 삽입 삭제
O(Log N), 가장 우선순위 높은 원소 조회는O(1)(top()) - 가장 큰/작은 원소를 빠르게 추출
예제코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(6);
pq.push(12);
pq.push(4);
cout << "top: " << pq.top() << endl; // 12
pq.pop(); // top(12) 제거
cout << "top: " << pq.top() << endl; // 6
}최소 힙은 선언 할 때 3번째 인자로 greater<T>
priority_queue<int, vector<int>, greater<int>> minPq;- 음수로 넣고 꺼낼 때 부호를 바꿔주면 greater 없이 구현 가능
순열
next_permutation / prev_permutation
사전 순 다음 순열 / 사전 순 이전 순열
반드시 원본 데이터를 정렬한 뒤 사용
예제 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5};
for(int x : v) cout << x << " "; // 1 2 3 4 5
cout << endl;
// 다음 순열
next_permutation(v.begin(), v.end());
for(int x : v) cout << x << " "; // 1 2 3 5 4
cout << endl;
// 다음 순열
next_permutation(v.begin(), v.end());
for(int x : v) cout << x << " "; // 1 3 2 4 5
cout << endl;
// 이전 순열
prev_permutation(v.begin(), v.end());
for(int x : v) cout << x << " "; // 1 2 3 5 4
cout << endl;
}<Numeric> 헤더
연속 구간 합(partial_sum)
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4};
vector<int> psum(4);
partial_sum(v.begin(), v.end(), psum.begin());
cout << psum[0] << endl; // 1
cout << psum[1] << endl; // 3 (1 + 2)
cout << psum[2] << endl; // 6 (1 + 2 + 3)
cout << psum[3] << endl; // 10 (1 + 2 + 3 + 4)
int sum = psum[3] - psum[1]; // 구간 [2, 4]의 합
}유니크 값(unique)
정렬 필수
vector<int> v = {1, 4, 4, 2, 2, 2, 5, 1};
sort(v.begin(), v.end()); // 정렬 필수! 1, 1, 2, 2, 2, 4, 4, 5
auto newEnd = unique(v.begin(), v.end()); // 1, 2, 4, 5, ?, ?, ?, ?
v.erase(newEnd, v.end()); // 1, 2, 4, 5총합(accumulate)
// 총합 구하기 3번 째 인자: 초기 값
int sum = accumulate(v.begin(), v.end(), 0);
// 4번째 인자로 multiplies<int>())를 넣어 총 곱 계산, 초기 값 1로 해야함
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>()); 빠른 이진 탐색
lower_bound / upper_bound 정렬된 구간에서 이진 탐색 O(log n)
lower_bound : x 이상의 값이 나오는 최초 위치
upper_bound : x 초과의 값이 나오는 최초 위치
예제 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 4, 4, 5, 7, 8};
auto lb = lower_bound(v.begin(), v.end(), 4);
auto ub = upper_bound(v.begin(), v.end(), 4);
cout << (lb - v.begin()) << endl; // 2
cout << (ub - v.begin()) << endl; // 4
}원소 변환(transform)
구간 내 원소를 함수를 모두 적용하는 함수
2가지 사용법
1. 단항 연산: 각 원소를 하나씩 변환 (예: 모두 2배)
2. 이항 연산: 두 구간의 원소들을 짝지어서 변환 (예: 같은 인덱스끼리 더하기)
단항 연산 예제 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // pow 함수를 위해 필요
using namespace std;
int main() {
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2(5); // v2 크기 미리 확보!
transform(v1.begin(), v1.end(), v2.begin(), [](int x){
return pow(x, 2); // 각 원소를 제곱!
});
for(int x : v2) cout << x << " "; // 1 4 9 16 25
}v2 확보 필수!
이항 연산 예제 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // plus<int> 를 위해 필요
using namespace std;
int main() {
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {6, 7, 8, 9, 10};
vector<int> v3(5);
transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), plus<int>()); // plus<int>() 사용!
for(int x : v3) cout << x << " "; // 7 9 11 13 15
}v1, v2는 반드시 같은 크기
최대값 & 최소값
max_element, min_element, minmax_element
iterator 반환
예제 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {4, 1, 6, 3, 8, 2};
// 1. max_element: 최댓값의 위치를 찾아줍니다
auto max_it = max_element(v.begin(), v.end());
cout << "최댓값: " << *max_it << endl; // 8 출력
// 2. min_element: 최솟값의 위치를 찾아줍니다
auto min_it = min_element(v.begin(), v.end());
cout << "최솟값: " << *min_it << endl; // 1 출력
// 3. minmax_element: 최솟값과 최댓값을 한 번에! (구조적 바인딩 활용했어요)
auto [min_iter, max_iter] = minmax_element(v.begin(), v.end());
cout << "최댓값2: " << *max_iter << endl; // 8 출력
cout << "최소값2: " << *min_iter << endl; // 1 출력
}조건 만족하는 원소 개수
count, count_if
예제 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1, 1, 2, 2, 3, 3};
// 값이 2인 원소 개수
int cnt = count(v.begin(), v.end(), 2);
// 짝수 개수
int even_cnt = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
cout << "값이 2인 원소 개수: " << cnt << endl;
cout << "짝수인 원소 개수: " << even_cnt << endl;
}iterator 이동
std::distance, std::advance
iterator 거리 계산 및 이동
int idx = distance(v.begin(), it); // idx = 2
advance(it, idx); // it를 2칸 전진코딩 테스트 팁
헤더 파일 모두 포함
#include <bits/stdc++.h>
C++ 표준 라이브러리를 모두 포함
효율적인 입력 출력
출력 속도 향상을 위한 코드
ios::sync_with_stdio(false);cin.tie(nullptr);(orcin.tie(0);)
C 표준 입출력(stdio)와 C++ 스트림을 분리하여 동작하므로 버퍼링 효율이 좋아져서 입출력이 약간 더 빨라집니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> a >> b;
cout << a + b << "\n";
}\n을 쓰는 이유: endl을 쓰게 되면 출력 버퍼가 강제로 flush 되어 느려질 수 있어서 \n 사용
문자열 전체 입력(공백 포함)
getline(cin, s);정렬 알고리즘
브루트포스(Brute Force)
가능한 모든 경우의 수 시도
자료의 크기가 작거나, 최적화된 알고리즘을 떠올리기가 어려울 때, 혹은 검증 과정을 위해서(정답이 정말 맞는지) 사용
n개의 원소가 있다면 부분집합의 개수는 2^n, 순열의 개수는 n! (팩토리얼) 가 됩니다.
- 부분집합을 전부 구하는 브루트포스: 2^n
- 순열(모든 원소를 나열하는 경우)의 브루트포스: n!
- 이중, 삼중 반복문 등을 이용한 모든 ‘조합’ 탐색
불필요한 중복을 제거하여 최적화 가능
백트래킹
트리
그래프
DFS
BFS
힙과 다익스트라(Dijkstra)
문자열
게임 개발자가 꿈인 게이머