binary_search, lower_bound, upper_bound 정렬되어 있는 배열, 컨테이너 등을 대상으로 탐색한다. binary_search: 탐색 대상이 되는 값이 존재하는지 확인하고 들어 있다면 true, 없다면 false를 반환한다. lower_bound: 찾고자 하는 값 이상이 처음 나타나는 위치를 반환한다. upper_bound: 찾고자 하는 값을 초과하는 값이 처음 나타나는 위치를 반환한다. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www..

이분 탐색(Binary Search) 선형 자료구조가 정렬되어 있을 때 특정한 값을 빠르게 찾는 방법이다. 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. www.acmicpc.net #include #include using namespace std; int main() { int N, M; int a[100000]; cin >> N..

분할 정복(Divide and Conquer) 말 그래도 문제를 분할과 정복으로 나눠서 해결하는 것을 말한다. 분할 단계에서는 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아질수록 풀기 쉬워지기 때문이다. 대체로 분할 정복은 재귀 호출을 사용한다. 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net #include #include using namespace..

그리디(Greedy) 각 단계에서 최선의 선택을 하는 알고리즘으로 탐욕적 기법이라고도 부른다. 즉, 말 그대로 눈앞의 가장 큰 이익만 좇는 기법이다. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n); // 끝나는 시간, 시작 시간 for (int i = 0; i > v[i].second >> v[i].first; sort(v.begin(), v.end()); int ans..

백 트래킹(Back Tracking) 한정 조건이 주어졌을 때 해를 얻을 때까지 모든 경우의 수를 검사하는 알고리즘으로 가다가 다시 돌아와서 다른 길로 간다. 모든 경우를 고려해야 하므로 재귀 함수를 이용한 DFS를 사용한다. 기본 원리 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net #include using namespace std; int n, m; int number[8]; bool ck[9]; // 중복 없이 M개를 고른 수..

브루트 포스(Brute Force) 연산이 1억회가 안 넘어갈 때 모든 경우의 수를 검사하는 알고리즘으로 완전 탐색이라고도 한다. 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #include #include using namespace std; bool board[50][50]; int compare(int x, int y, bool white) { int cnt = 0; for (int i = 0; i < 8; i++) { f..