목록이분탐색 (6)

Little Jay

[C++] 백준 2512번 - 예산

이진탐색을 활용하는 문제 생각보다 이진탐색할때 조건을 설정하는 부분이 어려웠다 #include #include #include using namespace std; long long arr[10001]; int main() { int n, sum = 0; cin >> n; for (int i = 0; i > arr[i]; sum += arr[i]; } int budget; cin >> budget; sort(arr, arr + n); long long low = 0; long long high = arr[n - 1]; if (sum
알고리즘/BOJ 2021. 9. 2. 16:19
[C++] 백준 1764번 - 듣보잡

마지막에 조건으로 이름을 사전순으로 출력해야 되는것을 제대로 못보고 왜 틀렸는지 하루종일 보고 있었다..... 일단 맵이나 해쉬로 풀지 않았다. 이거 같은 경우는 그냥 벡터를 계속 정렬해주면서 binary_search로 빠르게 이름을 찾으면 되는 문제인 것 같다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v(n); v.resize(n); string s; for (int i = 0; i > v[i]; } sort(v.begin(), v.end()); vector ..
알고리즘/BOJ 2021. 8. 17. 15:42
[C++] 백준 1620 - 나는야 포켓몬 마스터 이다솜

hash_table로 풀려고 했지만 채점서버에서 내 코드를 읽지 못해서 vector의 pair기능을 활용해서 다시 풀었다 이것 때문에 많이 문제를 채점해서 좀 그렇다 vector을 두개 사용했는데, 첫 번째 벡터는 바로 번호만 넣으면 출력이 되도록하는 도감으로 만들었고, 두 번째 벡터는 pair을 사용해서 이름과 번호를 같이 넣어서 sort해준 다음 이름순으로 정렬해서 이분탐색하여 찾았다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v1(n + 1); vector v2; v1.push_back(..
알고리즘/BOJ 2021. 8. 17. 15:34
[C++] 백준 13777번 - Hunt The Rabbit

저번 글을 보면 내가 이분탐색(이진탐색)에 약하다는 것을 깨달았다. solved.ac 에서 binary search 태그를 검색해서 내가 풀 수 있는 문제들을 풀어보는 것을 목표로 삼았다. 클래스 점수도 빨리 올려야 되는데 언제올리냐..... 이 문제는 영어 문제이다. 간단히 핵심만 해석하자면, 이분 탐색을 할 때마다 mid 값이 바뀌게 되는데 그 값을 출력해주면 되는 문제이다. 이분 탐색은 아래의 블로그를 참조했다. 아직 알고리즘에서 걸어야 할 길이 먼거같다...... https://blockdmask.tistory.com/167 [탐색] 이진탐색 (Binary Search) 구현 방법 안녕하세요. BlockDMask 입니다. 알고리즘 코딩 사이트(백준 온라인 저지)에서 '수 찾기' 문제를 풀다가 이진..
알고리즘/BOJ 2021. 8. 8. 16:10
[C++] 백준 1654번 - 랜선 자르기(retry needed)

처음으로 이분 탐색을 써본 문제. 이분 탐색을 처음 써보는 거라 많이 어색하기도 하고, 구현을 어떻게 해야하는지 감이 잘 안와서 여러 블로그를 보고 조금 터득했다. 이분 탐색 문제를 더 풀어봐야 감이 올 것 같다. 이 문제도 내 힘으로 푼 것이 아니라 나중에 한번 더 풀어봐야겠다. #include #include #include using namespace std; #define MAX 10000 int n, m; long long int line_arr[MAX]; bool isPossible(long long line) { int count = 0; for (int i = 0; i = m) return tr..
알고리즘/BOJ 2021. 8. 8. 15:47
[C++] 백준 1920 수 찾기

처음에 시간 초과가 떠서 봤더니 ios_base::sync_with_stdio(0); cin.tie(0); 이거 두개 안해서 틀렸었다. 항상 시간 초과가 나면 킹받는다. 이분(이진)탐색 즉, Binary Search를 이용하는 문제이다 자료구조를 배우긴 했지만 Binary Search를 배우지는 않아서 algorithm 헤더에 있는 binary_search 메소드를 사용했다 이 부분 구현은 혼자 따로 해봐야 겠다 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, x; cin >> n; vector v; for (int i = 0; i < n; i++) {..
알고리즘/BOJ 2021. 7. 18. 16:25
Prev 1 Next