๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
SW์‚ฌ๊ด€ํ•™๊ต ์ •๊ธ€/๊ฐœ๋ฐœ์ผ์ง€ - TIL

[Week02] ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์ด๋ถ„ํƒ์ƒ‰

by young-ji 2022. 4. 9.

[Week02] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ‚ค์›Œ๋“œ - ์ด๋ถ„ํƒ์ƒ‰, ๋ถ„ํ• ์ •๋ณต, ์Šคํƒ, ํ, ์šฐ์„ ์ˆœ์œ„ ํ

๊ฒ€์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์„ ํ˜•ํƒ์ƒ‰ / ์ด๋ถ„ ํƒ์ƒ‰

์ด๋ถ„ํƒ์ƒ‰

์ •๋ ฌ์ด ๋˜์–ด์žˆ๋Š” ๋ฐฐ์—ด์—์„œ ํŠน์ • ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด์„œ ๋ชจ๋“  ๋ฐ์ดํ„ฐ๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ํ™•์ธํ•˜๋Š” ๋Œ€์‹  ํƒ์ƒ‰์˜ ๋ฒ”์œ„๋ฅผ ์ ˆ๋ฐ˜์œผ๋กœ ์ค„์—ฌ๋‚˜๊ฐ€๋Š” ํƒ์ƒ‰ ๋ฐฉ๋ฒ•

 

์ด๋ถ„ํƒ์ƒ‰ ์‚ฌ์šฉ์‹œ ์ฃผ์˜์‚ฌํ•ญ

  1. ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์€ ์ •๋ ฌ๋˜์–ด์žˆ์–ด์•ผํ•œ๋‹ค.
  2. ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์ง€์ง€์•Š๊ฒŒ mid๊ฐ’์„ ์ž˜ ์ง€์ •ํ•ด์ค€๋‹ค

์ฐจ๋ก€๋กœ ์ฆ๊ฐ€(ํ˜น์€ ๊ฐ์†Œ)์‹œํ‚ค๋ฉด์„œ ํ’€์–ด์•ผํ•˜๋Š” ํƒ์ƒ‰๋ฌธ์ œ์— ํฐ ์ˆ˜์˜ ๋ฒ”์œ„๊ฐ€ ์ฃผ์–ด์ง„๋‹ค๋ฉด ์ด๋ถ„ํƒ์ƒ‰์„ ๋– ์˜ฌ๋ ค๋ณด์ž.

์‹œ๊ฐ„๋ณต์žก๋„ O(logN)

 

โœ… ์ด๋ถ„ํƒ์ƒ‰ ๊ตฌํ˜„ํ•˜๊ธฐ

while๋ฌธ์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„

def binary_serch(a,n_list) :
    st = 0
    en = n-1
    while st <= en :
        mid = (en+st)//2
        if n_list[mid] == a :
            return True
        elif n_list[mid] > a :
            en = mid -1
        else :
            st = mid + 1
    return False

 

โœ… ์ด๋ถ„ํƒ์ƒ‰ ๋ชจ๋“ˆ - bisect

  • bisect_left(alist, x) : ์ •๋ ฌ๋œ list์— x๋ฅผ ์‚ฝ์ž…ํ•  ์œ„์น˜๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค. x๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ x์˜ ์ธ๋ฑ์Šค๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.
  • bisect_right(alist, x) : ์ •๋ ฌ list์— x๋ฅผ ์‚ฝ์ž…ํ•  ์œ„์น˜๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค. x๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ ์˜ค๋ฅธ์ชฝ ์ธ๋ฑ์Šค๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค. 
from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
target = 4

print(bisect_left(a, target))     # 2
print(bisect_right(a, target))    # 4

์ด๋ถ„ํƒ์ƒ‰

import bisect
def binary_search(array, target):
    index = bisect.bisect_left(array, target)
    if index < len(array) and array[index] == target:
        return index
    #index๊ฐ€ len(array)์™€ ๊ฐ™๊ฑฐ๋‚˜ 0์ผ ๊ฒฝ์šฐ ํ•ด๋‹น list์— target์ด ์—†๋‹ค. 
    return False

 

๋ชจ๋“ˆ์„ ์ด์šฉํ•˜์—ฌ ์ค‘๋ณต์ด ์žˆ์„ ๊ฒฝ์šฐ ๋ฒ”์œ„๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹คโ• 

 

โœ… ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜

์ตœ์ ํ™” ๋ฌธ์ œ๋ฅผ ๊ฒฐ์ •๋ฌธ์ œ๋กœ ๋ฐ”๊พธ์–ด ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ๋ฒ•

๋ฌธ์ œ์˜ ์ƒํ™ฉ์„ ๋งŒ์กฑํ•˜๋Š” ํŠน์ • ๋ณ€์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’, ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ๊ฒฐ์ •๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋ฉด์„œ ํƒ์ƒ‰ ๋ฒ”์œ„๋ฅผ ์ขํ˜€๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. 

 

#๋ฐฑ์ค€2805

์ ๋‹นํ•œ ๊ธธ์ด๋ฅผ ์ฐพ์„๋•Œ๊นŒ์ง€ ๊ธธ์ด๋ฅผ ๋ฐ˜๋ณตํ•ด์„œ ์กฐ์ ˆํ•œ๋‹ค. ๊ทธ ํ›„ 'ํ˜„์žฌ ํฌ๊ธฐ๋ฉด ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š”๊ฐ€'๋ฅผ ํ™•์ธํ•œ ๋’ค ๋งŒ์กฑ ์—ฌ๋ถ€์— ๋”ฐ๋ผ ๋ฒ”์œ„๋ฅผ ์ขํ˜€๊ฐ„๋‹ค.

import sys

n,m = map(int,sys.stdin.readline().split())
trees = list(map(int,sys.stdin.readline().split()))

trees.sort()

#start,end ๋ณ€์ˆ˜๋ฅผ ์ธ๋ฑ์Šค๊ฐ’์ด ์•„๋‹Œ ๋ฐ์ดํ„ฐ ๊ฐ’์„ ๋‹ด๋Š”๋‹ค. 
start = 1
end = max(trees)

#target์ด ์ฃผ์–ด์ง€์ง€์•Š๊ณ  ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๋ชฉ์ ์ด๊ธฐ๋•Œ๋ฌธ์— mid๋ณ€์ˆ˜๋ฅผ ์ด์šฉํ•˜๋Š” ํ˜•ํƒœ
while start <= end :
    mid = (start+end)//2
    sum0 = [tree-mid if tree > mid else 0 for tree in trees]
    sum_value = sum(sum0)
    if sum_value >= m :
        start = mid + 1
    else : 
        end = mid - 1

print(end)

 

ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜ ์œ ํ˜•์˜ ๋ฌธ์ œ ๊ทผ๊ฑฐ

1. ๊ฒฐ์ • ๋ฌธ์ œ๋ฅผ ์ •์˜ ํ–ˆ์„ ๋•Œ, ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ

2. ๊ฐ€๋Šฅํ•œ ํ•ด์˜ ์˜์—ญ์ด ์—ฐ์†์ ์ด์—ฌ์•ผ ํ•œ๋‹ค. (๊ฐ์†Œํ•จ์ˆ˜์ด๊ฑฐ๋‚˜ ์ฆ๊ฐ€ํ•จ์ˆ˜์—ฌ์•ผํ•œ๋‹ค.)

 

 

์—ด์ฝ”ํ•˜์„ธ์šฉ ๐Ÿน 

๋Œ“๊ธ€