[이솦] 파이선으로 배우는 AI 기초 19

국밥맨의 IT& 교육2024-08-22 23:28

컴퓨터 프로그램은 우리가 가진 문제를 해결하는데 사용하기 위해 만들어졌다. 수학 문제외에도 다양한 문제들을 해결하기 위한 것이다. 인터넷 검색이라는 문제를 생각해 보자. 어떤 키워드를 검색하면 나오는 검색 페에지의 노출 순서는 어떻게 정해질까? 구글 이나 네이버등 검색결과를 보여주는 방식은? 그 순간에 검색하는것이 아니라. 미리 검색해 놓은 결과치를 보여 주는것이다. 그렇지 않으면 검색 결과를 보여 주는게 너무 느릴것이다.

그렇다면 검색 검색 결과를 보여주는 순서는 어떻게 될까? 상위순서는 가장 많은 검색 단어를 포함한 웹페이지라고 생각할수 있는데 오래전 검색 엔진방식이다. 하지만 내용없이 검색 단어만 많다면 필요로 하는 웹페이지가 아닐수 있다.

구글에서는 페이지 랭크라는 웹페이지 알고리즘을 사용한다. 다른 웹사이트의 링크를 많이 받는 웹사이트를 우선순위로 생각하는 검색 순위 알고리즘이다. 즉 참조하는 횟수가 많은 페이지를 우선순위로 둔다. 이것만 쓰는건 아니지만 페이지랭크 방식으로 검색 결과의 만족도를 높였다.

이처럼 알고리즘은 주어진 문제를 논리적으로 해결하기 위해서 필요한 절차, 방법, 명령어들을 모아 놓은 것이다. 사실 알고리즘은 광범위한 개념이다. 인공지능에서도 문제 해결을 위한 다양한 알고리즘을 사용한다.

오늘은 알고리즘이 무엇이고 어떤 종류의 알고리즘있는지 알아보고 기초 알고리즘인 정렬 알고리즘, 탐색 알고리즘을 알아보자.

알고리즘

알고리즘은 주어진 문제를 논리적으로 해결하기 위해서 필요한 절차, 방법, 명령어들을 모아 놓은것

넓게는 사람 손으로 해결하는것, 컴퓨터로 해결하는것, 수학적인것, 비수학적인것 모두를 포함함

알고리즘은 아라비아 숫자를 이용해서 최초로 사칙연산을 만든 페르시아 수학자 알콰리즈미의 이름에서 유래했다.

컴퓨터를 위한 알고리즘은 당연히 컴퓨터가 이해할수 있는 용어로 기술해 줘야 한다. 이때 알고리즘을 컴퓨터에서 필요한대로 기술하는 능력, 즉 컴퓨터 입장에서 명령을 구성하는 능력을 컴퓨팅 사고라고 한다.

전통적 인공 지능 문제를 하나 해결해 보자.

농부가 늑대, 양, 양배추를 강 건너로 옮기는 게임이다. 조건: 배에는 한개의 개체만 태울수 있다. 늑대와 양, 양과 양배추는 농부없이 같이 주면 안된다. 어떻게 하면 모두 무사하게 강을 건널수 있을까? 설명하지 못하겠다면

경우의 수를 나태는 전산학적 방법인 트리 형태로 표현할수 있다. 시작하면 강을 건너는 모든 방법을 적는다. 4개의 개체 즉 농부, 늑대, 양, 양배추의 모든 경우의 수를 정리한다.

예를들어 농부가 처음 강을 건너는 방법은 1. 양을 옮긴다. 2 늑대를 옮긴다. 3 양배추를 옮긴다. 4. 혼자 건너간다가 있다. 여기에서 양을 옮기는거 말고는 다음을 기약할수가 없다. 이런식으로 모든 경우의 수를 정리하다 보면 언젠가는 정답의 길을 찾을수 있다.

해답을 찾기 위해 모든 경우의 수를 빠짐없이 탐색할 방법이 필요하다. 트리가 매우 복잡하다고 가정해 보자. 트리안의 모든 경우의 수를 방문할 체계적인 방법이 필요하다.

트리를 탐색하는 알고리즘은 크게 2가지가 있다.

깊이 우선 탐색
너비 우선 탐색

깊이 우선 탐색은 한 방향으로 계속 가는 방법이다. 가보다가 막혀 있다면 바로 직전으로 와서 다음 방향으로 가보는 방법이다. 너비 우선 탐색은 지금 갈수 있는 칸에서 전체적으로 한칸만 가보는것이다. 그리고 다 가봤다면 그중 한 지점을 택하고, 다 가보는 것이다. 이렇게 하면 모든 지점을 빠지지 않고 가볼수 있게 된다. 알파고의 탐색도 상내가 놓은 다음에 내가 놓을수 이는 가장 좋을 수를 탐색하는 방법이다. 다만 모든 수를 다 하기에는 경우의 수가 너무 많아서 머신러닝을 통해 경험을 통해서 자동으로 개선하는 컴퓨터 알고리즘을 통해서 발전해 간다.

이렇게 컴퓨터가 문제를 해결하는 방법을 알고리즘 이라고 한다.

알고리즘 분류

컴퓨터는 수많은 알고리즘을 사용하며 알고리즘은 설계 기법에 따라서 4개로 분류가 가능하다.

분할정복
동적 계획법
탐욕적 방법
백트레킹

이렇게 4가지가 있다.

분할 정복 (divide and conquer)

merge sort,

quick sort,

binery search,

Straseen's Matrix Multiplication,

closest pair point 가 있으며 그대로 해결할수 없는 문제를 작은 문제로 잘게 나눠어 해결하는 방법이다.

동적 계획법( Dynamic Programming)

fibonacci number series,

knapsack problem,

tower of hanoi,

all pair shortest path by floyd-warshall,

shortest path by digktra,

prokext scheduling,

0/1 knapsack problem.이 있으며 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고 과거에 구했던 답을 활용하는 방법이다.

탐욕적 알고리즘 ( greedy algorithm)

Huffman code
Travelling Salesman Problem
Prim's Minimal Spanning Tree Algorithm
Kruskal's Minimal Spanning Tree Algorithm
Dijkstra's Minimal Spanning Tree Algorithm
Graph - Map Coloring
Graph - Vertex Cover
Job Scheduling Problem
Machine scheduling
Fractional Knapsack Problem
Activity Selection Problem

문제가 여러 단계로 구성되어 있는 경우에 단계별 최적 해답을 구함으로 전체 문제를 해결하는 방법이다. 항상 선택의 입장에서 가장 좋은 것을 선택하는 것이다.

백트레킹 ( backtracking)

backtracking

N queens

현재 상태에서 가능한 모든 후보군을 따라 들어가면서 해결책에 대한 후보를 구축해 나가는 방법이다.

각각의 방법은 장단점이 있다.

동적 계획법의 단점은 시간이 많이 걸릴수 있다.

탐욕적 방법은 순간의 선택이 최선이 아닐수 있다.

정렬 알고리즘

어러개가 있지만, 그중 매우 빠른 속도 때문에 많이 사용하는 알고리즘인 퀵정렬을 살펴보자.

초기상태 538491627 을

오름 차순인 123456789로 정렬을 해보자.

먼저 비벗을 정해줘야 한다. 피벗은 배열안에서 임의의 요소를 피벗 ( pivot) 이라고 부른다. 피봇은 나눌 값인데 일단 가장 앞에 있는 값을 이용한다. 5을 사용한다. 피벗을 기준으로 작은것은 왼쪽으로 큰것은 오른쪽을 이동시킨다. 그럼 5를 기준으로 나눠진 값들 중에서 다시 첫번째 숫자를 피벗으로 해서 다시 정렬 한다. 이제 더이상 반복할수 없을 때까지 하면 오름 차순으로 완성이 된다.

그럼 이방법은 앞선 알고리즘 분류중 어디에 속할까? 잘게 나누어 해결하는 분할 정복에 속한다.

퀵정렬은 정렬 속도가 빨라서 자료를 정렬해야 할때 널리 사용되고 있다.

오늘은 재미 있는 알고리즘을 적용할 것이다.

동전이 있다고 가정해 보자. 500원, 100원, 50원, 10원 동전을 1440원을 가장 적은 갯수의 동전으로 거슬러 주는 방법은? 각각의 동전을 써서 10개의 동전으로 금액을 만들수 있다.

def min_coin(value, coin_list):
    count = 0 
    for coin in coin_list:
        count += (value // coin) 
        value = value % coin 
    return count

먼저 min_coin이라는 함수를 만들고 매개변수를 value 와 coin list를 넣어보자.

value는 거슬러 줘야 할 값이고, coin list는 사용할수 있는 코인 갯수이다. 이때 coin-list속 코인은 큰 액수 부터 정렬이 되어 있다고 가정해보자. count는 반복해 주는 것이고 그 후에 반복문이 나온다. 하나씩 가져와서 value인 1440원을 500원으로 나눠 보자. 2가 나오면 2는 count로 저장된다. %연산자를 통해서 나머지는 계속 나누게 된다.

위 방법은 알고리즘 중에서 어떤것에 속하는가? 단계별 최적의 답을 구하는 탐욕적 방법이다.

실습

내가 가진 돈이 500만원이라고 하고 10개의 주식을 산다고 가정하고 각 주식의 금액은 다르다고 가정하자. 그중 3가지를 구매하되 500만원에 가장 근접하게 구매 해보자.

어떻게 하면 될까?

첫번째 선택에서 10의 주식 각각을 선택할수 있는 모든 경우를 계산하고 두번째 선택에서 두번째 주식을 선택할수 있는 모든 경우, 세번째 선택에서는 세번째 주식을 선택할숭 씨는 모든 경우를 계산해 보자. 이 모든 경우의 수를 계산하고 500만원에 가장 가까운 경우의 수를 찾는다.

이 내용을 search() 함수를 통해서 구현해 보자.

# 최대값
goal=5000000  
# 오늘 구매가능한 주식의 가격
pref = [3416918, 1068641, 1061440, 652845, 650599, 565392, 542713, 21642, 506494, 489202]
# 500만원에 가장 가까운 주식의 합가격
min_total = 0  
# 두 값을 저장하는 임시 변수
local_temp=0
# 세개의 주식 가격 인덱스를 저장
local_index1 = 0
local_index2 = 0
local_index3 = 0

def search(total, pos):
    global min_total, local_temp, local_index1, local_index2, local_index3 

    if pos>= len(pref):
        return
    if total < goal:  
        if abs(goal - (total + pref[pos])) < abs(goal - min_total):  
            min_total = total + pref[pos]
            local_temp = total
            local_index1 = pos
            search(total+pref[pos],pos+1 ) 
            search(total, pos+1)
            for local_index2 in range(len(pref)):
                for local_index3 in range(len(pref)):
                    if local_temp - pref [local_index2] == pref [local_index3]:
                        break
                break
search(0, 0)
print (min_total)
print (pref [local_index1])
print (pref [local_index2])
print (pref [local_index3])

이 코드는 주어진 목표 금액(500만원)에 가장 가까운 주식 가격의 합을 찾는 알고리즘을 구현한 것입니다. 주어진 주식 가격 목록 pref에서 세 개의 주식을 선택해 그 합이 목표 금액과 가장 가까운 경우를 탐색합니다. 각 부분을 자세히 설명하면 다음과 같습니다.
1. 변수 설정
goal = 5,000,000: 목표 금액인 500만원을 의미합니다.
pref = [3416918, 1068641, 1061440, 652845, 650599, 565392, 542713, 21642, 506494, 489202]: 오늘 구매 가능한 주식의 가격 목록입니다.
min_total = 0: 현재까지 찾은 주식 가격 합 중에서 목표 금액에 가장 가까운 값을 저장합니다.
local_temp = 0: 탐색 도중 임시로 주식 가격 합을 저장하는 변수입니다.
local_index1, local_index2, local_index3 = 0: 선택된 세 개의 주식 가격의 인덱스를 저장하는 변수입니다.
2. search 함수
이 함수는 재귀적으로 탐색을 진행하며, 주식 가격의 합이 목표 금액에 가장 근접한 조합을 찾습니다.
매개변수:
total: 현재까지 선택한 주식의 가격 합입니다.
pos: 현재 탐색 중인 주식 가격의 인덱스입니다.
기능:
if pos >= len(pref): 주식 목록을 모두 탐색한 경우 함수가 종료됩니다.
if total < goal: 현재 선택한 주식의 가격 합이 목표 금액보다 작은 경우 조건문 안의 로직이 실행됩니다.
if abs(goal - (total + pref[pos])) < abs(goal - min_total): 현재까지의 가격 합이 목표 금액과 더 가까워졌다면 min_total을 업데이트하고, 관련 변수들을 갱신합니다.
search(total + pref[pos], pos + 1): 현재 주식을 포함해 다음 주식으로 탐색을 진행합니다.
search(total, pos + 1): 현재 주식을 포함하지 않고 다음 주식으로 탐색을 진행합니다.
마지막 for 루프는 두 주식 가격의 합이 동일한 경우를 찾는 로직이지만, 실제로는 제대로 작동하지 않을 가능성이 있습니다.
3. 결과 출력
탐색이 완료되면 min_total 값과 선택된 주식 가격의 인덱스에 해당하는 주식 가격을 출력합니다.

요약

알고리즘은 문제를 해결하기 위한 절차를 표현하는것

컴퓨터 알고리즘을 특징에 따라서 분류하면 분할정복, 탐욕적방법 동적 계획법, 백트레킹으로 나눌수 있다.

자료를 정리할때 사용하는 퀵 정렬은 분학 정복 알고리즘이다.

동전교환에서는 탐욕적 방법이 적합하듯이 문제에 따라서 적잡한 알고리즘이 있다.

알고리즘의 장단점에 대해서 다 알아보자.

1. 분할정복(Divide and Conquer)
개념: 문제를 더 작은 부분 문제들로 나누고, 각 부분 문제를 해결한 후 그 결과를 합쳐서 전체 문제를 해결하는 방식입니다.
장점:
문제를 더 작은 부분 문제로 나누기 때문에 해결이 더 쉬운 경우가 많습니다.
병렬 처리 및 재귀적 구조에서 강점을 보이며, 알고리즘의 성능을 향상시킬 수 있습니다.
대표적인 예로 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
단점:
재귀적으로 문제를 풀기 때문에 함수 호출 오버헤드가 발생할 수 있습니다.
일부 문제에서는 중복 계산이 발생할 수 있어 비효율적일 수 있습니다.
각 부분 문제를 해결하고 결과를 합치는 과정이 복잡할 수 있습니다.
2. 탐욕적 방법(Greedy Algorithm)
개념: 현재 상황에서 최선의 선택을 함으로써 전체 문제를 해결하는 방법입니다. 각 단계에서 최적의 해를 선택하는 방식입니다.
장점:
구현이 간단하고 직관적입니다.
시간 복잡도가 낮은 경우가 많아, 빠른 해결이 가능합니다.
최적 부분 구조를 가지는 문제(예: 최단 경로 문제)에서는 최적의 해를 구할 수 있습니다.
단점:
항상 최적의 해를 보장하지 않으며, 일부 경우에는 최적해가 아닌 근사해를 제공할 수 있습니다.
문제의 성격에 따라 탐욕적 방법이 전혀 적용되지 않을 수 있습니다.
문제의 특성을 잘 분석해야만 사용이 가능하며, 실패 시 결과가 크게 어긋날 수 있습니다.
3. 동적 계획법(Dynamic Programming)
개념: 문제를 부분 문제로 나누고, 각 부분 문제의 결과를 저장해 중복 계산을 피하는 방식입니다. 주로 하위 문제의 최적 해를 이용해 상위 문제를 해결합니다.
장점:
중복 계산을 피함으로써 시간 복잡도를 크게 줄일 수 있습니다.
분할정복법의 중복 계산 문제를 해결할 수 있습니다.
최적화 문제에서 전역 최적해를 보장할 수 있는 경우가 많습니다. 예를 들어, 피보나치 수열, 배낭 문제 등이 있습니다.
단점:
많은 경우 메모리를 많이 사용하게 됩니다. 메모이제이션이나 테이블 저장을 위해 추가적인 공간이 필요합니다.
알고리즘이 복잡할 수 있으며, 문제의 성질을 잘 이해하지 않으면 적용하기 어렵습니다.
문제를 하위 문제로 분할하고 그 결과를 사용하는 방법을 설계하는 과정이 까다로울 수 있습니다.
4. 백트래킹(Backtracking)
개념: 가능한 모든 해를 탐색하는 방식으로, 조건에 맞지 않는 경로가 발견되면 되돌아가서 다른 경로를 탐색하는 방식입니다. 완전 탐색의 일종으로, 가지치기를 통해 비효율적인 탐색을 줄일 수 있습니다.
장점:
모든 가능한 해를 탐색하기 때문에 해가 존재한다면 반드시 찾아낼 수 있습니다.
가지치기를 통해 탐색 공간을 줄일 수 있어 성능을 개선할 수 있습니다.
대표적으로 N-Queen 문제, 퍼즐 문제 등이 있습니다.
단점:
시간 복잡도가 매우 높을 수 있습니다. 최악의 경우에는 가능한 모든 경우를 탐색해야 하므로 비효율적일 수 있습니다.
문제에 따라 탐색 공간이 매우 커질 수 있으며, 이에 따라 성능 문제가 발생할 수 있습니다.
문제에 대한 직관적인 최적화 기법이 없을 경우, 시간이 많이 걸릴 수 있습니다.
요약 비교
분할정복: 문제를 분할해 병렬 처리 및 재귀적으로 해결할 수 있지만, 중복 계산이 발생할 수 있음.
탐욕적 방법: 간단하고 빠르지만 항상 최적해를 보장하지는 않음.
동적 계획법: 중복 계산을 피해 최적해를 보장하지만 메모리 사용량이 많음.
백트래킹: 해를 반드시 찾을 수 있지만, 시간 복잡도가 높아 비효율적일 수 있음.

위 주식의 값을 계산하는건 백트레킹 알고리즘을 사용했다.

[이솦] 파이선으로 배우는 AI 기초 19