이미지 보기

[Algorithm] 알고리즘 설계 기법 : 완전 탐색, 순열, 탐욕 알고리즘

여러 알고리즘 설계 기법에 대해 알아보자.

22.02.10 작성

읽는 데 8분

완전 탐색(Executive Search)

고려할 수 있는 모든 경우의 수에 대해 나열해서 확인하는 방법이다.
가장 기본적인 접근 방법이다.
Brute-force or generate-and-test 기법이라고 불린다.
일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
수행 속도는 느리지만 해답을 찾아낼 확률이 높다.
우선 완전 탐색으로 접근하여 해답 도출 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직

순열(Permutation)

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
서로 다른 n개 중 r개를 택하는 순열은 nPr과 같이 표현한다.
nPr = n * (n-1) * (n-2) * ... * (n - (r-1))
nPn = factorial, 즉 n!이라고 부른다.
3을 포함하는 모든 순열을 생성하는 함수

for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1:
            for i3 in range(1, 4):
                if i3 != i1 and i3 != i2:
                    print(i1, i2, i3)

탐욕(Greedy) 알고리즘

최적해를 구하는 데에 사용되는 근시안적 방법. 가장 적은 비용과 횟수를 생각. 한 마디로 가성비!
여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근

동작 과정

해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 집합(Solution Set)에 추가
실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인. 즉, 문제의 제약 조건을 위배하지 않는지 검사.
해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인. 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작.

예시 : 거스름돈 줄이기

문제

어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

1단계 : 해 선택

가장 좋은 해를 선택한다. 단위가 클수록 개수가 줄어들므로 현재 가장 단위가 큰 지폐를 골라 거스름돈을 준다.

2단계 : 실행 가능성 검사

거스름돈이 손님에게 드려야 할 액수를 초과하는지 확인. 초과한다면 마지막에 추가한 지폐를 거스름돈에서 빼고, 1단계로 되돌아가서 한 단계 작은 단위의 동전으로 진행한다.

3단계 : 해 검사

해는 당연히도 손님에게 내드려야 하는 액수와 일치해야 한다.

Baby-Gin

0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속인 경우를 run, 3장의 카드가 동일한 경우 triplet이라고 한다. 그리고 6장의 카드가 run과 triplet으로만 구성된 경우를 baby-gin이라고 부른다.

완전 탐색 알고리즘 사용

입력 받은 6개의 숫자로 고려할 수 있는 모든 경우의 수를 생성한다. (위에서 순열을 생성하는 방식처럼) 그리고 앞의 3자리와 뒤의 3자리를 잘라 run과 triplet 여부를 테스트하여 baby-gin을 판단한다.

Greedy 알고리즘 사용

num = 456789 # Baby Gin 확인할 6자리 수

# 6자리 수로부터 각 자리 수를 추출하여 개수를 누적할 카운트 리스트
c = [0]*12  # (1)

# count 배열 c 항목 채우기
for i in range(6):
    c[num % 10] += 1
    num //= 10

# num의 길이를 모를 때
while num > 0:
    c[num % 10] += 1
    num //= 10

입력받은 숫자 문자열을 하나하나 떼서 정수형으로 바뀐 뒤 list로 저장하여 counts 변수 배열을 만드는 것이 아니라, 숫자 문자열 자체를 정수형으로 형변환하고 이를 10으로 나눈 나머지를 매번 counts 변수의 해당하는 인덱스에 추가하는 것이다.

i = 0
tri = run = 0

while i < 10:
    # tri 조사 후 해당하면 데이터 삭제
    if c[i] >= 3:
        c[i] -= 3
        tri += 1
        continue    # (2)

    # run 조사 후 해당하면 데이터 삭제
    if c[i] >= 1 and c[i+1] >= 1 and c[i+2] >= 1:
        c[i] -= 1
        c[i+1] -= 1
        c[i+2] -= 1
        run += 1
        continue    # (2)
    i += 1

if run + tri == 2:
    print("Baby Gin")
else:
    print("Lose")

(1) c를 12개로 초기화하는 이유는 run 조사 때 조사 범위 따로 설정하지 않으려고 뒤에 비어있는 0을 2칸 더 넣는 것이다. (10+2) 이 과정이 없으면 IndexError가 발생한다.
(2) if 문에 continue가 있는 이유는 해당 i에 대해서 다시 tri이나 run을 조사하기 위해 i+=1 없이 반복 종료

주의해야 할 점

입력받은 숫자를 정렬한 후, 앞 뒤 3자리씩 끊어서 run 및 triplet을 확인하는 방법을 고려할 수도 있다. [6, 4, 4, 5, 4, 4] 같은 경우 정렬하면 확인할 수 있지만, [1, 2, 3, 1, 2, 3] 같은 경우에는 정렬하면 오히려 확인에 실패한다.

위처럼 탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우가 있으니 주의하도록 한다.

FE Developer 박승훈

노력하는 자는 즐기는 자를 이길 수 없다

Github