|
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
63
64
65
66
67
68
69
70
71
72
73
|
# 이진 탐색 소스코드 구현(반복문)
def binary_search(array,target, start, end):
while start <= end:
mid =(start+end) //2
if array[mid] == target:
return mid
elif array[mid]> target:
end = mid -1
else :
start = mid +1
return None
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백을 기준으로 구분하여 입력
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
result = binary_search(array, i, 0, n - 1)
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')
# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001
# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split()))
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')
|
cs |
|
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
|
# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))
# 이진 탐색을 위한 시작점과 끝점 설정
start =0
end = max(array)
# 이진 탐색 수행(반복적)
result = 0
while(start<=end):
total =0
mid = (start+end)//2
for x in array:
# 잘랐을 때의 떡의 양 계산
if x > mid:
total += x- mid
# 떡의 양이 부족한 경우 더많이 자르기(왼쪽 부분 탐색)
if total < m:
emd = mid -1
# 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
else :
result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid +1
|
cs |
'알고리즘 문제 > 자료구조&알고리즘' 카테고리의 다른 글
| 다이나믹 프로그래밍 (0) | 2020.10.22 |
|---|---|
| 다이나믹 프로그래밍 (0) | 2020.10.22 |
| 이진 탐색 (0) | 2020.10.22 |
| 정렬 예제 (0) | 2020.10.22 |
| 정렬 (0) | 2020.10.21 |