본문 바로가기

전체 글

 (54)
Trees & Graphs ※ '엔지니어대한민국' 유튜브 채널을 통해 공부하였습니다. * 트리란? 먼저 트리란, 부모 자식 관계를 가지는 구조이다. 계층, 그룹 개념이 가능하다. (배열, 연결리스트, 스택, 큐 자료구조는 일직선 상의 구조이다.) * 트리의 종류 - 이진트리(binary tree) : 자식노드가 최대 2개까지만 붙는 구조. - 이진검색트리(binary search tree) : 현재 위치 노드의 왼쪽과 아래 노드는 현재 노드값보다 작아야 하고, 현재 위치 노드의 오른쪽과 위 노드는 현재 노드값보다 커야 하는 구조. -- 대표 balanced tree : red-black tree, AVL tree - 완전이진트리(complete binary tree) : 층(level)마다 왼쪽부터 채워진 구조. - Full Bi..
행렬 제곱 '분할정복'을 이용하여 n 이 홀수면, A^n = A * A^(n-1) n 이 짝수면, A^n = A^(n/2) * A^(n/2)
LIS(최장 증가 부분 수열) int LIS() { v.push_back(-1000000001); for (int i = 0; i v.back()) { v.push_back(arr[i]); cnt++; } else { deque ::iterator itr = lower_bound(v.begin(), v.end(), arr[i]); *itr = arr[i]; } } return cnt; } *주의 : 배열의 순서는 고려하지 않음
iterator 사용법 vector::iterator low = lower_bound(v.begin(), v.end(), tmp); *low = tmp;
분할 정복을 이용한 최대공약수 01. 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 02. 코드 #include using namespace std; int a, b, c; long long power(int n, int k) { if (k == 0) return 1; if (k == 1) return n; long long tmp = power(a, k / 2); if (k % 2) { return ((tmp * tmp)%c * a) % c; } return (tmp * tmp) % c; } int main() { cin >> a..
배열의 크기는 sizeof(배열이름)/sizeof(배열자료형) int arr[81]; cout
front(), top()는 큐와 스택의 size()가 존재하는 경우에만 사용 가능
char은 '', string은 ""

티스토리툴바