코딩테스트 4. 이분 탐색(결정알고리즘) & 그리디 알고리즘

1. 이분 검색

n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
lt=0
rt=n-1
while lt<=rt:
    mid=(lt+rt)//2
    if a[mid]==m:
        print(mid+1)
        break
    elif a[mid]>m:
        rt=mid-1
    else:
        lt=mid+1

 

2. 랜선자르기

def Count(len):
    cnt=0
    for x in Line:
        cnt+=(x//len)
    return cnt

k, n=map(int, input().split())
Line=[]
res=0
largest=0
for i in range(k):
    tmp=int(input())
    Line.append(tmp)
    largest=max(largest, tmp)
lt=1
rt=largest
while lt<=rt:
    mid=(lt+rt)//2
    if Count(mid)>=n:
        lt=mid+1
        res=mid
    else:
        rt=mid-1
print(res)

 

3. 뮤직비디오

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)
res=0
while lt<=rt:
    mid=(lt+rt)//2
    if mid>=maxx and Count(mid)<=m:
        res=mid
        rt=mid-1
    else:
        lt=mid+1
print(res)

 

4. 마구간 정하기

def Count(len):
    cnt=1
    ep=Line[0] ## end point
    for i in range(1, n):
        if Line[i]-ep>=len:
            cnt+=1
            ep==Line[i]
    return cnt
n, c=map(int, input().split())
Line=list(int(input()) for _ in range(n))
Line.sort()
lt=Line[0]
rt=Line[n-1]
while lt<=rt:
    mid=(lt+rt)//2
    if Count(mid)>=c:
        res=mid
        lt=mid+1
    else:
        rt=mid-1
print(res)

 

5. 회의실 배정

## 선생님 풀이
## 그 단계에서 제일 좋은 것을 차례차례 선택해 나가는 것. 
## 정렬과 동반되어서 문제 풀이 진행 됨.

## 회의가 끝나는 시간을 기준으로 정렬 해야함.
n=int(input())
meeting=[]
for i in range(n):
    s, e=map(int, input().split())
    meeting.append((s, e)) ## 튜플 형태로 
meeting.sort(key=lambda x: (x[1], x[0])) # x[1]을 기준으로 정렬
et=0 #end time
cnt=0
for s, e in meeting:
    if s>=et:
        et=e
        cnt+=1
print(cnt)

 

6.  씨름선수

## 선생님 풀이
## 키로 정렬 
## 맨 위의 사람은 키 이겼으니 체크
## 두번재 사람은 자기보다 키큰 사람보다 몸무게 이겨야함.
## 세번째 사람은 자기보다 키큰 사람보다 몸무게 이겨야함
## 이중 for문 은 비효율적임. 키는 정렬했으니까 버리고 
## 몸무게만 최대값 구하듯이 보면 됨.

n=int(input())
body=[]
for i in range(n):
    a, b=map(int, input().split())
    body.append((a, b))
body.sort(reverse=True) #내림차순
largest=0
cnt=0
for x, y in body:
    if y>largest:
        largest=y
        cnt+=1
print(cnt)

 

7. 창고 정리

## 선생님풀이
L=int(input())
a=list(map(int, input().split()))
m=int(input())
a.sort()
for _ in range(m):
    a[0]+=1
    a[L-1]-=1
    a.sort()
print(a[L-1]-a[0])

 

8. 침몰하는 타이타닉

## 가장 먼저 제일 높은 사람이랑 낮은 사람이랑 짝지어보고 무거우면 무거운 사람 만 pop
## 다시 두번째로 무거운 사람이랑 첫번째 가벼운 사람이랑 짝지어보기

# n, limit=map(int, input().split())
# p=list(map(int, input().split()))
# p.sort()
# cnt=0
# while p:
#     if len(p)==1:
#         cnt+=1
#         break
#     if p[0]+p[-1]>limit:
#         p.pop() #보트타고 탈출
#         cnt+=1
#     else:
#         p.pop(0)
#         p.pop()
#         cnt+=1
# print(cnt)

## 데크형으로 풀기
from collections import deque
n, limit=map(int, input().split())
p=list(map(int, input().split()))
p.sort()
p=deque(p)
cnt=0
while p:
    if len(p)==1:
        cnt+=1
        break
    if p[0]+p[-1]>limit:
        p.pop() #보트타고 탈출
        cnt+=1
    else:
        p.popleft()
        p.pop()
        cnt+=1
print(cnt)

 

9. 증가수열 만들기

# 수열의 마지막 항을 기억해야함. 라스트보다는 커야함.
# lt rt 값을 가져오고 정렬해서 작은 값을 가져와야함. 
# last 값보다는 큰 값으로 가져와야 함. 정렬해서 가져옴.
n=int(input())
a=list(map(int, input().split()))
lt=0
rt=n-1
last=0 
res="" # 문자열 초기화
tmp=[] # 빈 리스트
while lt<=rt:
    if a[lt]>last:
        tmp.append((a[lt], 'L')) # 튜플값으로 삽입
    if a[rt]>last:
        tmp.append((a[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. 역수열

## 선생님 풀이
# seq list [0]*n
# 0의 개수를 count 해서 그 다음 자리에 들어가기
# 빈공간을 세서 그 다음 칸에 들어가야함.
# 이미 들어간 숫자는 나보다 작기 때문에 상관 없음.

seq=[0]*n #0~n-1 인덱스 사용
for i in range(n):
    for j in range(n):
        if a[i]==0 and seq[j]==0: # i라는 숫자앞에 0이 몇개 있는가 j 가 0 어야 들어갈 수 있음.
            seq[j]=i+1
            break
        elif seq[j]==0:
            a[i]-=1
for x in seq:
    print(x, end=' ')