정렬, 이진 탐색, 다이나믹 프로그래밍

『이것이 코딩 테스트다』 6장부터 8장이다. 정렬은 sort(key=lambda x: x[1]) 로 다중 리스트를 정렬하는 연습이 전부고, 이진 탐색은 재귀와 반복문 두 가지로 구현한 뒤 부품 찾기와 떡볶이 떡 만들기에 적용했다. 부품 찾기는 set 으로 푸는 쪽이 더 간단해서 시행착오 파일을 따로 남겼다. 다이나믹 프로그래밍은 피보나치를 단순 재귀, 메모이제이션, 반복문 세 가지로 쓰고 실행 시간을 비교한 것까지만 있다.

위에서 아래로

n=int(input())
li=[]
for i in range(n):
    li.append(int(input()))
li.sort(reverse=True)
for i in li:
    print(i,end=' ')

성적이 낮은 순서로 학생 출력하기

n=int(input())
li=[]
for i in range(n):
    li.append(list(input().split())) #split으로 받으면 또 split대로 list가 나뉘는군
    li[i][1] = int(li[i][1])

li.sort(key=lambda x:x[1]) # array=sorted(key=lambda x:x[1]) 다중 리스트에서 각 요소 별로 정렬할 때 많이 쓰임

for i in li:
    print(i[0],end=' ')

두 배열의 원소 교체

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

li_a.sort()
li_b.sort(reverse=True)

for i in range(k):
    if li_a[i] < li_b[i]:
        li_a[i],li_b[i]=li_b[i],li_a[i]
    else:
        break # 정렬했기 때문에 b가 더이상 크지 않으면 의미 없어 반복문 탈출

print(sum(li_a))

이진 탐색: 재귀 함수로 구현

def binary_search(array,target,start,end):
    if start > end:
        return None
    mid = (start+end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array,target,start,mid-1)
    else:
        return binary_search(array,target,mid+1,end)

n,target = map(int,input().split())
array = list(map(int,input().split()))

result = binary_search(array,target,0,n-1)
if result ==None:
    print("원소가 존재하지 않습니다.")
else:
    print(f'{result+1}번째 위치에 있습니다.')

이진 탐색: 반복문으로 구현

def binary_search(array,target,start,end):
    while start <=end:
        mid = (start+end)//2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid -1
        else:
            start = mid +1
    return None

n,target = map(int,input().split())
array = list(map(int,input().split()))

result = binary_search(array,target,0,n-1)
if result == None:
    print("없음")
else:
    print(f'{result+1}위치에 있음')

부품 찾기

이진 탐색

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

def binary_search(array,target,start,end):
    while start <= end:
        mid = (start+end)//2
        if array[mid] == target:
            return 'yes'
        elif array[mid] > target:
            end = mid -1
        else:
            start = mid + 1
    return 'no'

array.sort()

for target in targets:
    result = binary_search(array,target,0,n-1)
    print(result, end=' ')

set 으로 (시행착오)

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

array = set(map(int,input().split())) # -> 단순히 특정 수 체크 용도라면

for target in targets: # O(M)
    if target in array: # O(N)
        print("yes" ,end=' ')
    else:
        print("no", end=' ')

# 시간복잡도 O(M * N), 종류가 n가지가 아니라면 set방법도 괜찮음

떡볶이 떡 만들기

#1차 풀이
n,m=map(int,input().split())
li=list(map(int,input().split()))

li.sort()

# 가운데 떡길이 만큼 잘라봐서 가늠을 하는거지

def binary_search(li,m,start,end):
    h=0
    while start<=end:
        mid = (start+end)//2
        # 떡을 H만큼 잘랐을 때 나머지 길이
        sum_li = []
        for item in li:
            diff = item - li[mid]
            if diff > 0:
                sum_li.append(diff)

        # M만큼의 떡을 얻었다면 = 높이 최대
        if m == sum(sum_li):
            h = li[mid]
            break
        # m이상 이미 충분히 얻음 = 높이를 더 높여도 됌  = start 오른쪽으로 이동
        elif m < sum(sum_li):
            start = mid +1
            h = max(li[mid],h)
        # m만큼 얻지 못함. 높이를 줄여야함
        else:
            end = mid -1
    return h

print(binary_search(li,m,0,n-1))

피보나치 수열

단순 재귀

import time

def fibo(x):
    if x ==1 or x ==2:
        return 1
    return fibo(x-1) + fibo(x-2)

start = time.time()
print(fibo(6))
end = time.time()
print(round(end-start,3))

메모이제이션 (탑다운)

# memo방법 fibo (1)

import time

d = [0] * 100

def fibo_memo(x):
    if x ==1 or x == 2:
        return 1
    if d[x] !=0:
        return d[x]
    d[x] = fibo_memo(x-1)+fibo_memo(x-2)
    return d[x]

start = time.time()
print(fibo_memo(6))
end = time.time()
print(round(end-start,3))


def fibo_memo(x):
  if x==1 or x==2:
    return 1
  elif d[x] !=0:
    return d[x]
  else:
    d[x] = fibo_memo(x-1) + fibo_memo(x-2)
    return d[x]

fibo_memo(6)

반복문 (보텀업)

# memo방법 fibo (2)

import time
start = time.time()

dd = [0] * 100
dd[1] = 1
dd[2] = 1
n=30
for i in range(3, n+1):
    dd[i] = dd[i-1]+dd[i-2]
print(dd[n])

end = time.time()
print(round(end-start,3))