[Python] 파라메트릭 서치(Parametric Search)

jake·2022년 9월 20일
0

python

목록 보기
13/20

파라메트릭 서치

파라메트릭 서치란 이분탐색에서 파생된 탐색 알고리즘이다.
따라서 두 방법은 상당히 유사하지만 문제의 틀만 맞다면 파라매트릭 서치가
훨씬 강력한 도구로 쓰일 수 있다.

파라메트릭 서치는 쉽게 말해 최적화 문제를 결정 문제로 바꾸어 푸는 것이라고
할 수 있다.

쉽게 이해하기 위해 예시를 들어보자.

나이를 기준으로 오름차순으로 정렬한 사람 1, 2, 3, 4, 5, 6, 7, 8, 9가 있다고 하자.
이 중 50세가 넘는 사람의 대답은 "yes", 넘지 않은 사람은 "no"라고 하자.
그렇다면 앞쪽의 50세가 넘는 사람들의 대답은 "no"일 것이고, 나머지 사람들의 대답은 모두 "yes"일 것이다.
이때 대답이 "yes"인 가장 나이가 어린 사람을 찾아보자.
대답은 ["no","no","no","no","no","yes","yes","yes","yes"]라고 가정하자.

이 문제는 처음으로 나이가 50세가 넘는 사람의 인덱스를 찾으면 되는데
이를 결정 문제로 바꾸면 질문이 바뀐다.


대답이 "Yes"인가요? 

대답이 "yes"인지 "no"인지 구분하고 이분탐색처럼 시작과 끝의 평균값을 계산해 범위를 점점 좁혀나가는 식으로 풀면 된다
밑의 코드로 결정 문제로 바꾼 질문에 대해 답을 살펴보자.

 

코드

def Parametric(array,start,end):
    
    if start>end: # 종료 조건 1
        return False

    mid=(start+end)//2

    if start==end: # 종료 조건 2
        if dic[start]=="yes":
            ans.append(start)        
            return True
        else:
            return False
        
    if dic[mid]=="no": # 재귀 조건 1
        return Parametric(array,mid+1,end)
        
    elif dic[mid]=="yes": # 재귀 조건 2
        if not Parametric(array,start,mid-1):
            if len(ans)==0:
                ans.append(mid)
            
     
ans=[]
arr=[0,1,2,3,4,5,6,7,8]
yesno=["no","no","no","no","no","yes","yes","yes","yes"]
dic={}
dic=dict(zip(arr,yesno))
Parametric(arr,0,8)

print(*ans)

이분탐색과 마찬가지로 평균값 mid는 시작과 끝의 소수점을 제거한 평균값으로 설정하였다.


종료 조건

종료 조건으로는 (1) 시작과 끝의 값이 역전 되었을 때, (2) 시작과 끝이 같을 때를 종료 조건으로 삼았다. 이때 대답이 "yes"면 리턴 True, 대답이 "no"면 리턴 Fasle

 

재귀 조건

재귀 조건이 좀 복잡한데 mid의 대답이 "no"면 mid 포함 왼쪽은 배열은
모두 대답이 "no"이기 때문에 왼쪽은 더이상 신경쓰지 않아도 된다.
그래서 바로 return Parametric(array,mid+1,end)을 호출하면 된다.


반면 mid의 대답이 "yes"일 경우 두 가지를 고려해야 한다.

  1. 처음으로 "yes"라고 대답한 사람이 mid인 경우
    ["no","no","no","yes"(mid),"yes","yes]

  2. 처음으로 "yes"라고 대답한 사람이 mid가 아닌 경우
    ["no","no","no","yes","yes"(mid),"yes]


1번과 2번을 구분하기 위해서 mid기준으로 왼쪽에 "yes"라고 대답한 사람이 있는지 확인해야 한다.

if not Parametric(array,start,mid-1) 이 조건문이 "yes"라고 대답한 사람이 있는지 확인하는 조건문인데 만약 이 조건문으로 앞에 "yes"라고 대답한 사람이 없으면 mid가 처음으로 "yes"라고 대답했으므로 mid를 답으로 출력하면 된다.

조건문을 통해 앞에 "yes"라고 대답한 사람이 있다는 것을 알았다면
다시 재귀를 통해 처음으로 "yes"라고 말한 사람을 찾아야 한다.

그러나 여기서 문제가 생기는데 앞에 사람이 모두 yes가 아닌 이상 조건문은 False를 출력한다.

예를 들어 조건문이 이 두가지 배열을 검사한다고 했을 때,
["no","no","no"], ["no","no","yes"]
배열안에 모두 "no"가 있으므로 False를 출력한다.
그러면 조건문이 의미가 없지 않다고 생각할 수 있는데 배열이 모두 "yes"로 이루어져 있는 경우도 있을 수 있기 때문에 조건문으로 검사는 해야한다.

어쨋든 대답이 "no"인 친구들 때문에 조건문은 False를 반환하고 재귀를 통해 다시 검사하여 답을 print하기 때문에 문제는 없다.


ans

굳이 왜 ans에 숫자를 넣어 출력을 했냐면, 재귀로 들어간 후 print를 하고 재귀를 빠져나온 후 워래 함수에서도 print를 하면 답이 두개가 print가 된다.
이것을 방지하기 위해 맨 처음 "yes"로 대답한 친구를 ans에 넣고
재귀를 빠져나와도 ans에 누군가 들어있다면 print하지 않는 식으로 코드를 짰다.

 

0개의 댓글