📝 Computer Science

[C] 이진 탐색 트리(BST)

이진 탐색 트리(BST) 각각의 노드가 최대 2개의 자식 노드를 가지는 이진 트리의 구조를 갖추고 있다. 연결 리스트로 구현된다. 기본 원리 모든 노드의 값은 유일하다. 루트 노드를 기준으로 왼쪽에 있는 값들은 루트 노드의 값보다 작다. 루트 노드를 기준으로 오른쪽에 있는 값들은 루트 노드의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 문제 #include using namespace std; typedef struct node_struct { int data; struct node_struct* left; struct node_struct* right; }node; node* insert_node(node* root, int value) { if (root == NULL) { root..

[C++] binary_search, lower_bound, upper_bound

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..

[C++] 이분 탐색(Binary Search)

이분 탐색(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..

[C++] 분할 정복(Divide and Conquer)

분할 정복(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..

[C++] 그리디(Greedy)

그리디(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..

[C++] 백 트래킹(Back Tracking)

백 트래킹(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개를 고른 수..