|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#Binary Search Implementation
import sys
inp = list(map(int,sys.stdin.readline().rstrip().split()))
arr = []
for i in range(len(inp)):
arr.append((inp[i],i)) #(원래원소, index)
t = int(input())
arr.sort(key=lambda x:x[0])
def binary_search(arr,st,ed,target):
if st==ed:
if arr[st][0]==target:
return arr[st][1]
else:
return -1
mid = (st + ed) // 2
if target < arr[mid][0]:
return binary_search(arr,st,mid-1,target)
elif target > arr[mid][0]:
return binary_search(arr,mid+1,ed,target)
else:
return arr[mid][1]
ln = len(arr)-1
result = binary_search(arr,0,ln,t) + 1
if result == -1:
print("N/A")
else:
print(result)
|
cs |
|
1
2
3
4
|
#Input
1 10 2 9 3 8 7 4 6 5 2
4
|
cs |
|
1
2
3
|
#Output
8
|
cs |
<(1)부품 찾기>
import sys
n = int(input())
shop = list(map(int,sys.stdin.readline().rstrip().split()))
m = int(input())
customer = list(map(int,sys.stdin.readline().rstrip().split()))
min_ = min(shop)
max_ = max(shop)
count = [0]*(max_-min_+1)
for i in shop:
count[i-min_] += 1
for i in customer:
if count[i-min_]>0:
print('yes',end=' ')
else:
print('no',end=' ')
<(2)떡볶이 떡 만들기> #Parametric Search
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import sys
n, k = map(int, input().split())
ls = list(map(int,sys.stdin.readline().rstrip().split()))
start = min(ls)
end = max(ls)
result = 0
while start<=end:
mid = (start + end) // 2
sum_ = 0
for i in ls:
if i > mid :
sum_ += i - mid
if k>sum_:
end = mid-1
else:
result = mid
start = mid + 1
break
print(result)
|
cs |
<(3)정렬된 배열에서 특정 수의 개수 구하기>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import sys
n,x = map(int,input().split()) #n은 원소개수, x는 특정수
arr = list(map(int,sys.stdin.readline().rstrip().split()))
def count_x(arr,x):
#일단 특정수 하나 찾기
start = 0
end = len(arr)-1
target = -1
while start <= end:
mid = (start + end) // 2
if arr[mid] > x:
end = mid - 1
elif arr[mid] < x:
start = mid + 1
else:
target = mid
break
if target == -1:
return target
#특정수 하나의 index를 이용해서 좌측 끝과 우측 끝의 index찾기
#좌측 index
start = 0
left_idx = target
end = left_idx
while start <= end:
mid = (start + end) // 2
if arr[mid] < x: #이건 범위 벗어날 걱정 X(mid<=left_idx)
start = mid + 1
else: #arr[mid]==x
if mid>0:
if arr[mid-1] != x: #좌측 index 발견
left_idx = mid
break
else:
end = mid -1
left_idx = end
else:
left_idx = mid
break
#우측 index
start = target
right_idx = target
end = len(arr)-1
while start <= end:
mid = (start + end) // 2
if arr[mid] > x: #이건 범위 벗어날 걱정 X(mid<=left_idx)
end = mid - 1
else: #arr[mid]==x
if mid<len(arr)-1:
if arr[mid+1] != x: #좌측 index 발견
right_idx = mid
break
else:
start = mid + 1
right_idx = start
else:
right_idx = mid
break
return right_idx - left_idx + 1
print(count_x(arr,x))
|
cs |
'프로그래밍 > 이코테python' 카테고리의 다른 글
| 이코테 Ch.8 Dynamic Programming 문제 풀이 (0) | 2022.09.02 |
|---|---|
| 이코테 Ch.6 Sorting 문제 풀이 (0) | 2022.08.29 |
| 이코테 Ch.5 DFS/BFS 문제 풀이 (0) | 2022.08.27 |
| 이코테 Ch.4 Implementation 문제 풀이 (0) | 2022.08.26 |
| 무지의 먹방 라이브 (2019 카카오 블라인드 공채 Level4) (0) | 2022.08.20 |