백준/이분탐색12

• 

  [백준 19637번 / C++] IF문 좀 대신 써줘 이분탐색을 이용한 문제이다~ #접근방법 이분탐색을 떠올려야 하는 단골 조건은 조건 범위가 10억을 넘길때이다. 뭐 아닌 문제도 있긴하겠지만 이분탐색을 이용해서 풀어야하는 문제는 대부분 10억 정도 되는 값을 조건으로 주어지기 때문에 해당 조건을 만났을 때 이분탐색을 의심해봐야한다. 이번 문제도 마찬가지다. 아래 조건을 보고 이분탐색을 고려해봐야한다. 칭호의 개수 N (1 ≤ N ≤ 10^5)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 10^5)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 10^5) 칭호의 개수가 100000 (10만) 이다. 그리고 캐릭터들의 개수 또한 100000 (10만) 이다. 그럼 여기서 생각을 해야할 것이 10만개의 캐릭터가 모두 상한값을 가지고 있다고.. 백준/이분탐색 2022. 4. 2.

• 

  [백준 3079번 / C++] 입국심사 이분탐색 문제이다. 해당 문제는 프로그래머스 입국심사 문제와 거의 똑같다고 보면된다. (사실, 그때 너무 열 받았던적이..) #접근방법 이분탐색에 대한 알고리즘을 모른다면 이분탐색 개념을 익히고 오는 것을 추천한다. 먼저 양쪽 끝 값을 설정해야 하는데 low와 high라는 변수를 둔다. 해당 변수들은 각각 제일 적게 걸리는 시간과 제일 오래 걸리는 시간을 초기화한다. 즉, low에는 0을 두고 high 에는 max.time[i] * m 을 둔다. high 초기화 값이 왜 저렇게 되는지 모를 수도 있는데 이게 무슨 말이냐면, 심사대 중 제일 시간이 오래 걸리는 심사대에 m명의 사람이 다 줄을 설수 있다. 그래서 최악의 상황에서 나올 수 있는 값을 high 값에다가 세팅 해주는 것이다. 이후 절반을 쪼개가면.. 백준/이분탐색 2022. 3. 22.

• [백준 2512번 / C++] 예산 이분 탐색을 이용하여 풀면 된다. 1. 벡터 V에 값을 저장 후 오름차순으로 정렬 2. high 값은 벡터의 제일 큰 원소의 값으로 저장 3. sum 변수에 mid값과 벡터의 원소의 값을 비교하여 작은값을 더함 4. sum값이 m보다 크거나 같으면 result 값에 mid 값 저장 후 이분 탐색 #include #include #include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector v; ll s, e; for (int i = 0; i > a; v.push_back(a.. 백준/이분탐색 2022. 2. 16.

• 

  [백준 1300번 / C++] K번째 수 이분 탐색 문제이다. 처음에 접근할 때 벡터를 생성하고 i*j 값을 push_back 해서 오름차순으로 정렬한다. k 위치에 해당하는 벡터의 원소를 출력한다. 이렇게 해선 안된다. N은 최대 10^5 이며 NxN 이기에 최악의 경우 100억의 벡터를 생성해야하는데 이러면 메모리 초과다. 그렇기 때문에 따로 벡터나 배열을 생성하지 않고 이분탐색으로만 확인하는 과정을 찾아보자. 1. low 에는 1 의 값을 저장하고 high 값에는 최악의 경우 10000000000(100억) 의 값을 저장한다. 2. 이차원 배열에는 i 행과 j 열이 있는데 각 원소는 i와 j의 곱의 결과가 저장되어있다. 현재 mid 값은 갱신되는 기준값이며 해당 기준값에서 i를 나눠준 몫이 j 값이다. 그렇기 때문에 i 행에서 mid값보다.. 백준/이분탐색 2022. 2. 16.

• 

  [백준 18113번 / C++] 그르다 김가놈 이분 탐색 문제이다. 접근 방식 1. 벡터 V에 꼬다리를 조건에 맞게 제거한 김밥 길이를 저장한다. - 김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 - 김밥 길이가 kcm이거나 그보다 짧으면 김밥 폐기 - 위의 조건에 해당되지 않으면 두쪽 꼬다리를 자름 2. p(mid) 의 최댓값을 구하기 위해서 low 값이 갱신될 때 result 값에 mid값을 넣어준다. 3. p의 값이 존재하지 않을 경우 - 1을 출력한다. #include #include using namespace std; typedef long long ll; int main() { //꼬다리 잘라낸 김밥 -> 손질된 김밥 //김밥 N개, kcm 잘라낸다 양쪽 균일하게 //김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 // 김밥 길이가 k.. 백준/이분탐색 2022. 2. 16.

• 

  [백준 15810번 / C++] 풍선 공장 이 문제를 처음 접할 때 바로 이분 탐색을 떠올려야한다. low는 0 으로 초기화를 하고 high 같은 경우엔 1,000,000,000,000으로 초기화한다 ( 스태프가 1명이고 풍선 하나를 만드는데 걸리는 시간이 1,000,000초가 걸릴 때 풍선 1000,000개를 만들 경우 ) 최소시간을 구하기 위해서 high 값을 갱신하면서 해당 조건문 블록에서 mid 값을 result 변수에 저장해준다. #include #include using namespace std; typedef long long ll; vector v; int main() { int n, m; cin >> n >> m; for (int i = 0; i > a; v.push_back(a); } .. 백준/이분탐색 2022. 2. 16.

• [백준 1072번 / C++] 게임 " 1 ~ INT_MAX " 범위에서의 이분탐색을 통해 result 값을 갱신. result 값과 Z값을 비교한 결과 result값이 크다면 high 위치를 mid-1 로 변경, 반대일 경우 low 위치를 mid+1로 변경. answer값이 0 그대로라면 0출력, answer값에 변화가 있었다면 answer값 출력. #include #include using namespace std; typedef long long ll; ll x, y, z; bool check(int mid) { ll X = mid + x; ll Y = mid + y; ll result = Y*100/X; if (result > z)return true; else return false; } int main() { cin >> x >.. 백준/이분탐색 2022. 1. 26.

• [백준 2776번 / C++] 암기왕 1. 수첩 1에 적혀있는 수들을 오름차순으로 정렬. 2. 이분탐색을 통해서 해당하는 값이 있으면 1 출력. 없으면 0 출력 * unordered_map 을 통해서도 이 문제를 해결할 수 있습니다. 자료구조 자료구조" data-og-description="*헤더로 을 갖는다. 은 key 와 value 의 쌍으로 이루어진 균형 이진 트리이다. key 를 기준으로 사전순으로 정렬되어 있기 때문에 검색 속도가 빠르다. 바로 map 의 쓰임을 baebalja.tistory.com #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; .. 백준/이분탐색 2022. 1. 26.

• 

  [백준 14627번 / C++] 파닭파닭 1. 범위가 "1 백준/이분탐색 2022. 1. 25.

• [백준 1561번 / C++] 놀이 공원 이분 탐색을 통해서 풀어야 할 문제다. 먼저 l과 h 에 최소로 들어갈 숫자 1과 최대로 들어가야할 숫자 60000000000을 저장한다. 즉, h에는 "놀이기구 하나에 운행시간 30 * 사람수의 최대" 가 들어가야한다. 내가 이렇게 초기화 안해서 아래 문제에서 매우 화가난적이 있어서 이제는 최대값이 몇인지를 계산부터 한다. 이 백준문제에서도 h값을 무작정 높은 숫자로 했다가 원하는 결과값이 안나올 수 있으니 초기화에 신경쓰자. [Level 3] 입국심사 (C++) 진짜 이 문제에 시간 엄청 많이 쏟아 부었다. 아무리봐도 이게 정답인데 계속 "6번 9번 테스트케이스"에서 오류가 났다. 너무 스트레스 받아서 시간 보니까 3시간이 지나있었다. 비쥬얼 스튜디오 baebalja.tistory.com 로직은 이렇.. 백준/이분탐색 2022. 1. 19.