Koala 4주차 : 이진탐색, 누적합
* 이진탐색(Binary Search)
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
이진 탐색은 "정렬된 리스트"에서 특정 값의 위치를 찾는다. 항상 이진 탐색을 할 때는 리스트를 정렬된 상태로 진행해야 함에 유의할 것!!
-> 반복문과 재귀 두 가지 방법을 사용할 수 있다.
1. 시간복잡도 : O(logN)
2. 자료를 오름차순으로 정렬한다.
3. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
4. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 3번과 4번을 반복한다.
ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)
ⓑ target이 mid 값 보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)
1. While 반복문을 사용한 이진탐색
def binary_search(target, data):
data.sort()
start = 0
end = len(data) - 1
while start <= end:
mid = (start+end) // 2
if data[mid] == target:
return mid
elif data[mid] > target:
end = mid - 1
else:
start = mid + 1
return
2. 재귀함수를 사용한 이진탐색
def binary_search(target, start,end):
if start > end:
return-1
mid = (start+end)//2
if data[mid] == target:
return mid
elif data[mid] > target:
end = mid - 1
else:
start = mid + 1
return binary_search(target, start, end)
def solution(target, data):
data.sort()
start = 0
end = len(data-1)
return binary_search(target, start, end)
* 이진탐색 관련 문제풀이
1. 1072 : 게임
* 완전 탐색으로 구현한 시간초과된 오답
import sys
input = sys.stdin.readline
import math
x, y =map(int, input().split())
num = math.floor((y/x)*100)
def find_i():
for i in range(1000000000):
n_num = math.floor(((y+i)/(x+i))*100)
if num != n_num:
return print(i)
if i == 1000000000:
return print(-1)
find_i()
* 이진탐색을 통한 풀이
import sys
input = sys.stdin.readline
import math
x,y = map(int, input().split())
z = math.floor((y*100)/x)
res = x
left, right = 0, x
if z>= 99:
print(-1)
else:
while left<=right:
mid = (left+right)//2
num = math.floor(((y+mid)*100)/(x+mid))
if num > z:
res = mid
right = mid-1
else:
left = mid+1
print(res)
-1을 출력하는 경우는 애초에 승률이 99%가 넘어갈 때이므로 이때를 체크해두고, 수정된 승률이 기존의 승률보다 높을 때를 갱신하여 갱신한 값을 출력해주면 된다.
2. 16401 : 과자 나눠주기
import sys
input = sys.stdin.readline
m,n = map(int,input().split())
list1 = list(map(int, input().split()))
left, right = 1, max(list1)
num = 0
while left<= right:
count = 0
mid = (left+right)//2
for i in list1:
count += i//mid
if count>=m:
num = mid
left = mid+1
else:
right = mid-1
print(num)
처음에는 list1.sort()를 한 다음에 right 변수에 list1[-1]을 할당했다. 그런데 시간초과가 떠서 max(list1)을 해줬더니 정답이 되었다. list의 sort()는 보통 O(nlogn), max()는 O(n)이라고 알고 있긴한데, 이게 답을 결정짓는 요소가 된다는 걸 아직은 이해하지 못하겠어서 질문글을 올렸다.
3. 17951 : 흩날리는 시험지 속에서 내 평점이 느껴진거야
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
arr = list(map(int, input().split()))
left, right = 0, int(1e5)*20+1
ans = 0
while left<=right:
mid = (left+right)//2
count = 0
num = 0
for i in arr:
num += i
if num>=mid:
count += 1
num=0
if count >= K:
ans = mid
left = mid+1
else:
right = mid-1
print(ans)
이 문제를 풀 때 mid 값이 의미하는 것은 맞은 문제 개수의 합으로 정해놓는 것이 중요했다. 그 다음 mid 값보다 맞은 문제 개수가 넘어가면 count하면서 나누는 부분의 개수인 K와 비교하며 이분탐색을 이어나가면서 풀이했다.
일단 이번 문제를 풀이하면서 count하는 방식이 이렇게 할 수도 있구나하는 걸 배웠고, 이분탐색이 꼭 이쁘게 정렬된 리스트 값들을 가지고 문제를 푸는 것이 아니라는 것을 알아갈 수 있었다.
* 누적합
-> 나열된 수의 구간 합을 빠르게 구하는 알고리즘이다.
dp랑 느낌이 많이 비슷한데 '연속하는 어떤 구간'이 나온다면 느낌이 올 수 있을 것이다.
1. 1차원 배열에서의 예제
https://www.acmicpc.net/problem/11659
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
list1 = list(map(int, input().split()))
prefix_sum=[0]
num = 0
for i in list1:
num += i
prefix_sum.append(num)
#print(prefix_sum)
for _ in range(m):
x,y = map(int, input().split())
print(prefix_sum[y]-prefix_sum[x-1])
2. 2차원에서의 예제
1. 2167 : 2차원 배열의 합
https://blog.naver.com/hcw2166/222505914437
Python - 2차원 배열의 합(누적합), 백준 2167
카카오 코딩테스트를 치뤘는데, 해당 문제에서 효율성 테스트를 통과하지 못했다. 모르는 부분은 반드시 알...
blog.naver.com
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = []
dp = [[0]*(m+1) for _ in range(n+1)]
for _ in range(n):
a.append(list(map(int, input().split())))
for i in range(1, n+1):
for j in range(1,m+1):
dp[i][j] = a[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
for _ in range(int(input())):
i,j,x,y = map(int,input().split())
print(dp[x][y]-dp[i-1][y]-dp[x][j-1]+dp[i-1][j-1])
3. 19951 : 태상이의 훈련소 생활
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
ground = list(map(int,input().split()))
order = [0 for _ in range(n+1)]
for _ in range(m):
a,b,k = map(int,input().split())
order[a-1] += k
order[b] -= k
for i in range(n):
order[i+1] += order[i]
for i in range(n):
ground[i] += order[i]
print(*ground)
누적합의 풀이 방식이 이렇게도 진행될 수 있구나를 깨달았다.
https://kau-algorithm.tistory.com/1539
[백준/python] 19951 태상이의 훈련소 생활
19951번: 태상이의 훈련소 생활 (acmicpc.net) 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인
kau-algorithm.tistory.com
위 블로그를 참고해 문제를 풀이했다.
* 4주차 모의테스트 문제(이진탐색, 누적합)
1. 19637 : if문 좀 대신 써줘
https://www.acmicpc.net/problem/19637
2. 10025 : 게으른 백곰
https://www.acmicpc.net/problem/10025
import sys
input = sys.stdin.readline
n,k=map(int,input().split())
max_sum = 0
list1 = []
for _ in range(n):
list1.append(list(map(int, input().split())))
list1.sort(key=lambda x:x[1])
left,right = 0,0
num = 0
while left<=right and right<n:
if list1[right][1]-list1[left][1] <= 2*k:
num += list1[right][0]
max_sum = max(max_sum,num)
right += 1
else:
num -= list1[left][0]
left += 1
print(max_sum)
이 문제를 처음 풀이할 때 k 범위의 중간값을 mid로 잡아 얼음양의 크기가 최대가 되도록하는 이진탐색 알고리즘을 만들려고 했으나 어떤 상황에서 left값이 바뀌고 right값이 바뀌는지 정할 수 없었다.
그래서 구글의 힘을 빌려 지난주에 공부했던 주제인 투 포인터로 해결할 수 있다는 것을 깨달았다. while문 전까지는 그냥 문제 상황에 대한 구현이니 넘어가고, while문이 본격적인 이 문제의 풀이이니 설명해보도록 하겠다.
범위가 중간을 기준으로 -k, +k이니 양쪽 끝의 포인터로 범위값을 계산했을 때 그 범위가 2*k안에 있으면 된다. 그러면 값에 오른쪽 포인터값의 얼음 양을 더하고 오른쪽 포인터값을 +1하면 된다. 만약 양쪽 끝의 포인터의 범위가 2*k 안쪽에 있지 않으면, 맨 왼쪽 포인터값의 얼음 양을 빼고 왼쪽 포인터값을 +1하면 된다.
투 포인터는 이럴 때 쓰는구나를 배워갈 수 있었던 문제였다.
3. 16139번 : 인간-컴퓨터 상호작용
https://www.acmicpc.net/problem/16139
1. 틀린 풀이(ValueError)
import sys
input = sys.stdin.readline
s = input().strip()
list1 = list(set(s))
q = int(input().strip())
every_list = []
for i in list1:
find_list = [0 for _ in range(len(s))]
for j in range(len(s)):
if s[j]==i:
find_list[j]+= 1
every_list.append(find_list)
for _ in range(q):
a,l,r = input().strip().split()
listm = every_list[list1.index(a)]
print(sum(listm[int(l):int(r)+1]))
누적합을 사용하지 않고 그냥 한 풀이 -> 7%에서 런타임에러가 난다.
2. 누적합을 이용한 풀이
import sys
input = sys.stdin.readline
s = input().strip() # 개행 문자 제거
q = int(input())
# 알파벳 26개에 대한 누적합 배열 생성
prefix_sum = [[0] * (len(s) + 1) for _ in range(26)]
# 누적합 계산
for i in range(len(s)):
for j in range(26):
prefix_sum[j][i + 1] = prefix_sum[j][i]
prefix_sum[ord(s[i]) - ord('a')][i + 1] += 1
# 쿼리 처리
for _ in range(q):
a, l, r = input().split()
l, r = int(l), int(r)
idx = ord(a) - ord('a')
result = prefix_sum[idx][r + 1] - prefix_sum[idx][l]
print(result)
뭔가 누적합을 써야할 것 같은데 어떻게 쓰는지 감이 안와서 chatGPT의 힘을 빌렸습니다.