티스토리

개발자 배씨

검색하기

블로그 홈

개발자 배씨

baebalja.tistory.com/m

배발자 님의 블로그입니다.

구독자: 45

방명록 방문하기

주요 글 목록

[백준 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만개의 캐릭터가 모두 상한값을 가지고 있다고.. 공감수 0 댓글수 0 2022. 4. 2.
[백준 3079번 / C++] 입국심사 이분탐색 문제이다. 해당 문제는 프로그래머스 입국심사 문제와 거의 똑같다고 보면된다. (사실, 그때 너무 열 받았던적이..) #접근방법 이분탐색에 대한 알고리즘을 모른다면 이분탐색 개념을 익히고 오는 것을 추천한다. 먼저 양쪽 끝 값을 설정해야 하는데 low와 high라는 변수를 둔다. 해당 변수들은 각각 제일 적게 걸리는 시간과 제일 오래 걸리는 시간을 초기화한다. 즉, low에는 0을 두고 high 에는 max.time[i] * m 을 둔다. high 초기화 값이 왜 저렇게 되는지 모를 수도 있는데 이게 무슨 말이냐면, 심사대 중 제일 시간이 오래 걸리는 심사대에 m명의 사람이 다 줄을 설수 있다. 그래서 최악의 상황에서 나올 수 있는 값을 high 값에다가 세팅 해주는 것이다. 이후 절반을 쪼개가면.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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값보다.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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); } .. 공감수 0 댓글수 0 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 >.. 공감수 0 댓글수 0 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; .. 공감수 0 댓글수 0 2022. 1. 26.
[백준 14627번 / C++] 파닭파닭 1. 범위가 "1 공감수 0 댓글수 0 2022. 1. 25.
[백준 1561번 / C++] 놀이 공원 이분 탐색을 통해서 풀어야 할 문제다. 먼저 l과 h 에 최소로 들어갈 숫자 1과 최대로 들어가야할 숫자 60000000000을 저장한다. 즉, h에는 "놀이기구 하나에 운행시간 30 * 사람수의 최대" 가 들어가야한다. 내가 이렇게 초기화 안해서 아래 문제에서 매우 화가난적이 있어서 이제는 최대값이 몇인지를 계산부터 한다. 이 백준문제에서도 h값을 무작정 높은 숫자로 했다가 원하는 결과값이 안나올 수 있으니 초기화에 신경쓰자. [Level 3] 입국심사 (C++) 진짜 이 문제에 시간 엄청 많이 쏟아 부었다. 아무리봐도 이게 정답인데 계속 "6번 9번 테스트케이스"에서 오류가 났다. 너무 스트레스 받아서 시간 보니까 3시간이 지나있었다. 비쥬얼 스튜디오 baebalja.tistory.com 로직은 이렇.. 공감수 0 댓글수 0 2022. 1. 19.
[백준 6236번 / C++] 용돈 관리 이분 탐색 문제이다. 어떤식으로 이분 탐색을 활용하는지 한번 살펴보자. 먼저 비교할 값을 이분탐색을 통해서 추출해낸다. 예를 들어 low 값과 high 값을 1과 100000값으로 정했으면 low와 high를 이용해 중간값을 구할 수 있다. 다음 그림을 한번 살펴보자. 즉, 첫 중간값은 50,000이 되고 두번째 중간값은 25,000 ... 이런식으로 계속 분할하다 보면 mid가 50일 때가 나올것이다. 이때를 한번 살펴보자 밑에 그림에서 현우가 날마다 사용하려고 하는 돈이 "10 40 30 10 50 10 40" 이라고 가정을 하자. 현재 mid 값인 50으로 현우가 날마다 사용하려고 정한 돈을 계속해서 빼주고 충당이 안된다면 다시 mid값을 초기화 시켜서 반복한다. mid값을 다시 초기화 시키는 작업.. 공감수 0 댓글수 0 2022. 1. 17.
[백준 2343번 / C++] 기타 레슨 [백준 6236번 / C++] 용돈 관리 이분 탐색 문제이다. 어떤식으로 이분 탐색을 활용하는지 한번 살펴보자. 먼저 비교할 값을 이분탐색을 통해서 추출해낸다. 예를 들어 low 값과 high 값을 1과 100000값으로 정했으면 low와 high를 이 baebalja.tistory.com 위의 문제와 거의 똑같은 문제다. 해당 링크 설명을 보고 한번 풀어보자. #include #include #include using namespace std; int l = 1; int h = INT_MAX; int n, m; vector v; bool check(int mid) { for (int i = 0; i mid)return 0; } int sum = 0; int cn.. 공감수 0 댓글수 0 2022. 1. 17.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.