[BOJ] 백준 2512 예산 / 이분탐색

💭 문제 이해 국가예산이 주어지고, N개의 지방에서 예산 요청이 주어질 때 정해진 예산 내에서 최대 얼마까지 배정할 수 있는 지 계산하는 문제이다. 내용은 다르지만 큰 틀은 이전에 풀었던 이분탐색 문제들과 다를 바가 없다. 최소 예산인 1부터 최대 예산인 max(지방의 예산요청들) 사이에서 이분탐색을 하며 그 값을 찾아내면 된다. 구현 언어: Python import sys r = sys.stdin.readline def binary_search(requests: list, budget: int) -> int: result = 0 left = 1 right = max(requests) while left = mid else req for req in requests) if total_sum int: re..

→2021.02.11

[BOJ] 백준 1764 듣보잡 / 이분탐색

💭 문제 이해 제목이....ㅋ 암튼 전형적인 방법으로 풀면 이분탐색이지만, 파이썬의 장점을 잘 살리면 이분탐색보다 실행속도도 더 빠르고 간단하게 풀어낼 수 있다. 풀이 방법은 다음과 같다. 1. 이분탐색 2. Set 자료구조와 in 연산자 3. Set의 교집합을 구할 수 있는 & 연산자 4. Set과 intersection 메소드를 이용한 교집합 연산 실행속도는 4 > 3 >= 2 > 1 순으로 빠르다. 구현 언어: Python 1. 이분탐색 import sys r = sys.stdin.readline def binary_search(d_list: list, b_list: list) -> list: result = [] d_list.sort() for b in b_list: left = 0 right =..

→2021.02.11

[BOJ] 백준 10816 숫자 카드 2 / 이분탐색

💭 문제 이해 이전에 풀었던 숫자 카드 문제와 거의 비슷하다. 주어진 숫자 입력들이 상근이가 가진 숫자 카드에 있는지 여부를 체크하는 문제였다면, 이 문제는 상근이가 그 숫자들을 몇 개 가지고 있는 지도 체크해야 한다는 점이다. Python의 Counter를 이용해서 상근이의 숫자 카드를 Key 값으로 카드번호, Value 를 카드 개수로 하는 딕셔너리를 생성했다. 그리고 입력으로 들어온 숫자가 Counter 객체에 존재한다면 Value를 출력하고, 없다면 0을 출력하게 구현했다. 구현 언어: Python import sys from collections import Counter r = sys.stdin.readline answer = [] n, my_card = int(r()), Counter(map..

→2021.02.09

[BOJ] 백준 1654 랜선 자르기 / 이분탐색

💭 문제 이해 영식이가 가지고 있는 K개의 랜선을 N개 이상의 동일한 길이의 선들로 만들기 위해 자를 길이를 찾아야하는 문제이다. 랜선의 길이는 최대 231-1로 완전탐색을 하게 되면 시간초과가 발생하게 된다. 이분탐색을 통해서 무리 없이 해결할 수 있는 문제이다. 구현 언어: Python import sys from collections import Counter r = sys.stdin.readline def binary_search(target_cnt: int, lines: list) -> int: result = 0 left = 1 right = max(lines) while left

→2021.02.09

[BOJ] 백준 10815 숫자 카드 / 이분탐색

💭 문제 이해 사실 이분탐색 문제인데, set 자료구조를 사용해서 in 연산자를 쓰면 원소를 찾는데 O(1) 밖에 안걸린다는 점이 너무나 매력적이다. 구현도 엄청 간단하게 하면서 시간도 겁나 빠르다니... 그래서 이번에도 set과 in 연산자를 이용해서 풀었다:) 구현 언어: Python import sys r = sys.stdin.readline def solve(my_cards: set, num_list: list) -> list: result = [] for num in num_list: result.append(1 if num in my_cards else 0) return result n, my_cards = int(r()), set(map(int, r().split())) m, num_list..

→2021.02.09

[BOJ] 백준 2805 나무 자르기 / 이분탐색

💭 문제 이해 자를 수 있는 최소 높이인 1 부터 max(나무의 높이 배열) 사이에서 최소 m미터 길이의 나무를 가져가기 위해 이분탐색을 진행하며 m을 찾아나가는 문제이다. 자른 나무 길이의 합을 구하기 위해 최악의 경우 100만 번의 sum 연산이 log(109) 만큼 반복된다. 이 풀이도 시간 초과가 발생하지는 않지만 Counter를 사용해서 100만 번의 연산을 감소시켜 시간을 줄이는 풀이를 찾게 되었다. 구현 언어: Python 1. 내 풀이 import sys r = sys.stdin.readline def binary_search(m, trees): answer = 0 left = 1 right = max(trees) while left = mid else 0, trees)) if total_..

→2021.02.09

[BOJ] 백준 1920 수 찾기 / 이분탐색

💭 문제 이해 두 개의 정수 리스트 a, b가 주어지고, b의 모든 원소를 비교하며 a에 존재하는 지 여부를 1과 0으로 출력하는 문제이다. 문제 자체는 간단하지만 완전탐색을 수행하면 105 * 105 = 1010 으로 시간 초과가 발생하게 된다. 이 문제는 두 가지의 해결 방법이 있다. 1. 이분 탐색을 통해 리스트 b에서 원소를 탐색하는 시간을 log(n)으로 줄인다. 2. set()의 in 연산자는 O(1)의 시간이 걸린다는 특징을 이용하여 리스트 b를 set으로 입력받은 후, in 연산자로 탐색한다. https://twpower.github.io/120-python-in-operator-time-complexity 구현 언어: Python 1. Binary Search import sys r = ..

→2021.02.09