Skip to content

Latest commit

 

History

History
287 lines (198 loc) · 9.24 KB

200506_완전검색&그리디.md

File metadata and controls

287 lines (198 loc) · 9.24 KB
Raw

완전 검색 & 그리디

  • 반복(Iteration)과 재귀(Recursion)
  • 완전검색기법
  • 조합적 문제
  • 탐욕 알고리즘

1.학습목표

  • 재귀적 알고리즘의 특성을 이해하고 이를 구현하기 위한 재귀 호출에 대해 학습한다.
  • 완전 검색의 개념을 이해하고 완전 검색을 통한 문제해결방법에 대해 학습
  • 조합적 문제(Combinatorial Problems)에 대한 완전 검색 방법에 대해 이해한다.
    • 순열, 조합, 부분집합을 생성하는 알고리즘을 학습한다.
  • 탐욕 알고리즘의 기법의 개념과 주요 특성을 이해한다.

2.반복과 재귀

  • 반복과 재귀는 유사한 작업을 수행할 수 있다.
  • 반복은 수행하는 작업이 완료될 때 까지 계속 반복
    • 루프(for, while 구조)
  • 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
    • 하나의 큰 문제를 해결할 수 있는 더 작은 문제로 쪼개고 결과들을 결합한다.
    • 재귀 함수로 구현
  • 반복 구조
    • 초기화
      • 반복되는 명령문을 실행하기전에 (한번만) 조건 검사에 사용할 변수의 초기값 설정
      • 조건 검사
      • 반복할 명령문 실행
      • 업데이트
        • 무한 루프가 되지않게 조건이 거짓이 되게 한다.
# 반복을 이용한 선택정렬

def selectionSort(A):
    n = len(A)
    
    for i in range(0, n-1):
        min = i
        for j in range(i+1, n):
            if A[j] < A[min]:
                min = j
        A[min], A[i] = A[i], A[min]

  • 재귀적 알고리즘

    • 재귀적 정의는 두 부분으로 나뉜다.
    • 하나 또는 그 이상의 기본 경우 (basis case or rule)
      • 집합에 포함되어 있는 원소로 induction을 생성하기 위한 시드(seed) 역할
    • 하나 또는 그 이상의 유도된 경우(inductive case or rule)
      • 새로운 집합의 원소를 생성하기 위해 결합되어지는 방법

  • 재귀 함수(recursive function)

    • 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
    • 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현한다.
    • 따라서, **기본 부분(basis part) 와 유도 부분(inductive part)**로 구성된다.
    • 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
      • 그러나, 재귀에 대해 익숙하지 않은 개발자들은 재귀적 프로그램이 어렵다고 느낀다.
    • 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 따라서 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다.
# 팩토리얼 재귀 함수의 호출

def factorial(n):
    # 기본 부분
    if n <= 1: 
        return 1
    # 유도 부분
    else: 
        return n * factorial(n-1)

2.1 반복 또는 재귀?

  • 해결할 문제를 고려해서 반복이나 재귀 방법을 선택

  • 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다.

    • 추상 자료형(List, Tree 등) 의 알고맂므은 재귀적 구현이 간단하고 자연스러운 경우가 많다.

  • 일반적으로, 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 한다.

  • 입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다.

2.2 반복과 재귀의 비교

재귀 반복
종료 재귀 함수 호출이 종료되는 베이스 케이스 반복문의 종료 조건
수행 시간 (상대적) 느림 빠름
메모리 공간 (상대적) 많이 사용 적게 사용
소스 코드 길이 짧고 간결 길다
소스코드 형태 선택 구조(if ... else) 반복 구조(for, while)
무한 반복시 스택 오버플로우 CPU를 반복해서 점유
  • 2^k 연산에 대한 재귀와 반복
# 재귀
def Power_of_2(k):
    if k == 0:
        return 1
    else:
        return 2 * Power_of_2(k-1)
    
# 반복
def Power_of_2(k):
	i = 0
	power = 1
	while i < k :
	    power = power * 2
	    i = l + 1
	return power

2.3 연습문제

  • 선택 정렬(SelectionSort) 함수를 재귀적 알고리즘으로 작성해 보시오.

4 3 7 5 => 3 4 5 7

# 재귀를 이용한 선택정렬
def SelectionSort(A, s):
    n = len(A)
    
    if s == n-1:
        return
    min = s
    for i in range(s, n):
        if A[min] > A[i]:
            min = i
    A[s], A[min] = A[min], A[s]
    
    SelectionSort(A, S+1)
    
A = [2, 4, 6, 1, 9, 8, 7, 0]
SelectionSort(A, 0)
print(A)

3. 완전 검색

문제 제시 : baby-gin Game

  • 설명
    • 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.
    • 그리고, 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin이라 부른다.
    • 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.

3.1 고지식한 방법(Brute Force)

  • brute force 는 문제를 해결하기 위한 간단하고 쉬운 접근법이다.
    • Just-do-it
    • force의 의미는 사람(지능)보다는 컴퓨터의 force를 의미한다.
  • brute-force 방법은 대부분의 문제에 적용 가능하다.
  • 상대적으로 빠른 시간에 문제해결(알고리즘 설계)을 할 수 있다.
  • 문제에 포함된 자료(요소, 인스턴스)의 크기가 작다면 유용하다.
  • 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용된다.
# 완전검색
def SequentialSearch(A, k):
    A[n] = k
    i = 0
    while A[i] != k:
        i += 1
    if i < n:
        return i
    else:
        return -1

3.2 완전 검색으로 시작하라

  • 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률 작다.
    • 완전검색은 입력의 크기를 작게 해서 간편하고 빠르게 답을 구하는 프로그램을 작성한다.
  • 이를 기반으로 그리디 기법이나 동적 계획법을 이용해서 효율적인 알고리즘을 찾을 수 있다.
  • 검정등에서 주어진 문제를 풀때, 우선 완전 검색으로 접근하여 해답을 도출한후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

3.3 완전 검색을 통한 Baby-gin 접근

  • 고려할 수 있는 모든 경우의 수 생성하기

    • 6개의 숫자로 만들 수 있는 모든 숫자 나열 (중복포함)

    • 예) 입력으로 [2, 3, 5, 7, 7, 7] 받았을 경우, 아래와 같이 순열 생성 가능

      • # 모든 경우의 순열 나열
2 3 5 7 7 7
2 3 7 5 7 7
2 3 7 7 5 7
...
7 7 7 5 3 2

  • 해답 테스트하기

    • 앞의 3자리와 뒤의 3자리를 잘라, run 과 triplety 여부를 테스트하고 최종적으로 베이진을 판단한다.
    • 예) [2, 3, 5, 7, 7, 7] => baby-gin 아님

3.4 완전 검색

  • 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것이다.

  • 또한, 이들은 전형적으로 순열(Permutation), 조합(Combination), 그리고 부분집합(subsets)과 같은 조합적문제들 (Combinatorial Problems) 과 연관된다.

  • 완전 검색은 조합적 문제에 대한 Brute-Force 방법이다.

  • 문제의 이해 ( 5188. 최소합 )

    • NxN 칸에 숫자가 적힌 판

    • 맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램

    • 예)

      • 1 2 3
        2 3 4
        3 4 5

      1, 2, 3, 4, 5 순으로 움직이고 최소합계는 15

# swea 5188_최소합 문제
import sys
sys.stdin = open('input.txt')

def find(r, c, s):
    global minV
    if r == N-1 and c == N-1: # 목적지 도착
        if minV > s+m[r][c]:
            minV = s + m[r][c]

    # 백트래킹
    elif minV <= s: # 목적지 도착전에 이미 다른
        return # 이동을 중단하고 다른 경로로

    else:
        if r+1 < N: # 아래로 이동 가능한지 확인
            find(r+1, c, s+m[r][c])
        if c+1 < N: # 오른쪽으로 이동 가능한지 확인
            find(r, c+1, s+m[r][c])

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    m = [ list(map(int, input().split())) for _ in range(N) ]

    minV = 100000
    find(0, 0, 0)
    print('#{} {}'.format(tc, minV))