[코드트리 조별과제] Parametric Search / 자연수 n개의 합 Python 풀이

매번 이렇게 급히 공부를 하네요ㅠ

 

이번에는 파라메트릭 서치를 공부했습니다.

이진탐색을 알긴 하지만, 뭔가 =의 여부 등 헷갈리는게 있어서 이번에 정리할 수 있었습니다.

 

그리고 파라메트릭 서치를 그 전에는 잘 이해를 못하고 있었던 것 같더라고요...? 이번에 느낀 건 범위를 줄이는 스킬.. 정도로 이해했어요

 

Parametric Search(파라메트릭 서치)

파라메트릭 서치는 범위를 반씩 줄여나가면서 가장 적합한 답을 찾는 방법인 것 같습니다

어떤 구간의 중간이 조건에 부합되는지를 확인하고,

부합하는지 여부에 따라 왼쪽/오른쪽 범위를 변경하면서 구간을 더 좁혀나가는 방식이에요

 

이진탐색이라고도 할 수 있는데, 포인트는 최댓값/최솟값을 찾기에는 파라메트릭 서치가 더 적합하다는 것!

 

문제로 이해해봅시다

 

문제) 자연수 n개의 합

https://www.codetree.ai/missions/8/problems/sum-of-n-natural-numbers/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

1부터 n까지의 합이 s이하가 되는 최대 n이 무엇인지 찾는 문제에요

 

풀이 - Python

s=int(input())
ans=0
l,r=1,1_000_000_000_000

while l<=r:
    m=(l+r)//2
    if m*(m+1)//2<=s:
        l=m+1
        ans=max(m,ans)
    else:
        r=m-1

print(ans)

 

배운 점

1. 이진탐색 코드의 포인트

- 이진탐색에서 left, right를 사용한다면, 종료조건은 l이 r을 넘어갔을 때이다! (left<=right 등호가 포함된다는 것)

- left, right를 업데이트 할 때, mid의 양 옆으로 업데이트한다.. 왜냐면, left==right가 될 때도 반복문이 수행되므로!

 

2. 정답 업데이트

- 조건을 확인하는 기준이 mid이므로, 정답을 업데이트 할 때는 mid를 사용한다!!

 

3. 초기 세팅

- 최댓값을 구한다면, 절대 불가능한 작은 값을 초깃값으로 세팅하고, 최솟값을 구한다면 불가한 가장 큰 값을 초깃값으로 설정한다

 

 

4. 내가 대충 알던 파라메트릭 서치의 정체..!

def para_search(li,n): #n 이하인 수 중 가장 오른쪽 값
  cur=-1
  step=len(li)
  while step>0:
    if li[cur+step]>n:
      step//=2
    else:
      cur=cur+step
  return cur

이 코드가 무엇이냐면, 어떤 리스트 안에서 n 이하인 수 중 가장 오른쪽 값(=최댓값)을 찾는 코드이다.

left right를 설정하지 않고, step을 이용하는데, 나는 이제껏 파라메트릭 서치라고 하면 이렇게 해야하는줄 알았다...ㅎㅎ

하지만 분석해보자면,

초깃값으로 절대 불가능한 가장 작은 인덱스(-1)를 설정해놓고, 구간을 좁혀가는 형식이다

left=0, right=n-1 -> 이렇게 하면 mid를 이용하지만

cur=-1, step=n -> 이렇게 하면 cur을 바꿔가는 형태가 되는 것이다!

 

이때 cur이 left의 역할을 하게 되는데, 여기서의 포인트는 최댓값, 즉 가장 오른쪽 값을 사용하므로 left를 더 크게 하여 범위를 줄일 수 있다면, 계속 오른쪽으로 갈 뿐 다시 뒤로 가지는 않는다는 점!

 

그리고 끝나는 종료 조건이 step이 있을 때인데, 여기서 cur+step이 right의 역할을 하므로 left==right가 같아지는, 즉 step==0일 때 종료된다는 것이다.