알고리즘
-
스택 응용, 백준 9935: 문자열 폭발알고리즘 2024. 3. 5. 11:47
#include #include #include using namespace std; int main(int argc, const char * argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); stack stack; string str, bomb; cin >> str >> bomb; int strSize = str.size(); int bombSize = bomb.size(); char bombEnd = bomb[bombSize - 1]; for (int i = 0; i < strSize; i++) { char c = str[i]; stack.push(c); if ( c == bombEnd ) { if( stack.size() < bombSize ) cont..
-
이분탐색 3 - LIS (Longest Increasing Subsequence), 백준 12105알고리즘 2024. 3. 2. 21:28
#include using namespace std; int main(int argc, const char * argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int arr[n]; int now = 0; cin >> arr[0]; for (int i = 1; i > num; if (num > arr[now]) { now++; arr[now] = num; } else { int start = 0, end = now, mid = 0; int result = 0; while (start = num ) { result = mid; end = mid - 1; } else { start = ..
-
이진탐색 2 - Parametric Search, 백준 1654알고리즘 2024. 3. 2. 17:49
#include using namespace std; int main(int argc, const char * argv[]) { cin.tie(NULL); ios::sync_with_stdio(false); int k, n; cin >> k >> n; int lines[k]; long start = 1, end = 0, mid = 0; for (int i = 0; i > lines[i]; if (end < lines[i]) { end = lines[i]; } } while (start = n) { start = mid + 1; } else { end = mid - 1; } } cout
-
이분 탐색(binary search)알고리즘 2024. 2. 25. 21:48
int search(int *arr, int n, int size) { int start = 0, end = size - 1; int now; while (start n){ end = now - 1; } else { start = now + 1; } } return 0; } 게임 만들다 까먹은 게 많아서 코딩 연습 문제를 풀고 있습니다. 그런데 이분 탐색 while문 내부 구현을 까먹어서 나중에 헷갈리지 안도록 기록용으로 남겨둡니다. 시작, 중간, 끝 조건: 시작 지점이 끝 지점 "이하" c++의 sort 시간 복잡도는 O(nlog(n)), 이분탐색의 시간복잡도는 O(log(n)) 정렬이 안된 배열이라 하면 (n+1)log(n)이니 그냥 O(nlog(n))이라 보면 됩니다.