차근차근 Python 알고리즘 스터디 week_3, 4

강의

섹션 4. 이분탐색&그리디 알고리즘

랜선자르기

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이 다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

import sys
sys.stdin=open("input_2.txt", "r")
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)

뮤직비디오

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

import sys
sys.stdin=open("input.txt", "r")
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)

마구간 정하기

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

import sys
sys.stdin=open("input.txt", "r")
def Count(len):
    cnt = 1
    ep = Line[0]
    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 = []
for _ in range(n):
    tmp = int(input())
    Line.append(tmp)
Line.sort()
lt = 1
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)

회의실 배정(그리디)

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
정렬을 동반되어 문제를 푼다.

import sys
sys.stdin = open("input_5.txt", "r")
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])) # 기준 바꿔놓기
et = 0
cnt = 0
for s, e in meeting:
    if s >= et:
        et = e
        cnt += 1

print(cnt)

씨름 선수

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자 만 뽑기로 했습니다.”
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다. 씨름 선수로 뽑히는 최대 인원을 출력하세요.

import sys
sys.stdin = open("input_6.txt", "r")

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)

창고 정리

import sys
sys.stdin = open("input_7.txt", "r")
L = int(input())
a = list(map(int, input().split()))
m = int(input())

a.sort()
for _ in range(m):
    a[0] += 1
    a[-1] -= 1
    a.sort()

print(a[-1] - a[0])

침몰하는 타이타닉

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있 으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.

#1
import sys
sys.stdin = open("input_8.txt", "r")
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)

#2 
import sys
from collections import deque
sys.stdin = open("input_8.txt", "r")
n, limit = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
cnt = 0
p = deque(p)

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)

1번 알고리즘에서 pop(0)을 하면 리스트의 모든 값들이 하나씩 당겨지는 연산이 수행되어 비효율적이다. 그래서 deque 구조를 사용해 p.popleft()을 사용한다면 더욱 효율적인 알고리즘을 구현할 수 있다.

증가수열

1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다.
이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열 을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니 다.
예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다.
맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽끝에서5를가져와 2345증가수열을만들수있습니다.
첫째 줄에 최대 증가수열의 길이를 출력합니다.
두 번째 줄에 가져간 순서대로 왼쪽 끝에서 가져갔으면 ‘L', 오른쪽 끝에서 가져갔으면 ’R'를 써 간 문자열을 출력합니다.(단 마지막에 남은 값은 왼쪽 끝으로 생각합니다.)

import sys
sys.stdin = open("input_9.txt", "r")
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)

역수열

import sys
sys.stdin = open("input_10.txt", "r")
n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
seq = [0] * n
for i in range(1, n + 1):
    for j in range(n):
        if a[i] == 0 and seq[j] == 0:
            seq[j] = i
            break
        elif seq[j] == 0:
            a[i] -= 1

for x in seq:
    print(x, end=' ')

교재 : [셋째마당] 탐색과 정렬

순차 탐색 알고리즘

def serch_list(a,x);
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            return i
    return -1

주어진 리스트에서 특정값의 위치를 찾아 돌려주는 알고리즘

선택정렬

#1
def find_min_idx(a):
    n = len(a)
    min_idx = 0
    for i in range(1, n):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def sel_sort(a):
    result = []
    while a:
        min_idx = find_min_idx(a)
        value = a.pop(min_idx)
        result.append(value)
    return result
    
#2
def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

선택정렬은 리스트의 최솟값을 하나씩 빼서 새로운 리스트에 넣어 정렬하는 방법이다. 계산복잡도 : $O(n^2)$

삽입정렬

#1
def find_ins_idx(r, v):
    for i in range(0, len(r)):
        if v < r[i]:
            return i
    return len(r) # 찾아서 없으면 맨 뒤

def ins_sort(a):
    result = []
    while a:
        value = a.pop(0) # 리스트에서 한개 꺼내서 
        ins_idx = find_ins_idx(result, value) # 값이 들어갈 위치를 찾아
        result.insert(ins_idx, value) # 찾은 위치에 삽입 
    return result
    
#2
def ins_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

삽입 정렬은 값을 하나 꺼내 새로운 리스트의 적당한 위치를 찾아 삽입해 정렬하는 방법이다. 계산복잡도 : $O(n^2)$

병합정렬

#1
def merge_sort(a):
    n = len(a)
    if n <= 1: # 종료 조건
        return a

    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    result = []
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else :
            result.append(g2.pop(0))

    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))

병합정렬은 리스트를 절반으로 나눈 다음, 서로 첫 번째 값들을 비교하며 재귀 호출로 풀어가는 방식이다. 계산복잡도 : $O(n*logn)$

퀵정렬

def quick_sort(a):
    n = len(a)
    if n <= 1:
        return a
    pivot = a[-1] # 기준값
    g1 = []
    g2 = []

    for i in range(0, n -1): # 마지막 값은 기준값
        if a[i] < pivot:
            g1.append(a[i]) # 크면 g1
        else:
            g2.append(a[i]) # 작으면 g2
    return quick_sort(g1) + pivot + quick_sort(g2)

퀵정렬은 기준값(pivot)을 정한 뒤, 그 값보다 큰 그룹과 작은 그룹을 나누어가며 재귀호출로 풀어가는 방식이다.

퀵 정렬의 경우, 기준값을 잘 못잡는 경우(가장 크거나 작은 값을 기준값으로 잡는 경우) 선택정렬이나 삽입정렬처럼 계산복잡도가 $O(n^2)$이 되어버리지만, 평균적일 때는 $O(n*logn)$

이분탐색

def binary_serch(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if x == a[mid]:
            return mid
        elif x > a[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return -1

이분탐색이란 정렬된 리스트에서 특정값을 찾아 위치를 찾는 문제에서 리스트의 중간값과 특정값을 비교해보며 탐색하는 알고리즘이다.
계산복잡도 : $O(logn)$

연습문제

# 7_1
def serch_list_2(a,x):
    n = len(a)
    ans = []
    for i in range(0, n):
        if x == a[i]:
            ans.append(i)
    
    if ans != []:
        return ans
    else:
        return -1

# 7_3
def serch_student(s_no, s_name, num):
    for i in range(0, len(s_no)) :
        if num == s_no[i]:
            return s_name[i]
    return "?"

# 11_1 거품정렬
def bubble_sort(a):
    n = len(a)
    while True:
        changed = False
        for i in range(0, n - 1):
            if a[i] > a[i + 1]:
                print(a)
                a[i], a[i + 1] = a[i + 1], a[i]
                changed = True
        if changed == False:
            return
    
# 12_1 재귀 호출을 이용한 이분탐색
def binary_serch_2(a, x, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if x == a[mid]:
        return mid
    elif x > a[mid]:
        return binary_serch_2(a, x, mid + 1, end)
    else :
        return binary_serch_2(a, x, start, mid - 1)
    return -1