본문 바로가기

Algorithm/Binary Search

 (47)
(C++) - 프로그래머스(Programmers) : 징검다리 답 https://programmers.co.kr/learn/courses/30/lessons/43236?language=cpp 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이분탐색 문제였습니다. 풀이방법 바위 사이의 거리를 mid로 생각해 해당 조건을 찾았을 때의 거리들의 max값을 찾는 이분탐색을 시행하였습니다. 1. mid보다 바위 사이의 거리가 작다면 제거해준다. removeCount값을 증가시킵니다. 2. 모든 바위를 제거했을때의 removeCount값이 n보다 크면 너무 많이 지웠으므로..
(C++) - 프로그래머스(Programmers) : 입국심사 답 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr answer가 될 수 있는 최대 범위를 잘 정해야하는 이분탐색 문제였습니다. 절반 테케에서 시간초과가 계속나 2시간 날렸습니다.^^ 시간초과가 자꾸 뜰 경우 : 자료형의 범위를 초과할 경우 시간초과로 처리하는 것 같습니다. 이거 때문에 이분탐색 로직을 계속 고민하여 시간을 쓸데없이 버렸습니다. 풀이방법 : 걸리는 시간을 찾아야 되는 값이라고 상정한 후 그에 대..
(C++) - 프로그래머스(Programmers) : 예산 답 https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그�� programmers.co.kr 상한액을 잘 배정해야되는 이분탐색 문제였습니다. 풀이방법 : 다음과 같이 두가지의 경우로 나누어 해결했습니다. 1. 상한액을 배정할 필요가 없는 경우 : 즉 총 예산 M보다 budgets에 담긴 전체 예산이 더 적을 경우엔 budgets들 중 가장 큰 값을 반환합니다. 저의 경우 이 부분이 없어 계속 틀렸습니다. 2. 상한액을 이분탐색을 통해 배정해야되는 경우 :..
(Text) - 백준(BOJ) 15641번 : SUPER SUPER BINARY SEARCH DELUXE 2.5 ~ https://www.acmicpc.net/problem/15641 15641번: SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2: T 1 이상 100 이하의 자연수를 출력한다. 단, 하나의 자연수만 정답이다. 정답은 맞은 사람이 나타날 때마다 바뀐다. 정답보다 작은 수를 출력하면 33% 부근에서 "틀렸습니다"를 받는다. 정답보다 큰 수를 출력하면 66% 부근에서 "틀렸습니다"를 받는다. www.acmicpc.net 1~100까지의 숫자를 이분탐색하며 제출합니다. 이분탐색 시간 복잡도가 O(logN)이므로 9번만에 답을 찾을 수 있습니다. 답은..
(C++) - 백준(BOJ) 1920번 : 수 찾기 답 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분탐색을 구현해보는 문제였습니다. 풀이방법 1. STL binary_search함수를 사용해 key값을 찾았다면 1을 아니라면 0을 출력하도록 합니다. 2. 직접 이분탐색을 구현하는 방법도 있습니다. * 입출력이 많으므로 c와 동기화를 풀어줘야 시간초과가 나지 않습니다. Code 1. STL 사용 #include #include #include #..
(C++) - 백준(BOJ) 13702번 : 이상한 술집 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 이분탐색(Binary Search)문제입니다. 개인적으로 변수 l은 1과 무척 헷갈리므로 대문자 L로 사용하심을 추천합니다. 저거 하나 때문에 뇌핏줄에 심각한 손상이 올 수 있습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, k를 입력받습니다. 각각 주전자 개수, 친구들의 수 입니다. 2. n만큼 loop를 돌며 주전자의 용량을 입력받습니다. 입력받을 때마다 a배열에 저장해줍니다. 그리고 big에..
(C++) - 백준(BOJ) 2805번 : 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색(Binary Search) 문제입니다. 풀이방법 1. 나무길이의 정보를 배열에 입력받고 오름차순으로 정렬합니다. 2. 찾으려는 절단기의 높이를 mid로 정해 이분탐색을 시행합니다. O(100만log100만)으로 시간제한에 걸리지 않습니다. 자른 나무들의 합이 m보다 작다면 다많이 잘라야하므로 절단기의 높이를 낮춰야합니다. 그 반대의 경우 절단기의 높..

티스토리툴바