[파알문] 4. 이분탐색 & 그리디

Nam_JU·2023년 8월 7일

Algorithm

목록 보기

17/20

2023.08.07

4-1. 이분 검색 - 이분탐색

내코드

"""
이분 검색
8 32
23 87 65 12 57 32 99 81
"""
n, m = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
print(arr.index(m)+1)

정답코드

"""
이분 검색
8 32
23 87 65 12 57 32 99 81
"""
n, m = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
lt = 0
rt = len(arr)-1

while lt<=rt: #중요!
    mid = (lt+rt)// 2
    if arr[mid]==m:
        print(mid+1)
        break
    elif arr[mid]<m:
        lt=mid+1
    else:
        rt=mid-1

4-2. 랜선 자르기

📌 파이썬 리스트 컨프리헨션

"""
4 11
802
743
457
539
"""
# 입력방식 1 - for문 [802, 743, 457, 539]
arr = []
for _ in range(k):
    s = int(input())
    arr.append(s)
# 입력방식 2 - 리스트 컨프리 헨션 [802, 743, 457, 539]
array = [int(input()) for _ in range(k)]
# 입력방식 3 - 리스트 컨프리 헨션 헷갈린 코드 [[802], [743], [457], [539]]
arr2 = [list(map(int, input().split())) for _ in range(4)]

정답코드

"""
4 11
802
743
457
539
"""

def Count(len):
    cnt=0
    for x in arr: #전체 랜선 갯수 구하기
        cnt+=(x//len)
    return cnt

k, n = map(int, input().split())
arr = [int(input()) for _ in range(k)]
arr.sort(reverse=True)

lt=1
rt=arr[0]

while lt<=rt:
    mid = (lt+rt)//2
    if Count(mid)>=n:
        answer=mid
        lt=mid+1 #랜선의 최대길이를 구해야함으로 lt를 늘린다
    else:
        rt=mid-1

print(answer)

4-3. 뮤직 비디오

문제이해가 어려웠음...
주어진 리스트가 곡당 시간길이이고 여기서 각 DVD에 들어갈 적정 시간을 찾아 최소의 시간을 찾는 문제

"""
뮤직비디오
9 9
1 2 3 4 5 6 7 8 9
"""

def Count(capacity):
    cnt=1
    sum=0 #곡 누적 시간
    for x in music:
    	#곡 누적 시간 추가여부확인 
        if sum+x>capacity:
            cnt+=1
            sum=x
        else:
            sum+=x
    return cnt

n, m = map(int, input().split())
music = list(map(int, input().split()))
maxx = max(music)
lt=1
rt=sum(music)
answer=0
while lt<=rt:
    mid=(lt+rt)//2
    if mid>=maxx and Count(mid)<=m:
        answer=mid
        rt=mid-1
    else:
        lt=mid+1
print(answer)

4-4. 마구간 정하기

"""
5 3
1
2
8
4
9
"""
def Count(len):
    cnt=1
    ep=cage[0] #첫번째 마굿간에 말 배치
    for x in range(1, n):
         # 현재 내가 배치하려는 지점 - 마지막에 말을 배치한 지점
        if cage[x]-ep>=len:
            cnt+=1
            ep=cage[x]
    return cnt #배치한 말의 마릿수

n, c= map(int, input().split())
cage = [int(input()) for _ in range(n)]
cage.sort()
lt=1
rt = cage[-1]
res=0
while lt<=rt:
    mid=(lt+rt)//2 #가장 가까운 두 말의 거리
    if Count(mid)>=c:
        res=mid
        lt=mid+1
    else:
        rt=mid-1
print(res)

4-5. 회의실 배정 - 그리디

비슷한 문제를 푼적 있는데 튜플생성, 정렬까진 괜찮아도
그 다음의 조건을 항상 못만들었던 기억이 있음...
해당 문제는

최대한 많은 회의가 생성되어야함

그러기 위해서는 끝나는 회의시간을 기준으로 잡아야한다

현재 끝나는 시간 <= 다음 회의시작시간

"""
5
1 4
2 3
3 5
4 6
5 7
"""

# [[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]]
n = int(input())
arr = [list(map(int, input().split()))for _ in range(n)]

# 어떤 기준으로 정렬을 해야할까? [[2, 3], [1, 4], [3, 5], [4, 6], [5, 7]]
arr.sort(key=lambda v:v[1])

next=0
answer=0
for start, end in arr:
    if start>=next: #다음 시작시간 >= 현재 끝나는 시간 (최초값은 0임으로 자동 시작)
        next=end
        answer+=1
print(answer)

4-6. 씨름 선수

몸무게를 기준으로 최댓값 갱신일때 카운트하기

"""
5
172 67
183 65
180 70
170 72
181 60
"""

n = int(input())
people = [list(map(int, input().split())) for _ in range(n)]

#키 내림차순 정렬
people.sort( key=lambda v:-v[0]) #[[183, 65], [181, 60], [180, 70], [172, 67], [170, 72]]

answer=0
maxw = -2147000000
for height,weight in people:
    if weight > maxw:
        maxw = weight
        answer+=1
print(answer)

2023.08.08

4-7. 창고정리

sort()하는 부분을 for문 가장 위에 두었다가 답이 아니라서 당황함. 값을 변경후 -> 정렬 하는 순서로 가야지 마지막 정렬하는 부분에서 잘리지 않고 끝남

"""
10
69 42 68 76 40 87 14 65 76 81
50
"""

l = int(input())
arr = list(map(int, input().split()))
m = int(input())
arr.sort()
for _ in range(m):
    #arr.sort()
    arr[0]+=1
    arr[-1]-=1
    arr.sort()
print(arr[-1]-arr[0])

4-8. 침몰하는 타이타닉

내코드
몸무게가 넘었을경우 그 차례가 짤리지 않고 카운트 하는법을 생각하는데 시간이 걸림

"""
5 140
90 50 70 100 60
"""
n, m = map(int, input().split())
people = list(map(int, input().split()))
people.sort()
print(people)
sumw = 0
answer=0
for x in people:
    if sumw+x>m:
        answer+=1
        sumw=x
    else:
        sumw+=x
if sumw!=0:
    answer+=1
print(answer)

정답

"""
5 140
90 50 70 100 60
"""
from collections import deque
n, m = map(int, input().split())
people = list(map(int, input().split()))
people.sort()
people=deque(people)
answer=0
while people:
    if len(people)==1:
        answer+=1
        break
    if people[0]+ people[-1]>m:
        people.pop()
        answer+=1
    else:
        people.popleft()
        people.pop()
        answer+=1
print(answer)

4-9. 증가수열 만들기

삽질..

n = int(input())
arr = list(map(int, input().split()))
str_res = ""
answer=[]

lt=0
rt=len(arr)-1


if arr[lt]<arr[rt]:
    answer.append(arr[lt])
    str_res+="L"
    lt+=1
else:
    answer.append(arr[rt])
    str_res+="R"
    rt-=1

while lt<rt:
    if arr[lt] < arr[rt] and answer[-1]< arr[lt]:
        answer.append(arr[lt])
        str_res += "L"
        lt += 1
    if arr[lt] > arr[rt] and answer[-1]<arr[rt]:
        answer.append(arr[rt])
        str_res += "R"
        rt -= 1
print(len(answer))
print(answer)
print(str_res)

정답코드

"""
5
2 4 5 1 3
"""

n = int(input())
arr = list(map(int, input().split()))
str_res = ""
answer=[]

lt=0
rt=len(arr)-1
last = 0
answer = ""
tmp = []

while lt<=rt:
    if arr[lt]>last:
        tmp.append((arr[lt], 'L'))
    if arr[rt]>last:
        tmp.append((arr[rt], 'R'))
    # 비교할필요 없이 오름차순으로 크기 정렬
    tmp.sort()
    if len(tmp)==0:
        break
    else:
        answer=answer+tmp[0][1] #가장 작은 인덱스의 value값 저장
        last=tmp[0][0] #가장 작은 인덱스의 key값 저장
        if tmp[0][1]=='L':
            lt+=1
        else:
            rt-=1
    tmp.clear()

print(len(answer)) #문자열 크기가 정답 갯수
print(answer)

4-10. 역수열

역수열의 특성을 생각하지 못하고 코드를 짰다가 오류가 나서 이해를 못했음

"""
8
5 3 4 0 2 1 1 0
"""

n = int(input())
arr = list(map(int, input().split()))
answer = [0]*n

for i in range(n):
    for j in range(n):
        # 0자리 확보,빈자리인지 확인
        if arr[i]==0 and answer[j]==0:
            answer[j]=i+1
            break
        elif answer[j]==0: # 내 앞공간의 0을 찾아서 위치 파악
            arr[i]-=1

print(' '.join(map(str, answer)))