심화 과정 13 일차

1. 자료구조 및 알고리즘 13일차 수강하기

 

 -  이진 탐색

 

2. 새롭게 알게된 지식

 - 원하는 수를 특정 범위내에서 빠르게 찾을때 이진 탐색이 유용하다.

 

과제 1 : 두 수의 합 2 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

 

 - 접근 : 

 

 투포인터로 문제 해결

 

 - 코드 구현 : 

 

 

 

과제 2 : 2D 행렬 검색 2 https://leetcode.com/problems/search-a-2d-matrix-ii/

 

 - 접근 : 

 

 오름차순의 조건을 이용해서 빠르게 구하는 문제

 특별한 로직이 생각나지 않아 브루트포스로 해결

 

 - 코드 구현 : 

 

 

과제 3: 예산 https://www.acmicpc.net/problem/2512

2512번: 예산

 

 - 접근 : 

 

 이진탐색으로 해결

 

 - 코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
    
    def determination(self, nums, target, mid):
        res = 0
        for n in nums:
                res += min(n, mid)
        return res <= target

    def answer(self):
        n = int(self.input())
        nums = [int(i) for i in self.input().split()]
        target = int(self.input())
        left, right, ans = 0, max(nums), 0
        
        while left <= right:
            mid = (left + right) // 2
            if self.determination(nums, target, mid):
                ans = mid
                left = mid + 1
                continue

            right = mid - 1

        self.output(f'{ans}\n')

s = Solution()
s.answer()

 

 

과제 4: 나무 자르기 https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

 - 접근 : 

 

 이진 탐색으로 해결

 

 - 코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write

    def determination(self, trees, m, h):
        res = 0
        for x in trees:
            if x > h:
                res += x - h
        return res >= m

    def answer(self):
        n, m = map(int, self.input().split())
        trees = [int(i) for i in self.input().split()]

        left, right, ans = 0, 2000000000, 0

        while left <= right:
            mid = (left + right) // 2
            
            if self.determination(trees, m, mid):
                #자를 수 있는 나무 길이 중 최소가 될때까지 실행
                ans = mid
                left = mid + 1
                continue
            
            right = mid - 1

        self.output(f'{ans}\n')
                
s = Solution()
s.answer()

 

 

과제 5 : 랜선 자르기 https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 -접근 : 

 

 이진 탐색으로 해결

 

 - 코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
    
    def determination(self, nums, target, mid):
        res = 0
        for n in nums:
                res += min(n, mid)
        return res <= target

    def answer(self):
        n = int(self.input())
        nums = [int(i) for i in self.input().split()]
        target = int(self.input())
        left, right, ans = 0, max(nums), 0
        
        while left <= right:
            mid = (left + right) // 2
            if self.determination(nums, target, mid):
                ans = mid
                left = mid + 1
                continue

            right = mid - 1

        self.output(f'{ans}\n')

s = Solution()
s.answer()