[Week02] ์๊ณ ๋ฆฌ์ฆ ํค์๋ - ์ด๋ถํ์, ๋ถํ ์ ๋ณต, ์คํ, ํ, ์ฐ์ ์์ ํ
๊ฒ์ ์๊ณ ๋ฆฌ์ฆ - ์ ํํ์ / ์ด๋ถ ํ์
์ด๋ถํ์
์ ๋ ฌ์ด ๋์ด์๋ ๋ฐฐ์ด์์ ํน์ ๋ฐ์ดํฐ๋ฅผ ์ฐพ๊ธฐ ์ํด์ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ์์ฐจ์ ์ผ๋ก ํ์ธํ๋ ๋์ ํ์์ ๋ฒ์๋ฅผ ์ ๋ฐ์ผ๋ก ์ค์ฌ๋๊ฐ๋ ํ์ ๋ฐฉ๋ฒ
์ด๋ถํ์ ์ฌ์ฉ์ ์ฃผ์์ฌํญ
- ์ฃผ์ด์ง ๋ฐฐ์ด์ ์ ๋ ฌ๋์ด์์ด์ผํ๋ค.
- ๋ฌดํ ๋ฃจํ์ ๋น ์ง์ง์๊ฒ 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
๋ชจ๋์ ์ด์ฉํ์ฌ ์ค๋ณต์ด ์์ ๊ฒฝ์ฐ ๋ฒ์๋ฅผ ๊ตฌํ ์ ์๋คโ
โ ํ๋ผ๋ฉํธ๋ฆญ ์์น
์ต์ ํ ๋ฌธ์ ๋ฅผ ๊ฒฐ์ ๋ฌธ์ ๋ก ๋ฐ๊พธ์ด ํด๊ฒฐํ๋ ๊ธฐ๋ฒ
๋ฌธ์ ์ ์ํฉ์ ๋ง์กฑํ๋ ํน์ ๋ณ์์ ์ต์๊ฐ, ์ต๋๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ๋ฅผ ์ด๋ถํ์์ผ๋ก ๊ฒฐ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ฉด์ ํ์ ๋ฒ์๋ฅผ ์ขํ๊ฐ ์ ์๋ค.
์ ๋นํ ๊ธธ์ด๋ฅผ ์ฐพ์๋๊น์ง ๊ธธ์ด๋ฅผ ๋ฐ๋ณตํด์ ์กฐ์ ํ๋ค. ๊ทธ ํ 'ํ์ฌ ํฌ๊ธฐ๋ฉด ์กฐ๊ฑด์ ๋ง์กฑํ๋๊ฐ'๋ฅผ ํ์ธํ ๋ค ๋ง์กฑ ์ฌ๋ถ์ ๋ฐ๋ผ ๋ฒ์๋ฅผ ์ขํ๊ฐ๋ค.
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. ๊ฐ๋ฅํ ํด์ ์์ญ์ด ์ฐ์์ ์ด์ฌ์ผ ํ๋ค. (๊ฐ์ํจ์์ด๊ฑฐ๋ ์ฆ๊ฐํจ์์ฌ์ผํ๋ค.)
์ด์ฝํ์ธ์ฉ ๐น
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week03] ์๊ณ ๋ฆฌ์ฆ - DFS / BFS ๋ฐฑ์ค ๋ฌธ์ (5) | 2022.04.21 |
---|---|
[Week03] ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋ (3) | 2022.04.20 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week01] ์๊ณ ๋ฆฌ์ฆ - ์ ๋ ฌ01 (0) | 2022.04.09 |
[Week01] ์๊ณ ๋ฆฌ์ฆ - ์ฌ๊ทํจ์ (0) | 2022.04.07 |
๋๊ธ