- 1. 이분 검색
- 이분 검색은 정렬된 상태에서 사용 가능하다.
# ch4 - 1. 이분 검색
# 이분 검색은 정렬된 상태에서 사용 가능
n = 8
m = 32
arr = [23, 87, 65, 12, 57, 32, 99, 81]
lt = 0
rt = n-1
arr.sort()
while lt <= rt:
mid = (lt+rt)//2
if arr[mid] == m:
print(mid+1)
break
elif arr[mid] > m: # m 이 더 작은 경우 왼쪽으로
rt = mid-1
else: # m 이 더 큰 경우 오른쪽으로
lt = mid+1
# ch4 - 2. 랜선 자르기(결정 알고리즘)
k = 4 # 이미 있는 랜선 개수
n = 11 # 필요한 랜선 개수
lenList = [802, 743, 457, 539]
lt = 1
rt = max(lenList)
maxLen = 0
while lt <= rt:
mid = (lt+rt)//2
num = 0
for x in lenList:
num = num + x//mid
if num < n:
rt = mid-1
else:
maxLen = max(maxLen, mid)
lt = mid+1
print(maxLen)
# ch4 - 3. 뮤직비디오(결정 알고리즘)
n, m = 9, 3
info = [1, 2, 3, 4, 5, 6, 7, 8, 9]
maxx = max(info)
lt = 1
rt = sum(list(info))
res = rt
while lt <= rt:
mid = (lt+rt)//2
sum = 0
cnt = 1
for x in info:
if (sum + x) > mid:
cnt = cnt + 1
sum = x
else:
sum = sum + x
if mid >= maxx and cnt <= m:
# 반례 : 가장 긴 노래보다 용량이 커야한다
res = mid
rt = mid-1
else:
lt = mid+1
print(res)
# ch4 - 4. 마구간 정하기(결정 알고리즘)
n, c = 5, 3 # 마구간 개수, 말 마리수
listX = [1, 2, 8, 4, 9] # 1 2 4 8 9
listX.sort()
lt = listX[0]
rt = listX[n-1]
res = 0
while lt <= rt:
mid = (lt+rt)//2
cnt = 1
ep = listX[0]
for x in listX:
if (x-ep) >= mid:
# print(lt, rt, x)
cnt = cnt+1
ep = x
if cnt >= c:
res = mid
lt = mid + 1
else:
rt = mid-1
print(res)
- 5. 회의실 배정(그리디)
- list.sort(key=lambda x: (x[1]. x[0]))
# ch4 - 5. 회의실 배정(그리디)
# 그리디는 그 순간에 가장 좋은 방법을 선택 -> 대부분 정렬과 사용된다.
n = 5 # 회의 수
list = [[1,4],[2,3],[3,5],[4,6],[5,7]]
# 2차원 배열 정렬
# lambda x : 리스트의 원소를 x로 받고
# x[1], x[0]: 1번이 1순위, 0번이 2순위로 정렬
list.sort(key=lambda x: (x[1], x[0]))
endTime = 0
cnt = 0
for start, end in list:
if start >= endTime:
endTime=end
cnt = cnt+1
print(cnt)
# ch4 - 6. 씨름 선수(그리디)
# 키와 몸무게 중 적어도 하나는 크거나 무거운 지원자만 뽑기
# 키랑 몸무게가 둘다크면 탈락
n = 5
info = [[172,67],[183,65],[180,70],[170,72],[181,60]]
info.sort(reverse=True) # 첫번째원소 내림차순 정렬
largest = 0
cnt = 0
for h,w in info:
#print(h, w)
if w>largest: # 몸무게가 더 크면
print(h, w)
largest=w # 최대 몸무게
cnt = cnt + 1
# ch4 - 7. 창고 정리(그리디)
l = 10 # 창고 가로 길이
list = [69,42,68,76,40,87,14,65,76,81] # 상자 높이
m = 50 # 높이 조정 횟수
for idx in range(50):
list.sort()
list[0] = list[0] +1
list[-1] = list[-1] -1
list.sort()
print(list[-1]-list[0])
# ch4 - 8. 침몰하는 타이믹(그리디)
# 무게 제한이 m 일 경우에, 최소로 필요한 구명 보트 수 구하기
# n, m = 20, 120
#list = [68, 72, 30, 105, 55, 115, 36, 67, 119,
# 111, 95, 24, 25, 80, 55, 85, 75, 83, 21, 81]
n, m = 5, 140
list = [90,50,70,100,60]
list.sort()
print(list)
cnt = 0
while list:
if len(list) == 1:
cnt = cnt + 1
if list[0]+list[-1] > m:
list.pop()
cnt = cnt + 1
else:
list.pop(0)
list.pop()
cnt = cnt + 1
print(cnt)
# ch4 - 9. 증가수열 만들기(그리디)
list = [3, 2, 10, 1, 5, 4, 7, 8, 9, 6]
new = []
listRear = 0
while list:
# 둘다 큰 경우 - 작은 것 부터 먼저 넣기
if list[0] > listRear and list[-1] > listRear:
if list[0] < list[-1]: # rt가 큰 경우
new.append('L')
listRear = list[0]
list.pop(0)
elif list[0] > list[-1]: # lt 가 큰 경우
new.append('R')
listRear = list[-1]
list.pop()
else: # lt == rt 종료
break
# 왼쪽만 큰 경우
elif list[0] > listRear:
new.append('L')
listRear = list[0]
list.pop(0)
# 오른쪽만 큰 경우
elif list[-1] > listRear:
new.append('R')
listRear = list[-1]
list.pop()
else: # lt == rt 종료
break
print(new)
- 10. 역수열(그리디) - 복습
- 역수열이 주어지면, 원래 수열 구하기
# ch4 - 10. 역수열(그리디)
n = 8
list = [5,3,4,0,2,1,1,0]
list.insert(0,0)
new = [0]*len(list)
for i in range(1,n+1):
for j in range(n):
if list[i]==0 and new[j]==0:
new[j]=i
break
elif new[j]==0:
list[i] = list[i] -1
print(new)