[4]알고리즘스터디 - 섹션4_2주차 스터디

파이썬 알고리즘 문제풀이 스터디

알까기 _ 섹션 4

문제 1 - 이분검색

n, m = map(int,input().split())
arr = list(map(int,input().split()))

arr.sort()
lt , rt = 0, n-1

while lt <= rt :
    mid = (lt+rt) // 2 
    if arr[mid] > m : # 큰 부분 자르기
        rt = mid -1 
    elif arr[mid] == m :
        print(mid+1)
        break
    else : # 작은 부분 자르기 
        lt = mid +1 

문제 2 - 랜선자르기

k, n = map(int,input().split())
Line = []
largest = 0
for i in range(k) :
    tmp = int(input())
    Line.append(tmp)
    largest = max(largest, tmp)

def isalright(mid):
    cnt = 0
    for v in Line :
        cnt += (v // mid)
    return cnt  # 랜선의 개수 반환 

lt , rt = 1, largest # 포인터가 아닌 값 자체 
ans = 0
while lt <= rt :
    mid = (lt+rt) // 2 
    if isalright(mid) >= n : # 원하는 개수보다 크거나 같을 경우 
        ans = max(ans,mid) # 자동으로 이전값보다 좋은 값이기에 이렇게 안해도 괜찮음 
        lt = mid +1  # 길이를 늘리기위해 lt를 이동 
    else :  # 길이가 너무 길어서 원하는 개수보다 작을 경우 
        rt = mid -1 

print(ans)

문제 3 - 뮤직 비디오

n, m = map(int,input().split())
Music= list(map(int,input().split()))

lt , rt = 1, sum(Music) # 포인터가 아닌 값 자체
ans = 0
maxx = max(Music)
def isCount(capacity): # DVD 몇장이 필요한지 반환 
    cnt = 1
    sum = 0
    for x in Music :
        if sum + x > capacity :  # 노래를 넣는데 넘쳤다.
            cnt+=1 
            sum = x # 넣어서 넘친 노래를 처음에 넣는다. 
        else : #  넘치지않아 저장할 수 있다. 
            sum += x
    return cnt 


while lt <= rt :
    mid = (lt+rt) // 2 
    if mid> maxx and isCount(mid) <= m :  # DVD 용량은 가장 긴 노래를 담을 수  있도록 만들어져야함 
        ans = mid 
        rt = mid -1 # 큰 쪽을 버리기  
    else :  
        lt = mid +1 

print(ans)

문제 4 - 마구간 정하기

n, c = map(int,input().split())
arr = []
for _ in range(n) :
    arr.append(int(input()))

arr.sort()
lt , rt = 1, arr[-1] # 마구간 
ans = 0

def Count(len): # 배치한 말의 개수 반환 
    cnt = 1 # 첫번째 말 배치 
    ep =arr[0]  # 첫번째 마구간에 배치  # end Point
    for i in range(1,n) : # 첫번째 마구간에 놓았으므로 1부터 시작 
        if arr[i]-ep >= len :
            cnt+=1  # 말 배치
            ep =arr[i]
    return cnt 


while lt <= rt :
    mid = (lt+rt) // 2 
    if Count(mid) >= c : 
        ans = mid 
        lt = mid +1  
    else :  
        rt = mid -1 

print(ans)

[그리디]

그리디는 sort와 함께 간다.

문제 5 - 회의실 배정

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

meeting.sort(key = lambda x : (x[1],x[0]))
cnt = 0
endTime = 0 # endTime을 밖에 두면 된다. 
for s,e in meeting :
    if s>=endTime : 
        endTime = e
        cnt += 1

print(cnt)

• 그리디는 정렬과 함께 간다.
• lambda 함수
• 회의가 끝나는 기준으로 정렬

문제 6 - 씨름 선수

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

height.sort(reverse=True) # 내림차순으로 

largest = 0
cnt = 0
for h,w in height: 
    if largest < w :
        largest = w
        cnt +=1 
print(cnt)

• 키 순으로 정렬하여 체중으로 갱신된 횟수를 count한다.

문제 7 - 창고 정리

l = int(input())
block = list(map(int,input().split()))
m = int(input())

for i in range(m) :
    block.sort()
    block[0]+=1
    block[l-1] -=1 
block.sort()
print(block[l-1] - block[0])

• 정렬은 그리디의 친구!

문제 8 - 침몰하는 타이타닉

from collections import deque
n,m = map(int,input().split())
weight = list(map(int,input().split()))
weight.sort()

weight = deque(weight) # 자료구조 덱 이용 
cnt = 0
while weight :
    if len(weight) == 1: # 혼자 남았을 경우 
        cnt +=1
        break
    if weight[0]+weight[-1] <= m :
        cnt+=1 
        weight.popleft()
        weight.pop() # 인수를 넣지않으면 마지막 원소 
    else:
        cnt+=1 
        weight.pop()
print(cnt)

• deque 이용
• 혼자 남았을 경우 생각해주기

문제 9 - 증가수열 만들기

n = int(input())
arr = list(map(int,input().split()))

lt,rt = 0, n-1
last = 0 # 증가수열의 마지막 값 
res = ""
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 : 
        res = res + tmp[0][1]
        last = tmp[0][0]
        if tmp[0][1] == 'L' :
            lt +=1 
        else :
            rt -= 1
    tmp.clear()
print(len(res))
print(res)

문제 10 - 역수열

• <내가 푼 풀이>

n = int(input())
arr = list(map(int,input().split()))
ans = \[0\]\*(n)  
for i in range(n) :  
tmp = 0  
for j in range(n) :  
if tmp == arr\[i\] and ans\[j\]==0 : # 넣을려고 하는 ans가 0인지를 고려해야한다!!  
ans\[j\] = i+1  
break  
if ans\[j\] == 0 : tmp +=1  
for val in ans :  
print(val , end= ' ')

• <강사님의 풀이>

n = int(input()) arr = list(map(int,input().split()))`
ans = \[0\]\*(n)  
for i in range(n) :  
for j in range(n) :  
if 0 == arr\[i\] and ans\[j\]==0 :# 빈자리 확보 & 앞자리도 확보  
ans\[j\] = i+1  
break  
elif ans\[j\] == 0 : # 빈자리 한개 확보  
arr\[i\] -= 1  
for val in ans :  
print(val , end= ' ')

• tmp를 추가시켜 비교하도록 생각했는데 강사님은 arr의 해당 값을 감소 시키도록 푸셨다.