Algorithm/이분탐색3 [프로그래머스] 입국심사 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238 KEY 시간을 기준으로 이분탐색한다는 방법 자체를 떠올리기가 어려운 문제다. 1분~가장 오래 걸리는 시간 까지 이분탐색으로 시간을 탐색하면서, 모든 사람이 심사를 받을 수 있는 시간 중 가장 짧은 시간대를 찾으면 된다. 시간을 심사대의 시간으로 나누어 더함으로써 완료할 수 있는 사람 수(cnt)를 센다. 가령 심사대는 7, 10분 두개가 있고, 지금 시간이 30분이라고 할 때, 완료할 수 있는 사람 수는 30/7 + 30/10 = 6이다. 자료형에 조심하자. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 2023. 4. 6. [백준] 1920 수찾기 c++ 문제 링크 https://www.acmicpc.net/problem/1920 KEY 이중for문을 돌려서 일일이 확인하는 작업은 100,000 * 100,000 O(N^2)으로 시간초과가 발생한다. 따라서 O(logN)의 시간복잡도를 갖는 이분탐색과 map, ordered_map을 활용하여 풀이할 수 있다. unordered_map: HashTable로 구현된 자료구조. 탐색 시 O(1)의 시간복잡도 map: 이진탐색트리로 구현된 자료구조. 탐색 시 O(logN)의 시간복잡도. map의 경우 자동으로 정렬되므로(Red Black Tree의 특징) 삽입/삭제가 빈번할 경우 성능이 저하되는 특징이 있다. 따라서 이 문제와 같은 경우 최대 100,000번 불필요한 정렬을 할 수 있으므로, unordered_m.. 2023. 3. 31. [백준] 1654 랜선 자르기 c++ 가장 긴 랜선을 기준으로 1부터 가장 긴 랜선 길이를 탐색하면서 갯수가 k이상이 되게 하는 값 중 최댓값을 구하는 문제이다. 주의할 점은, 완전탐색을 할 경우 1,000,000 *10,000의 시간복잡도가 나오기 때문에 1부터 가장 긴 랜선의 길이를 탐색할 때, 이진탐색을 이용해야 한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include #include #include using namespace std; int n, k; vector v; long long answer; //갯수 합산하는 함수 int ch.. 2023. 2. 25. 이전 1 다음
