본문 바로가기

분류 전체보기132

백준 2805번 : 나무 자르기 문제 링크 : www.acmicpc.net/problem/2805 내 풀이(2021.1.17) : #include #include using namespace std; long long tree[1000000]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; long long M; cin >> N >> M; for (int i = 0; i > tree[i]; } int start = 0, mid, end = 1000000000; long long total_cnt = 0; while (start 0) total_cnt += cut; } if (total_cnt == M).. 2021. 1. 17.
백준 1920번 : 수 찾기 문제 링크 : www.acmicpc.net/problem/1920 내 풀이(2021.1.16) : #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; vector A; for (int i = 0; i > temp; A.push_back(temp); } sort(A.begin(), A.end()); int M; cin >> M; vector X; for (int i = 0; i > temp; X.push_bac.. 2021. 1. 16.
이분 탐색 개념 - 선형 탐색(순차 탐색)의 O(n)를 O(logn)으로 줄여줌 - sort 함수로 정렬을 먼저 시행한 후에, 이분 탐색 - sort()가 arr와 vec 둘 다 가능한 것처럼 binary_search(), lower_bound(), upper_bound() 모두 arr와 vec 둘 다 가능 - 아래와 같이 초기화했다고 가정하겠다. int arr[] = { 4, 12, 11, 10, 4, 2, 4, 5, 14, 1 }; int N = sizeof(arr) / sizeof(int); sort(arr, arr + N); - 정렬 후에의 원소 구성은 다음과 같다. 1 2 4 4 4 5 10 11 12 14 원소 1개를 찾을 때 1) 존재 유무를 찾을 때 cout 2021. 1. 16.
정렬의 종류 선택 정렬 www.youtube.com/watch?v=jpyslMwprao O(N^2) 삽입 정렬 www.youtube.com/watch?v=DRkL5EBZ7KY O(N^2) : 최선의 경우 O(N) 퀵 정렬 www.youtube.com/watch?v=EuJSDghD4z8 평균 O(NlogN) : 최악의 경우 O(N) 계수 정렬 www.youtube.com/watch?v=65Ui3RNibRA O(N+K) : K = 최대값 STL을 이용한 정렬에서는 최악의 경우에도 O(NlogN)이 나오도록 추가적인 로직이 더해져 있음 2021. 1. 15.

티스토리툴바