이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 10 번째 글 입니다.
목차
실버2 : 정렬 문제이다.
풀이
이전에 upper bound, lower bound가 잘 명확히 이해가 안되어서 다시 파이썬으로 풀어보자하고 도전했다.
lower bound
원하는 값보다 큰 값의 시작 index
일단 먼저 알아둬야 하는 것은, lower bound나 upper bound나 오른쪽 index로 답을 내려는 가정이 깔려있다는 사실이다. 그게 가장 중요하다. 그리고 나서 중앙값을 제안했을 때 문제의 목적에 맞게 후보가 되는지만 판단해주면 된다. 두 알고리즘이 공통적으로 가정하는 것을 정리해보자.
- right index로 답안을 낼 것이다.
- 나중에 while문을 통과하기 위해 양쪽 index(left, right)를 업데이트 할 때는 left한쪽으로만 이동한다.
- 즉 이말은 right index는 업데이트 시 mid를 그대로 두고, left만 mid+1로 기존 값을 검사하지 않아 최종적으로
while (left < right)문을 통과하기 위함이다.
- 즉 이말은 right index는 업데이트 시 mid를 그대로 두고, left만 mid+1로 기존 값을 검사하지 않아 최종적으로
def lower_bound(a, v): # v이하 최대 인덱스
left = 0
right = len(a)
print("left right mid value action")
while left < right:
temp = []
mid = (left+right)//2
temp.extend(list(map(str, [left, right, mid, v])))
if a[mid] < v:
left = mid + 1
temp.append(f'update left to {mid+1}')
else:
right = mid
temp.append(f'update right to {mid}')
print(" ".join(temp))
return right
index 0 1 2 3 4 5 6 7 8
list 2 4 5 5 5 7 9 9 9
find 5
위와 같은 문제가 주어졌다고 생각해보자.
left right mid value action
0 9 4 5 update right to 4
0 4 2 5 update right to 2
0 2 1 5 update left to 2
2
자 0과 8을 보고 중간값인 4가 채택된다. 리스트에서 해당되는 값은 5, 원하는 값과 같다. 그런데 우리가 하고싶은게 무엇인가? 이 5가 처음으로 등장하는 곳을 알고 싶은 것이다. 그럼 이녀석은 답이 될 수 있는 후보 이다. 그런데 이 5보다 작은 곳에서 답이 나오면 어떡하지? 그러니까 right 인덱스에 얘를 붙잡아두고 그 사이의 값을 다시 탐색한다. 이 작업의 결과가 두번째 라인이다. 두번쨰에서도 우리는 5를 찾았다. 여전히 새로운 후보이니 붙잡아 둔다. 그런데 그 다음으로 가보니 값이 4가 나왔다. 얘는 후보가 될 수 없다. 그리고 이 4보다 큰쪽에서 5라는 값을 찾아야 하니까 +1하여 left를 업데이트 한다. 이제 right와 left가 값이 2로 같아졌기 때문에 반복문을 탈출하고, 끝난다.
여기서 핵심은, 같은 것이 나왔을 때 어떻게 처리해야 하느냐에의 판단이다. 같은 값이 나오게 되었을 때, lower bound의 경우 왼쪽을 탐색해야 한다.(더 작은 곳에 후보가 있는지) 그렇기 때문에 right를 땡겨오는 것.
upper bound
원하는 값보다 큰 (초과) 첫번째 index
def upper_bound(a, v): # v이하 최대 인덱스
left = 0
right = len(a)
print("left right mid value action")
while left < right:
temp = []
mid = (left+right)//2
temp.extend(list(map(str, [left, right, mid, v])))
if a[mid] <= v:
left = mid + 1
temp.append(f'update left to {mid+1}')
else:
right = mid
temp.append(f'update right to {mid}')
print(" ".join(temp))
return right
index 0 1 2 3 4 5 6 7 8
list 2 4 5 5 5 7 9 9 9
find 5
가장 중요한 것은 뭐다? 같았을 때 어디를 탐색해야 하는지이다. 같을 경우, 이번에는 오른쪽을 탐색해야 한다. 왜냐하면 일단 5가 나왔다. 그럼 얘보다 일단 큰 부분에서 답이 나올거아닌가? 그러니 mid+1로 left를 업데이트 한다. 만약에 그 다음 스텝에서 조사한 값이 내가 원하는 값보다 크면, 그럼 답은 더 작은 곳에 있으니 이녀석을 붙잡아 두고(답이 될 수 있는 후보이다.) 다음으로 넘어간다.
left right mid value action
0 9 4 5 update left to 5
5 9 7 5 update right to 7
5 7 6 5 update right to 6
5 6 5 5 update right to 5
5
Code
def lower_bound(a, v): # v이하 최대 인덱스
left = 0
right = len(a)
print("left right mid value action")
while left < right:
temp = []
mid = (left+right)//2
temp.extend(list(map(str, [left, right, mid, v])))
if a[mid] < v:
left = mid + 1
temp.append(f'update left to {mid+1}')
else:
right = mid
temp.append(f'update right to {mid}')
print(" ".join(temp))
return right
def upper_bound(a, v): # v이하 최대 인덱스
left = 0
right = len(a)
print("left right mid value action")
while left < right:
temp = []
mid = (left+right)//2
temp.extend(list(map(str, [left, right, mid, v])))
if a[mid] <= v:
left = mid + 1
temp.append(f'update left to {mid+1}')
else:
right = mid
temp.append(f'update right to {mid}')
print(" ".join(temp))
return right
a = [2,4,5,5,5,7,9,9,9]
lower_bound(a, 5)
upper_bound(a, 5)
문제 풀이 Code