Alogorithm _ 2. 완전탐색, 이분탐색

● 탐색이란?

많은 데이터 속에서 원하는 데이터를 찾는 것으로 웹에서 특정 문자를 가진 웹문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용한다.

 

탐색의 종류는 다음과 같이 많은 것들이 있다.

 

완전탐색

이분탐색

깊이우선탐색

너비우선탐색

문자열탐색

KMP

BM

 

이 포스트에서는 가장 기본이 되는 완전 탐색, 이분 탐색, 깊이우선탐색, 너비우선탐색 만 다룰 예정이다.

 

● 완전탐색

브루트 포스(Brute Force)라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법으로 소개된다.

(물론 그만큼 풀리지 않는 방법이 없다는 장점이 있다.)

 

대표적인 완전탐색의 구현 방법은 반복문과 재귀함수(완전 탐색 외의 동적 계획법, 백트래킹, 탐욕법등 다양한 알고리즘에서도 사용하기도 한다.)가 있다.

 

for문 활용의 완전탐색은 굳이 학습하지 않아도 익숙하게 구현해온 방법이며 대표적인 형식은 다음과 같다.

def solution(trump):
	for i in range(len(trump)):
    	if trump[i] == 8:
        	return i
 	return -1

위와 같이 간단한 반복문 외의도 재귀함수를 사용하여도 완전탐색을 쉽게 구현할 수 있다.

def solution(trump, loc):
	if trump[loc] == 8:
    	return loc
    else:
    	return solution(trump, loc+1)

재귀함수를 이용한 완전탐색은 쉽게 무한루프에 빠질수도 있으니 유의하자.

 

● 이분탐색

이진검색이라고도 표현하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘이다.

일반적으로 중간의 값을 선택하여 찾꼬자 하는 값과의 크고 작음을 비교 하는 방법을 사용한다.

 

예시코드(trump list에서 8을 찾는 예제)는 다음과 같다.

def solution(trump):
	left = 0
    right = len(trump)-1
    while(left<=right):
    	mid = (left+right)//2
        if turmp[mid] == 8:
        	returm mid
        elif trump[mid] < 8:
        	left = mid + 1
        elif trump[mid] > 8:
        	right = mid - 1
    return mid

 

● 알고리즘 문제 - 문자열압축 (2020 카카오 블라인드)

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

문제 풀이

이 문제는 주어진 수의 배열과(위치가 고정) 연산자의 갯수(위치가 가변)에 따른 경우의 수 중의 결과식의 최댓값과 최솟값을 탐색하는 문제이다.

 

완전 탐색의 방법으로는 "모든 경우의 수"의 결과값을 저장하고 그중의 최댓값과 최솟값을 탐색하는 방법이 있다.

(max, min 함수 방법을 이용하면 쉽게 구현이 가능할듯 하다.)

 

이분 탐색 방법으로 접근하기위해서는 결과값 계산 후 결과값을 오름차순으로 정렬하여 수행하여야한다. 이분탐색을 하는 알고리즘을 만들어 적용할 경우 계산된 결과가 많을경우 위의 완전탐색보다 시간이 절약될것으로 예상되지만 우선 완전탐색의 방법으로 이문제를 해결해 보자. (계산식의 결과를 유추할 만한 논리를 만들어놓으면 불필요한 계산은 수행하지 않는 방법을 사용하면 시간이 더 절약될 것으로 예상된다.)

 

다음과 같은 방법으로 문제를 풀어보자.

1.  결과식을 뽑기위해 연산리스트를 만드는 것이 중요하다. 첫번째 변수는 수의 갯수로, for문을 돌릴 때 N +(N-1)번의 루프를 돌려 연산식을 완성시킨다. ==> 연산식을 만드는것이 아닌 바로 연산을 하는것이 유리할듯(앞에서부터 연산규칙)

 

2. 수열은 숫자가 변하지 않으므로 for문 내의 홀수번째 수행일경우 숫자를 연산리스트에 차례대로 추가해준다.

 

3. 3번째 입력은 인덱스 0,1,2,3 => 더하기 빼기 곱하기 나누기로 입력하며 인덱스의 값이 0이 아닌 것중 하나를 랜덤으로 추출한다. (추출한 연산자는 3번째 입력 리스트의 해당 인덱스 -1연산을 수행하여 준다)

 

4. for문이 모두 마치면 연산리스트의 추가되며 연산이 가능한 모든 경우의 수를 구한다.

 

다만, 위의 방식대로 하면 문제점이 있다. 해당 가능한 경우의 수가 몇개가 있는지 모르므로 언제 연산리스트의 생산을 그만두어야 하는지 알지 못한다. (혹시나 모를 경우의 수 때문의 계속 연산리스트를 만들어봐야 한다.)

 

그럼 경우의 수를 어떻게 구할까?

 

하나의 케이스를 생각해보자

[3, 4, 0, 2] 라는 세번쨰 입력을 받게되면

연산자의 자리는 총 9개이다.

더하기가 들어갈 자리의 경우의 수는 9*8*7/3*2*1 이 된다. (맞나?)

이제 남은 자리는 6자리, 빼기가 들어갈 경우의 수는 6*5*4*3/4*3*2*1 이며

곱하기는 0개이므로 자리가 몇개이든 하나의 경우의 수

나누기는 2개이고 남은자리도 2개이므로 무조건 2*1/2*1 =1 이다.(자리가 다정해져있으므로 어처피 1이다.)

 

그럼 [a,b,c,d]의 수열로 바꿔 공식화 해보면

(N*(N-1)...(N-a+1)/(a*(a-1)...1)) * ((N-a)...(N-a-b+1)/(b...1)) * ((N-a-b)...(N-a-b-c+1)/(c...1)) * 1 이된다.(써보니 복잡하네)

 

그럼 두가지 방법이 생긴다.

연산자 만드는 for문은 무진장 돌린다음에 저 경우의 수의 숫자와 일치하면 stop하는 방법과(연산자가 많으면 시간이 오래걸릴 확률이 있다.)

 

+부터 /까지 체계적으로 배치하여 동일한 경우의 수를 만드는 것을 배제하는 방법.

 

아무래도 후자가 좋아보이므로 후자의 알고리즘으로 만들어보자.

 

3번의 랜덤추출을 하는방법을 대신하여 알고리즘을 좀더 체계적으로 구현할 필요가 있어보인다.

 

==> itertools.permutation이라는 API로 쉽게 구현가능.(구현해보려니 만만치 않다.)

 

from itertools import permutations

## 필요 input 요소 추출
def input_(input_list):
    n = input_list[0][0]
    num_list = input_list[1]
    list_3 = input_list[2]

    add = list_3[0]
    sub = list_3[1]
    mul = list_3[2]
    div = list_3[3]

    addList = ['+'] * add
    subList = ['-'] * sub
    mulList = ['*'] * mul
    divList = ['/'] * div
    operatorList = addList + subList + mulList + divList

    return n, num_list, operatorList


# 연산자 경우의 수 조합
def combine_oper(operatorList):
    oper_set = (list(permutations(operatorList)))
    alllist = list(set(oper_set))
    opers_list = list(map(list, alllist))
    return opers_list


# 연산 수행 (oper_list
def operation(num_list, oper_list):
    res = num_list[0]
    idx = 1
    for oper in oper_list:
        if oper == '+':
            res += num_list[idx]
        elif oper == '-':
            res -= num_list[idx]
        elif oper == '*':
            res *= num_list[idx]
        else:
            if res < 0:
                res = -((-res) // num_list[idx])
            else:
                res //= num_list[idx]
        idx += 1
    return res


if __name__ == "__main__":

    input_list = []
    for i in range(3):
        data = list(map(int, input().split()))
        input_list.append(data)

    n, num_list, operatorList = input_(input_list)
    oper_list_combined = combine_oper(operatorList)

    res_list = []
    for opers_list in oper_list_combined:
        res = operation(num_list, opers_list)
        res_list.append(res)
    # max
    print(max(res_list))
    # min
    print(min(res_list))