07. 이진탐색
순차탐색- O(N)
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
이진탐색 - O(logN)
배열 내부의 데이터가 정렬되어 있어야만 사용 가능하다
이진탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.
- 재귀함수 이진탐색
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 = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target , 0, n-1)
if result == None:
print("존재x")
else:
print(result+1)- 라이브러리 이진탐색
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
a = [1,2,3,3,3,3,5,5,8,9]
print(count_by_range(a, 4,4)) #값이 4인 데이터 개수 출력
print(count_by_range(a, -1, 3)) # 값이 [-1, 3] 범위에 있는 데이터 개수 출력부품 찾기
- 완탐풀이 : 10분, O(N)
n = int(input())
n_arr = list(map(int, input().split()))
m = int(input())
m_arr = list(map(int, input().split()))
answer =[]
for check in m_arr:
if check in n_arr:
answer.append("YES")
else:
answer.append("NO")
print(' '.join(answer))
떡볶이 떡 만들기
- 1차시도
이진탐색을 공부했음에도 완탐으로 풀려고 했다...
내림차순 정렬하여 큰값을 기준으로 전체탐색을 해 h와 근접한 값을 찾으려함.
찾고 난뒤 범위값을 만들어 합을 비교
arr = [19, 17, 15, 10] #내림차순정렬
h = 19 [0,0,0,0] sum=0
h = 17 [2,0,0,0] sum=2
h = 15 [4,2,0,0] sum=6
h = 10 [9,7,5,0] sum=31
m=8이라면 15~10사이 범위가 정해졌고,
여기서 14,13,12,11일때의 sum차이를 비교하려고 했는데... 넘 비효율적이라고 생각됨 - 2차시도
자꾸 코드 에러가 떠서 이해를 못함. 평면적으로 생각을 했다.
값이 크니까 오른쪽 큰값을 줄여나가야 한다고 생각을 했는데, 문제에서는 총합의 크기가 큼으로 왼쪽 작은 값을 키워야 총 합의 크기가 줄어든다.
n, m = map(int, input().split())
arr = list(map(int, input().split()))
lt = 0
rt = max(arr)
answer=0
while lt <=rt:
save = 0
mid = max(arr) // 2
for x in arr:
if x>mid:
save += x-mid
else:
continue
if save>mid: #sv값이 더 클경우 -> 큰범위를 줄여야..?
rt = mid-1
elif save<mid: #sv값이 더 작을경우
lt = mid+1
else:
answer=save
print(answer)- 최종
n, m = map(int, input().split())
arr = list(map(int, input().split()))
lt = 0
rt = max(arr)
answer=0
while lt <=rt:
save = 0
mid = (lt+rt) // 2
for x in arr:
if x>mid:
save += x-mid
else:
continue
if save>mid: #sv 더 클경우
lt = mid+1
answer = mid
else:
rt = mid-1
print(answer)합한 값이 클때, 작을때, 같을때로 나누려고 했었는데 합이 클경우의 mid값을 answer에 저장시켜 계속 남기는 방식을 이해하지 못했었음.
문제점
- 주어진 값이 억단위일 경우 바로 이분탐색을 생각하기
- 중간값을 어떻게 활용할지 고민 후 코드 짜기
- save 값 초기화
max(arr)//2로 둔 실수 (lt, rt 활용을 제대로 생각 못함)- 범위값 설정 고민
08. 다이나믹 프로그래밍
다이나믹 프로그래밍(동적 계산법)
다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 멤모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
탑다운 Top-Down
재귀함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방법
d = [0]*100
def pibo(x):
print('f(' + str(x) + '),', end=' ')
if x==1 or x ==2:
return 1
if d[x]!=0:
return d[x]
d[x]=pibo(x-1) + pibo(x-2)
return d[x]
pibo(6)보텀업 Bottom-Up
단순히 반복문을 이용하여 소스코드를 작성하는 경우, 작은 문제부터 차근차근 답을 도출하는 방법
d=[0]*100
d[1]=1
d[2]=1
n=99
for i in range(3 +n+1):
d[i]=d[i-1] + d[i-2]
print(d[n])1로 만들기
- 1차시도 - 에러
예전 책 예시문제와 같아서 같은 방식으로 풀었더니 2의 값에서 먼저 나눠져 경우의 수가 더 늘어난 것을 알게됨
n = int(input())
cnt=0
while n>1:
if n%5==0:
cnt+=1
n=n//5
elif n%3==0:
cnt+=1
n=n//3
elif n%2==0:
cnt+=1
n=n//2
else:
cnt+=1
n-=1
print(cnt) # 26 -> 5- 2차시도 - 구현에러
DFS 탑다운 방식으로 풀면 된다고 생각함
최소 경우의수라 우선 나눠지지 않는 값들은 제외하고 나눠지는 값들중 0이되는 것에서 카운트한 최소값을 답으로 하면 되지 않을까? 생각했는데 구현에서 막힘...
이부분은 좀더 고민해보고 다시 수정할 예정
min_value = 2147000000
def DFS(v, n):
global min_value
if n==0: # 최소경우를 출력시켜야 하는데 먼저 0이된값이 나옴...
if v<min_value:
min_value=v
return min_value
else:
if n%5==0:
DFS(v+1, n=n//5)
elif n%3==0:
DFS(v+1, n=n//3)
elif n%2==0:
DFS(v+1, n=n//2)
else:
DFS(v+1, n=n-1)
def solution(n):
return DFS(0, n)
print(solution(26))- 책풀이 Bottom-UP
def solution(n):
answer=0
d=[0]*30001 #저장장소
for i in range(2, n+1): #2-6까지 범위
#1을 뺄 경우 , +1 경우의수
d[i]= d[i-1] +1
"""
2,3,5로 나눠질때 min[저장된값, 현재값+(1경우의 수)] 비교
a(i) = min(a(i-1), a(i/2), a(i/3), a(i/5))+1
-1,/2,/3,/5 계산한 값중 가장 작은 값의 경우를 비교해 +1을 해준다
"""
if i%2 == 0:
d[i]=min(d[i], d[i//2]+1)
if i%3 == 0:
d[i]=min(d[i], d[i//3]+1)
if i%5 == 0:
d[i]=min(d[i], d[i//5]+1)
return d[n]
print(solution(6))점화식 부분을 이해하는데 시간이 오래걸렸다.
바텀업 방식을 푸는 습관을 들여야할것 같음
- 완탐접근시 오래걸린다면 DP적용이 되는지 고민하기
- 재귀에서 구한답이 bottom-up으로 구현이 가능하다면 코드 개선하기
- 재귀함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는것을 권장한다. 스택의 크기가 한정되어있기 때문이다
비슷한 문제: 백준1463번
개미전사
- 인덱스를 활용해서 2칸~마지막칸까지 경우의 수를 생각해봤는데 아이디어가 떠오르지 않았음
이문제도 점화식이 이해안가서 직접 예제를 만들고 그리고나서야 이해가 됐다...
n = int(input())
food = list(map(int, input().split()))
d = [0]*100
d[0] = food[0]
d[1] = max(food[0], food[1]) #두번째 칸을 공격 or 두번째칸을 공격하지 x
for i in range(2,n):
#현재위치에 더큰값을 저장 = (전값[-1], 전전값[-2]+현재[0]) 비교
d[i] = max(d[i-1], d[i-2] + food[i])
print(d[n-1])바닥공사
dp문제는 꾸준히 풀고 복습하는게 살길같다...
수열의 규칙을 파악하는게 중요한데 내머리로는 어림도없음..
규칙파악이 안돼서 계속 그렸는데,,, 책을 봐도 이해를 못했었다. 다시 설명보면서 그려보니 얼추 이해가 됐다.
여기서 파악해야 할 규칙은 n-1, n-2일때의 경우의 수
n = int(input())
d = [0]*1001
d[1]=1 #1 -> 1
d[2]=3 #2 -> (2,2) ,(1,1)(1,1)가로, 세로 => 3가지
for i in range(3, n+1):
"""
타일의 최대 길이는 2임으로 두가지 경우만 존재함 d[1], d[2]
d[3] = d[2] + (d[1]*2)
1. d[i-1]의 경우 = 1X2 - 1가지
2. d[i-2]의 경우 = 2X2, 2X1(2개) - 2가지
"""
d[i]= (d[i-1] +2 *d[i-2])%796796
print(d[n])비슷한문제 : 백준 1727번
효율적인 화폐구성
- 문제를 제대로 보고 풀자... - 에러
그리디에서 풀었던 대로 코드를 짜다가 막혀서 어떤식으로 생각해야할지 막힘
n, m = map(int, input().split())
coin = []
for i in range(n):
a= int(input())
coin.append(a)
coin.sort(reverse=True)
cnt=0
while m>0:
for x in coin:
if x%m==0:
cnt=m//x
m=m//x
print(cnt)
- 점화식
n, m = map(int, input().split())
coin = []
for i in range(n):
a= int(input())
coin.append(a)
d=[10001]*(m+1)
d[0]=0 # 아무것도 사용 안할경우 = 0
for i in range(n): #i: 화폐단위
for j in range(coin[i], m+1) : #j: 각각의금액
if d[j-coin[i]]!= 10001: #INF가 아니면 만들 수 있는 값이다
"""
i = 0~2 => i=0, coin[0]=2
j = 2~7 => 금액구하기
d[2-coin[0]] = 0 -> INF가 아님으로 만들 수 있다.
d[2] = min(d[2], d[2-2]+1)
최솟값(10001, 1)
d=[0, 10001, "1", 10001] <=2는 1개로 만들어짐
"""
d[j] = min(d[j],d[j-coin[i]]+1)
if d[m]== 10001:
print(-1)
else:
print(d[m])
개발기록