[Section04] Python 알고리즘 문제풀이 01~03

Q1. 이분검색 : 주어진 N개의 숫자를 오름차순으로 정렬 후 이분검색하여 M이 몇 번째에 있는지 출력

입력 :

N (3<=N<=1,000,000) M

N개의 수

출력 : M의 위치 번호

 

[내가 쓴 코드]

n, m = map(int, input().split())
a = list(map(int, input().split()))
low, high = 0, n-1
a.sort()

while(True) :
    mid = (low + high) // 2
    if a[mid] == m :
        print(mid+1)
        break
    elif a[mid] > m :
        high = mid - 1
    else :
        low = mid + 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

알고리즘 수업에서 들었던 거 참고하여 작성했음! 풀이코드와 while문 종료조건말고 동일한 듯

sort 함수를 사용하면서 효율성에 대한 궁금증이 생겨서 찾아봤는데 충분히 빠르다고 한다,,,

 

 

---

Q2. 랜선자르기(결정알고리즘) : K개의 랜선을 N개의 같은 길이의 랜선으로 만들기 위한 최대 랜선 길이

입력 :

N(1<=N<=1,000,000) K(1<=K<=10,000) 단, K <= N

N개의 랜선 길이

출력 : 최대 랜선 길이

 

[내가 쓴 코드]

def check(a, mid, k) :
    while(True) :
        count = 0
        mid += 1
        for x in a :
            count += (x//mid)
        if count == k :
            continue
        else :
            return mid - 1

n, k = map(int, input().split())
a = list()

for i in range(n) :
    a.append(int(input()))
    
low, high = 0, max(a)
count = 0

while(True) :
    mid = (low+high) // 2
    
    for x in a :
        count += (x//mid)
        
    if count == k :
        mid = check(a, mid, k)
        print(mid)
        break
    elif count < k :
        count = 0
        high = mid - 1
    else :
        count = 0
        low = mid + 1
        
#초반 접근
#large = max(a)
#m = large
#div = 2
#count = 0
#while(True) :
#    for x in a :
#        count += (x // m)
#    if count == k :
#        print(m)
#        break
#    else :
#        count = 0
#        m = large // div
#        div += 1

 

[풀이 코드]

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 :
        res = mid
        lt = mid + 1
    else :
        rt = mid - 1
        
print(res)

 

초반 접근으로 가장 긴 랜선을 나누는 방식으로 문제를 풀고 20점을 받아서 최대한 이분검색 관점으로 새로 작성하였음

최종 코드는 60점,,,

+) n이랑 k바꿨네 허허

 

특정 범위 안에 답이 있을 경우 이분검색 결정알고리즘을 사용함

1) 범위 : 1 ~ 가장 긴 랜선

2) Count 함수 생성

3) while문 종료 조건으로 lt <= rt 설정

4) 이분검색으로 최적의 답 찾기

 

---

Q3. 뮤직비디오(결정알고리즘) : N개의 곡이 들어있는 DVD를 최소한의 크기가 되도록 M개로 나누었을 때 DVD의 길이

입력 :

N(1<=N<=1,000) M(1<=M<=N)

N개의 곡의 길이

출력 : 최소 DVD 길이

 

[내가 쓴 코드]

정렬이 되어있는 범위가 어디인지 모르겠어서 못 풀었다. 하...

 

[풀이 코드]

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)    #n == m 일 경우를 고려
lt = 1
rt = sum(Music)

res = 0

while lt <= rt :
    mid = (lt + rt) // 2
    if mid >= maxx and Count(mid) <= m :    #n == m 일 경우를 고려
        res = mid
        rt = mid - 1
    else :
        lt = mid + 1
print(res)

DVD에 담겨있는 곡의 총 길이를 범위로 잡고 계산 실행

 

 

 

*강의 : 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)