자세한 설명은 아래 포스트를 참고하기
masso.tistory.com/80?category=891816
1. 부품 찾기
: 다른 input 만드느라 애 좀 먹었다..ㅠㅜ
1-0. input & output
N, M = 5, 3
store, client = [8, 3, 7, 9, 2], [5, 7, 9]
N, M = 50, 20
store = [73,15,26,59,49,44,8,47,63,74,66,81,67,41,52,45,57,4,51,12,10,37,64,7,48,23,42,18,71,55,36,61,83,82,2,20,94,76,28,58,50,92,79,70,96,19,54,97,40,86]
client = [4,35,20,53,93,6,63,52,21,41,5,77,91,78,79,7,46,39,64,95]
N, M = 60, 60
store = [911,643,184,439,855,981,950,776,519,204,321,47,749,53,851,272,970,270,42,137,523,251,990,171,487,860,796,19,841,46,799,215,333,766,214,709,687,299,334,554,991,396,163,473,869,76,549,128,821,756,703,463,60,283,706,81,314,415,517,375]
client = [500,923,351,303,489,294,579,708,287,382,137,906,229,788,332,251,862,486,795,638,932,725,573,541,329,177,324,868,710,277,290,909,948,364,87,727,652,497,977,618,532,258,949,632,687,29,735,580,617,770,70,946,569,743,189,388,322,636,61,200]
1-1. 정렬한 후 이진 탐색 binary Search
'''=== way1. binary search ==='''
def binary_search(target, start, end, arr):
if start > end:
return False
mid = (start + end) // 2
if arr[mid] == target:
return True
elif target < arr[mid]:
return binary_search(target, start, mid-1, arr)
else:
return binary_search(target, mid+1, end, arr)
start_time = timeit.default_timer()
store = sorted(store)
for target in client:
if binary_search(target, 0, N-1, store):
print("yes", end = ' ')
else:
print("no", end = ' ')
print()
end_time = timeit.default_timer()
print(">> binary_search time: ", end_time - start_time)
1-2. set의 성질 이용하기
'''=== way2. set() ==='''
set_store = set(store)
start_time = timeit.default_timer()
for target in client:
if target in set_store:
print("yes", end = ' ')
else:
print("no", end = ' ')
end_time = timeit.default_timer()
1-3. 계수 정렬(생략)
2. 떡볶이 떡 만들기
: 손님이 원하는 길이에 딱 맞는 최대 높이를 찾을 수 없다면,
손님이 원하는 길이보다 더 많이 주는 높이 중에서 최댓값을 반환해야한다!! (아래 input 2,3 참고)
2-0. input
'''절단기에 설정할 수 있는 높이의 최댓값: 872
>> sequential_search time: 0.0007, >> recursive_binary_search time: 0.0003, >> while_binary_search time: 0.0003
'''
N, M = 200, 1357
rice_cakes = [273, 20, 157, 49, 24, 224, 175, 193, 169, 153, 141, 297, 258, 287, 268, 154, 211, 185, 113, 294, 129, 117, 242, 91,
122, 106, 215, 292, 271, 188, 56, 167, 256, 63, 172, 206, 213, 51, 249, 146, 54, 124, 97, 198, 264, 200, 197, 156, 209,
13, 252, 62, 152, 236, 27, 207, 160, 277, 10, 176, 241, 223, 46, 274, 205, 262, 22, 291, 293, 132, 11, 253, 41, 283,
199, 110, 126, 36, 71, 105, 220, 87, 231, 31, 171, 128, 263, 270, 30, 95, 281, 183, 155, 260, 216, 135, 44, 257, 276,
104, 254, 279, 217, 12, 299, 55, 149, 138, 58, 125, 246, 266, 66, 201, 75, 85, 57, 77, 229, 101, 133, 21, 35, 161, 240,
286, 131, 290, 99, 130, 88, 184, 261, 247, 83, 151, 84, 238, 81, 221, 267, 265, 89, 173, 123, 245, 79, 26, 102, 225,
278, 219, 186, 144, 68, 166, 180, 120, 162, 118, 52, 25, 139, 45, 50, 43, 163, 17, 86, 255, 168, 140, 181, 28, 96, 53,
112, 233, 109, 70, 237, 196, 248, 80, 232, 159, 111, 100, 275, 194, 78, 251, 272, 295, 76, 94, 289, 174, 47, 202]
'''절단기에 설정할 수 있는 높이의 최댓값: 240
>> sequential_search time: 0.0011, >> recursive_binary_search time: 0.0005, >> while_binary_search time: 0.0006
'''
2-1. 순차 탐색 sequential Search
'''sequential_search'''
def sequential_search(arr):
max_H = max(arr)
while max_H > 0:
total = 0
for ele in arr:
if ele > max_H:
total += ele - max_H
if total >= M:
print("절단기에 설정할 수 있는 높이의 최댓값: ", max_H)
break;
max_H -= 1
'''%% 입력의 범위가 최대 10억까지의 정수이므로 시간 초과를 받는다.'''
start_time = timeit.default_timer()
sequential_search(rice_cakes)
end_time = timeit.default_timer()
print(">> sequential_search time: ", format(end_time - start_time, ".4f"))
2-2. 이진 탐색 binary Search
'''binary_search'''
def binary_search(ans, arr, minH, maxH):
global result
if minH > maxH:
return -1
midH = (minH + maxH) // 2
total = 0
for ele in arr:
if ele > midH:
total += ele - midH
if total >= ans:
result = midH
return binary_search(ans, arr, midH+1, maxH)
elif total < ans:
return binary_search(ans, arr, minH, midH-1)
start_time = timeit.default_timer()
result = 0
binary_search(M, rice_cakes, 0, max(rice_cakes))
print("절단기에 설정할 수 있는 높이의 최댓값: ", result)
end_time = timeit.default_timer()
print(">> recursive_binary_search time: ", format(end_time - start_time, ".4f"))