[알고리즘] 재귀용법, 동적계획법과 분할 정복, 이진탐색, 순차 탐색,백트랙킹,탐욕 알고리즘

Photo by Michael Dziedzic on Unsplash

 

*** 아래의 내용은 패스트 캠퍼스 알고리즘 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***

1. 재귀 용법 (recursive call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

예제 — 시간 복잡도와 공간 복잡도

• factorial(n) 은 n — 1 번의 factorial() 함수를 호출해서, 곱셈을 함
• 일종의 n-1번 반복문을 호출한 것과 동일
• factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

 

* 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기

n! = n X (n - 1)!
함수를 하나 만든다.
함수(n) 은 n > 1 이면 return n X 함수(n - 1)
함수(n) 은 n = 1 이면 return n

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return num

 

 

* 재귀 호출의 일반적인 형태

일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

일반적인 형태2
 def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

 

재귀 호출은 스택의 전형적인 예

• 함수는 내부적으로 스택처럼 관리된다.

2. 동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)

(1) 정의

1)동적계획법 (DP 라고 많이 부름)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• Memoization 기법을 사용함
• Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
• 예: 피보나치 수열

* 피보나치 수열을 재귀용법과 동적 계획법으로 각각 구현하기

재귀용법
def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)




동적계획법
def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

2) 분할 정복

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
• 일반적으로 재귀함수로 구현
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
• 예: 병합 정렬, 퀵 정렬 등

 

(2) 공통점과 차이점

1)공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

2)차이점

동적 계획법

• 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
• Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

분할 정복

• 부분 문제는 서로 중복되지 않음
• Memoization 기법 사용 안함

3. 순차탐색

(1) 순차 탐색 (Sequential Search) 이란?

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

(2) 알고리즘 분석

• 최악의 경우 리스트 길이가 n일 때, n번 비교해야 함
• O(n)

4. 이진탐색

(1) 이진 탐색 (Binary Search) 이란?

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

(2) 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기)

 

[저작자] by penjee.com

(3) 분할 정복 알고리즘과 이진 탐색

1) 분할 정복 알고리즘 (Divide and Conquer)

• Divide: 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.

2) 이진 탐색

• Divide: 리스트를 두 개의 서브 리스트로 나눈다.
• Comquer
• 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
• 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

(4) 알고리즘 분석

• n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행
• 빅 오 표기법으로는 k + 1 이 결국 최종 시간 복잡도임 (1이 되었을 때도, 비교연산을 한번 수행)
• 결국 O(logn + 1) 이고, 2와 1, 상수는 삭제 되므로, O(logn)

5. 백트랙킹

1) 백 트래킹 (backtracking)

• 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름
• 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략
• 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법
• 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현
• 각 후보군을 DFS 방식으로 확인
• 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
• Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
• Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
• 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)

상태 공간 트리 (State Space Tree)

• 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

2)N Queen 문제 이해

• 대표적인 백트래킹 문제
• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
• 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 함

3)Pruning (가지치기) for N Queen 문제

• 한 행에는 하나의 퀸 밖에 위치할 수 없음 (퀸은 수평 이동이 가능하므로)
• 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치
• 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸들이 이동할 수 없는 위치가 없을 경우에는, 더 이상 퀸을 배치하지 않고, 이전 행의 퀸의 배치를 바꿈
• 즉, 맨 위의 행부터 전체 행까지 퀸의 배치가 가능한 경우의 수를 상태 공간 트리 형태로 만든 후, 각 경우를 맨 위의 행부터 DFS 방식으로 접근, 해당 경우가 진행이 어려울 경우, 더 이상 진행하지 않고, 다른 경우를 체크하는 방식

4)Promising for N Queen 문제

• 해당 루트가 조건에 맞는지를 검사하는 기법을 활용하여,
• 현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 다음과 같은 조건으로 확인
• 한 행에 어차피 하나의 퀸만 배치 가능하므로 수평 체크는 별도로 필요하지 않음

6. 탐욕 알고리즘

(1) 탐욕 알고리즘 이란?

• Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식

(2) 탐욕 알고리즘 예

문제1: 동전 문제

• 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
• 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

문제2: 부분 배낭 문제 (Fractional Knapsack Problem)

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
• 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
• 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름
• Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름)

(3) 탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용
• 반드시 최적의 해를 구할 수 있는 것은 아니다.
• 최적의 해에 가까운 값을 구하는 방법 중의 하나임

예

 

• ‘시작’ 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 시에
• Greedy 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19 가 됨
• 하지만 실제 가장 작은 값은 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 답

** 위의 내용은 패스트 캠퍼스 알고리즘 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***