Algorithm/Binary Search (47) 썸네일형 리스트형 (C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 순위 검색 programmers.co.kr/learn/courses/30/lessons/72412?language=cpp (C++) - 백준(BOJ) 3020번 : 개똥벌레 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이분 탐색 문제였습니다. 풀이방법 1. 석순이나 종유석의 서순은 중요하지 않습니다. 높이에 따라 부서질지 아닐지만 확인하면 되기 때문에 정렬해도 문제였습니다. 석순과 종유석에 대한 입력을 두개의 vector 변수에 나눠 담고 오름차순으로 sort해줍니다. 2. 구역을 1부터 시작해 height까지 loop를 돌며 최소의 장애물 파괴 수를 구합니다. 석순의 경우 선택한 구역(i) 이상의 높이를 가진 인덱스를 구해줍니.. (C++) - 백준(BOJ) 3078번 : 좋은 친구 www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 1. map 자료구조 m을 선언합니다. key엔 이름길이, value는 해당 이름길이를 가진 학생들의 등수들이 담긴 vector입니다. 2. m의 크기만큼 loop를 돕니다. 매 이름 길이마다 좋은 친구의 순서쌍을 변수 ans에 더해줍니다. 현재 index에서 k만큼 더한 v[i] + k를 초과하는 등수를 가진 친구가 처음나오는 index를 찾습니다. 찾게 된.. (C++) - 백준(BOJ) 6236번 : 용돈 관리 www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이분탐색 문제였습니다. 문제 지문에 오해의 소지가 있어 푸는데 애먹었습니다.. 풀이방법 * k원을 인출했다면 해당 돈이 부족해질 때까지 다음날에도 그 다음 날에도 계속해서 쓸 수 있습니다. 돈이 부족해졌다면 기존에 있는 돈은 넣고 다시 k원을 인출하므로 k원이 됩니다. 1. 인출할 돈을 최소로 하기위해 0원부터 0x3f3f3f3f까지 이분탐색을 위해 범위를 정합니다. 2. 매번 mid마다 체크함수를 실행해줍니다. 모.. (C++) - 백준(BOJ) 7795번 : 먹을 것인가 먹힐 것인가 www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net lower_bound를 구현해보는 혹은 사용해보는 문제였습니다. 풀이방법 1. a,b를 오름차순으로 정렬합니다. 2. 모든 a의 원소들에 대해서 이분탐색을 시행합니다. a의 원소가 b의 원소 이하가 되는 index 지점을 찾게 된다면 해당 index지점까지 생명체 a는 b생명체를 먹을 수 있습니다. 이를 다르게 표현하자면 a의 원소값의 lower_bound 지.. (C++) - 백준(BOJ) 2776번 : 암기왕 답 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 입출력이 많기 때문에 c의 헤드들과 동기화를 끊어줘야 합니다. 그 후 이분탐색하시면 됩니다. 풀이방법 찾았다면 flag = 1로 만들어주고 찾기 못했다면 flag가 초기값 그대로인 0이므로 이분탐색 시행 후 flag를 return 해주면 됩니다. Code #include #define fastio ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); using namesp.. (C++) - 백준(BOJ) 1756번 : 피자 굽기 답 www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net 이분탐색 구현방법을 생각해야하는 문제였습니다. 풀이방법 1. 이분탐색은 정렬이 되었을 때 할 수 있기 때문에 구불구불한 오븐을 정리해야합니다. 위에서 봤을 때 오븐의 중간층은 넓어도 그 위의 층들이 중간층보다 좁을 때 중간층이 튀어나온 부분을 확인할 수 없습니다. 여기서 착안해서 오븐을 위에서 봤을 때 위층부터 너비의 내림차순으로 오븐 너비를 수정할 수 있습니다. 2. 이분탐색 시행 : 이전에 놓았던 오븐의 너비 보다 .. (C++) - 백준(BOJ) 2428번 : 표절 답 www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 * 모든 파일이 크기가 1억으로 동일할 경우 파일의 개수가 10만개라면 pair의 개수가 int범위를 초과할 수 있으니 long long형으로 답과 함수 자료형을 선언했습니다. 1. 입력 file값을 오름차순으로 정렬합니다. 2. 현재 index를 가장 큰 값으로 가정, 0 ~ index - 1까지 파일사이즈가 .. 이전 1 2 3 4 5 6 다음
