728x90
반응형

Algorithm/Binary Search 10

[백준 2512 / Python / 실버2] 예산

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다. import sysinput = sys.stdin.readline"""1. 모든 요청을 줄 수 있다면 다 준다2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다"""N = int(input())reqs = list(map(int, input().split()))budget = int(input())def calc(limit, arr): """ 상한가를 고려해, 지급해야 할 금액 계산 limit: 상한가 ..

[프로그래머스 / python / Level 2] 순위 검색

2021 KAKAO BLIND RECRUITMENT 출제 문제이다. Level 2이긴 한데 왜 2인지 전혀 모르겠고, 내가 느끼기엔 최소 Level 3이고 백준으로 치면 골드 4이상이 아닌가 싶다. 그냥 개인적 느낌이다. 단순 이분탐색만 사용되는 것이 아니라 해시, 조합, 문자열 파싱 등 다양한 알고리즘이 활용되고 구현요소도 많아서 실수할 부분이 매우 많고 복잡하다. 카카오 문제는 다 이런 거 같다. 하나의 알고리즘만 보는 게 아닌 이런저런 알고리즘을 조합하여 구현처럼 만들어내는 것.. 특히 초보자들에겐 더욱 어려운 것 같다. 나에게도 어렵고. from collections import defaultdictfrom itertools import productimport bisectdef solution(..

[프로그래머스 / python / Level 3] 주사위 고르기

2024 KAKAO WINTER INTERNSHIP 3번 문제이다. 아주 어려운 문제였다. 알고리즘 분류도 애매하다. 완전탐색, 조합, 구현, 이분탐색 정도일까?여러 가지 알고리즘이 복합적으로 쓰이고, 완전탐색 -> 이분탐색 아이디어를 떠올리기도 쉽지 않은 문제였다.개인적으로 Level 3 중에서 가장 어려운 편 아닌가 싶고, 3번 문제로 나온 건 난이도 조절 실패인 것 같다(개인적 의견).백준으로 치면 골드 1 정도 될 거 같은 느낌. from itertools import combinations, productdef binary_search(arr, target): """ 이분 탐색 정렬된 점수 합 리스트를 받아, target보다 작은 요소의 개수를 반환합니다. """ ..

[Baekjoon 1654 / Python / 실버2] 랜선 자르기

이분 탐색 문제이다. 늘 결과 도출 부분에서 묘하게 헷갈린다. # 실버2 -> 이분 탐색"""K : 이미 가지고 있는 랜선의 개수N : 만들어야 할 랜선의 개수data[] : K개 랜선 리스트start : 1 -> 랜선 최소 길이end : max(data) -> 랜선 최대 길이- 랜선 길이를 기준으로 이분 탐색 실시- 반복할 때 마다 조건 검사    -> 해당 길이로 N개 랜선 제작이 가능한지    -> 모든 랜선을 일일이 길이로 나눠 총 랜선 개수 세기- 최대값을 찾아야 하므로 end 출력"""import sysinput = sys.stdin.readlineK, N = map(int, input().split())data = [int(input()) for _ in range(K)]start = 1en..

[Baekjoon 3079 / Python / 골드5] 입국심사

이분 탐색 문제이다. 일반적인 이분 탐색의 틀에서 크게 벗어나지 않는다.다만 start와 end의 초기 설정 및 mid값의 유효성을 어떻게 판단할지에 대해서 고민이 좀 필요했다.  # 이분 탐색import sysinput = sys.stdin.readlineN, M = map(int, input().split())test = [int(input()) for _ in range(N)]# 이분 탐색def binarySearch():    start = min(test)    end = max(test) * M    result = end    while start end:        mid = (start + end) // 2        total = 0        # 임의의 시간(mid) 동안 몇명..

[Baekjoon 2110 / Python / 골드4] 공유기 설치

import sysinput = sys.stdin.readline# 집, 공유기 개수N, C = map(int, input().split())house = [int(input()) for _ in range(N)]  # 집 좌표house.sort() # 집을 순서대로 정렬# 이분 탐색으로 인접 공유기 간의 최소 거리를 찾는다def binarySearch():    end = house[-1] - house[0] # 최대 거리    if C == 2:        return end    start = 1 # 최소 거리    result = 0 # 결과를 저장할 변수    # 최적의 거리를 찾을 때까지 반복한다    while start end:        cur = house[0] # 마지막으로 공유..

[Baekjoon 2805 / python / 실버2] 나무 자르기

import sys n, m = map(int, sys.stdin.readline().split()) # 나무의 수 / 요구 벌목량 tree = list(map(int, sys.stdin.readline().split())) # 나무 리스트 tree.sort(reverse=True) # 내림차순 정렬 (큰 나무부터) result = 0 # 이분 탐색으로 적절한 "높이"를 탐색한다 start = 1 # 최소 높이 end = max(tree) # 최대 높이 while start while문이 끝나면, 반드시 start가 end보다 1 크다 mid = (start + end) // 2 cutTree = 0 for i in tree: # 높이(mid)를 설정하고 일일이 벌목을 해본다 if i > mid: # 나..

[Baekjoon/JAVA] 백준 10815번 숫자 카드

주어지는 숫자의 범위가 매우 크기 때문에, 일일이 비교하는 방법보다는 이분 탐색 알고리즘을 이용해야 합니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st; int n = Integer.parseInt(br.readLine()); int cards[] = new int[n]; st = new StringTok..

728x90
반응형