모두의 알고리즘 with Python

gimmicks_u·2022년 4월 2일
0
post-thumbnail

[첫째마당] 알고리즘 기초

1부터 n까지 연속된 숫자의 합을 구하는 알고리즘

  1. 첫 번째 방법
def sum_n(n):
    a = 0
    for i in range(1, n+1):
        a = a + i
    return a

print(sum_n(10))
print(sum_n(100))
55
5050

for문을 이용하여 a에 저장된 값을 하나씩 늘려가는 방법이다.

  1. 두 번째 방법
def sum_n(n):
    return n * (n + 1) // 2

print(sum_n(10))
print(sum_n(100))
55
5050

등차수열의 합을 구하는 공식인
k=0nk=\displaystyle\sum_{k=0}^{n}{k}= n(n+1)2n(n+ 1)\over 2 을 이용하여 간단하게 작성할 수 있다.

첫 번째 방법은 입력값 nn이 커질수록 덧셈을 많이 반복하지만, 두 번째 방법은 nn값의 크기와 관계없이 연산을 한번씩만 하면 답을 얻을 수 있기 때문에 더욱 좋은 방법이다.

이렇게 주어진 문제를 푸는 여러 가지 방법 중 어떤 방법이 더 좋은 것인지 판단할 때 필요한 것이 '알고리즘 분석' 이다

계산 복잡도

어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도(complexity)' 라고 한다. 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그 중 대문자 O표기법을 많이 사용한다(빅 오 표기법)

첫 번째 알고리즘은 입력크기 nn에 대해 사칙연산을 n번 해야한다. 이 때 이 알고리즘의 계산 복잡도를 O(n)O(n)이라고 표현한다. 필요한 계산 횟수가 입력 크기에 '정비례' 할 때 O(n)O(n)이라고 표현한다.

두 번째 알고리즘은 입력 크기 n과 무관하게 사칙연산을 세 번해야 한다. 이 때 알고리즘의 계산 복잡도는 O(1)O(1)로 표현한다.

  • O(n)O(n) : 필요한 계산 횟수가 입력 크기 nn과 비례할 때
  • O(1)O(1) : 필요한 계산 횟수가 입력 크기 nn과 무관할 때

최댓값을 찾는 알고리즘

def find_max(a):
    max_v = a[0]
    for i in range(1,len(a)):
        if a[i] > max_v:
            max_v = a[i]
    return max_v

리스트의 첫 번째 값을 저장해놓고, 다음 값을 첫 번째 값과 비교해 크다면 max_v에 할당하여 최댓값을 찾는 알고리즘이다.

이 알고리즘 또한 입력 크기가 nn일 때 계산은 정비례관계에 있기 때문에, 계산복잡도를 O(n)O(n)으로 표현할 수 있다.

최댓값의 위치를 구하는 알고리즘

def find_max_idx(a):
    max_idx = 0
    for i in range(1,len(a)):
        if a[i] > a[max_idx]:
            max_idx = i
    return max_idx

동명이인을 찾는 알고리즘

name = ["Tom", "Jerry", "Mike", "Tom"]

def find_same_name(a):
    n = len(a)
    result = set()
    for i in range(0, n - 1): #마지막은 비교할 필요가 없음
        for j in range(i + 1, n):  
            if a[i]==a[j]:
                result.add(a[i])
    return result

n번째 이름을 마지막까지 같은지 차례차례 비교하고, 같은 이름이 있다면 result 집합에 추가한다. 마지막은 비교하지 않아도 되기 따문에, 두 번째 for문의 범위는 range(i+1, n)이 된다.

이 경우 계산복잡도는, 입력크기(이름 숫자) nn에 대해
0+1+2+...(n1)0+1+2+...(n-1)번이다, 이를 등차수열의 합으로 계산하면
12n2+12n{1\over2}n^2+{1\over2}n번이 된다. 결국 nn의 제곱에 비례해서 계산시간이 변하는 것이 핵심이기 때문에, 계산복잡도를 O(n2)O(n^2)으로 표현할 수 있다.

연습문제

#1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램
def pow_sum1(n):
    a = 0
    for i in range(1, n+1):
        a = a + i ** 2
    return a

def pow_sum2(n):
    return n * (n + 1) * (2 * n + 1) // 6
#숫자 n개를 리스트로 입력받아 최솟값을 구하는 프로그램
lst = list(map(int, input().split()))

deffind_min(a):
    min_v = a[0]
    for i in range(1,len(a)):
        if a[i] < min_v:
            min_v = a[i]
    return min_v

print(find_min(lst))
#n명 중 두 명을 뽑아 짝을 지을 수 있는 모든 조합을 출력하는 프로그램
lst = ["Tom", "Jerry", "Mike"]

def pair_name(a):
    n = len(a)
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            print(a[i], "-", a[j])

print(pair_name(lst))

[둘째마당] 재귀 호출

팩토리얼을 구하는 알고리즘

def fact_1(n):
    f = 1
    for i in range(1, n + 1):
        f = f * i
    return f
def fact_2(n):
    if n <=1 :
        return 1
    return n * fact_2(n - 1)

fact_2 함수는 n!=n(n1)!n!=n*(n-1)! 의 성질을 이용하여 작성한 재귀호출 코드이다. 반복문을 이용한 알고리즘과 재귀 호출을 이용한 알고리즘의 계산복잡도는 모두 O(n)O(n)이다.

최대공약수 알고리즘

def gcd_1(a, b):
    i = min(a, b)
    while True:
        if a % i == 0 and b % i == 0:
            return i
        i = i - 1
def gcd_2(a,b):
    if b == 0:
        return a
    return gcd_2(b, a 5 b)

gcd_1 코드는 두 수 중 더 작은 값을 놓고 1씩 줄여가며 공통된 약수인지 비교해보는 코드이다. gcd_2 코드는 유클리드 알고리즘을 이용한 코드인데, 수학자 유클리드가 생각해낸 최대공약수의 성질에 따라 작성한 코드이다.

a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)

하노이의 탑 옮기기

원반이 n개인 하노이의 탑 옮기기 (출발점 from, 도착점 to, 보조 aux)

# 하노이이의 탑 알고리즘
def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:
        print(from_pos, "->", to_pos)
        return

    hanoi(n - 1, from_pos, aux_pos, to_pos) # 원반 n-1개를 2번 기둥으로 이동
    print(from_pos, "->", to_pos) # 가장 큰 원반을 3번 기둥으로 이동
    hanoi(n - 1, aux_pos, to_pos, from_pos) # 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 이동
    
  1. 원반이 한개면 그냥 옮기면 끝(종료조건)
  2. 1번 기둥에있는 n-1개를 2번 기둥으로 옮기기
  3. 1번 기둥에 있는 가장 큰 원반을 3번으로 옮기기
  4. 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮기기

탑의 층수가 높을수록 원반을 더 많이 움직여야 한다. nn층의 탑을 옮기려면 원반을 모두 2n12^n-1번 옮겨야 하는 것을 알 수 있으므로, 계산복잡도를 O(2n)O(2^n)으로 나타낼 수 있다.

연습문제

# 1부터 n까지의 합 구하기(재귀 호출)
def Q4_1(n):
    if n <=1 :
        return 1
    return n + Q4_1(n-1)

# 숫자 n개 중에서 최댓값 찾기
def Q4_2(a):
    n = len(a)
    if n <= 1:
        return a[0]
    max_tmp = Q4_2(a[0:n-1])
    if max_tmp > a[n-1]:
        return max_tmp
    else:
        return a[n-1]

# 피보나치 수열
def Q5_1(n):
    if n <= 1:
        return  n
    return Q5_1(n-1) + Q5_1(n-2)

[셋째마당] 탐색과 정렬

순차 탐색 알고리즘

def serch_list(a,x);
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            return i
    return -1

주어진 리스트에서 특정값의 위치를 찾아 돌려주는 알고리즘

선택정렬

#1
def find_min_idx(a):
    n = len(a)
    min_idx = 0
    for i in range(1, n):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def sel_sort(a):
    result = []
    while a:
        min_idx = find_min_idx(a)
        value = a.pop(min_idx)
        result.append(value)
    return result
    
#2
def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

선택정렬은 리스트의 최솟값을 하나씩 빼서 새로운 리스트에 넣어 정렬하는 방법이다. 계산복잡도 : O(n2)O(n^2)

삽입정렬

#1
def find_ins_idx(r, v):
    for i in range(0, len(r)):
        if v < r[i]:
            return i
    return len(r) # 찾아서 없으면 맨 뒤

def ins_sort(a):
    result = []
    while a:
        value = a.pop(0) # 리스트에서 한개 꺼내서 
        ins_idx = find_ins_idx(result, value) # 값이 들어갈 위치를 찾아
        result.insert(ins_idx, value) # 찾은 위치에 삽입 
    return result
    
#2
def ins_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

삽입 정렬은 값을 하나 꺼내 새로운 리스트의 적당한 위치를 찾아 삽입해 정렬하는 방법이다. 계산복잡도 : O(n2)O(n^2)

병합정렬

#1
def merge_sort(a):
    n = len(a)
    if n <= 1: # 종료 조건
        return a

    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    result = []
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else :
            result.append(g2.pop(0))

    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))

병합정렬은 리스트를 절반으로 나눈 다음, 서로 첫 번째 값들을 비교하며 재귀 호출로 풀어가는 방식이다. 계산복잡도 : O(nlogn)O(n*logn)

퀵정렬

def quick_sort(a):
    n = len(a)
    if n <= 1:
        return a
    pivot = a[-1] # 기준값
    g1 = []
    g2 = []

    for i in range(0, n -1): # 마지막 값은 기준값
        if a[i] < pivot:
            g1.append(a[i]) # 크면 g1
        else:
            g2.append(a[i]) # 작으면 g2
    return quick_sort(g1) + pivot + quick_sort(g2)

퀵정렬은 기준값(pivot)을 정한 뒤, 그 값보다 큰 그룹과 작은 그룹을 나누어가며 재귀호출로 풀어가는 방식이다.

퀵 정렬의 경우, 기준값을 잘 못잡는 경우(가장 크거나 작은 값을 기준값으로 잡는 경우) 선택정렬이나 삽입정렬처럼 계산복잡도가 O(n2)O(n^2)이 되어버리지만, 평균적일 때는 O(nlogn)O(n*logn)이다.

이분탐색

def binary_serch(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if x == a[mid]:
            return mid
        elif x > a[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return -1

이분탐색이란 정렬된 리스트에서 특정값을 찾아 위치를 찾는 문제에서 리스트의 중간값과 특정값을 비교해보며 탐색하는 알고리즘이다.
계산복잡도 : O(logn)O(logn)

연습문제

# 7_1
def serch_list_2(a,x):
    n = len(a)
    ans = []
    for i in range(0, n):
        if x == a[i]:
            ans.append(i)
    
    if ans != []:
        return ans
    else:
        return -1

# 7_3
def serch_student(s_no, s_name, num):
    for i in range(0, len(s_no)) :
        if num == s_no[i]:
            return s_name[i]
    return "?"

# 11_1 거품정렬
def bubble_sort(a):
    n = len(a)
    while True:
        changed = False
        for i in range(0, n - 1):
            if a[i] > a[i + 1]:
                print(a)
                a[i], a[i + 1] = a[i + 1], a[i]
                changed = True
        if changed == False:
            return
    
# 12_1 재귀 호출을 이용한 이분탐색
def binary_serch_2(a, x, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if x == a[mid]:
        return mid
    elif x > a[mid]:
        return binary_serch_2(a, x, mid + 1, end)
    else :
        return binary_serch_2(a, x, start, mid - 1)
    return -1

[넷째마당] 자료구조

큐(queue)와 스택(stack)

큐와 스택은 컴퓨터 과학에서 다루는 여러 가지 자료 중 가장 기본것인 것으로, 자료를 넣는 동작과 빼는 동작을 할 수 있으며, 자료가 일렬로 보관된다는 공통점이 있지만, 자료를 넣고 뺄 때 동작하는 방식이 서로 다르다.

큐(queue)는 줄서기에 비유할 수 있다. 택시를 타기 위해 줄을 서는 과정에서, 택시가 도착하면 가장 먼저 줄을 선 사람이 가장 먼저 택시를 타게 되는 것처럼 큐도 같은 특징을 가지고 있다. First In First Out
큐에 자료를 한 개 집어넣는 동작을 인큐(enqueue), 꺼내는 동작을 디큐(dequeue)라고 표현한다.

스택(stack)은 접시 쌓기에 비유할 수 있다. 다 먹은 접시를 쌓을 때 접시를 차곡차곡 위로 쌓아 올리고, 설거지 하기위해 접시를 꺼낼 때도 가장 위에 있는 접시부터 꺼내는 것처럼, 스택은 가장 마지막에 들어간 자료를 가장 먼저 꺼내는 특징을 가지고 있다. Last In First Out

회문 찾기 알고리즘

순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말을 회문(palindrome)이라고 한다. 어떤 문장이 주어졌을 때, 이 문장이 회문인지 아닌지 찾는 알고리즘을 작성한다.

def palindrome(s):
    qu = []
    st = []
    for x in s:
        if x.isalpha():
            qu.append(x.lower())
            st.append(x.lower())
    
    while qu:
        qu.pop(0) != st.pop
        return False
    
    return True

딕셔너리를 이용한 동명이인 찾기 알고리즘2

def find_same_name(a):
    name_dict = {}
    for name in a:
        if name in name_dict:
            name_dict[name] += 1
        else:
            name_dict = 1
    
    result = set()
    for name in name_dict:
        if name_dict[name] >= 2:
            result.add(name)
    
    return result

문제3 에서 리스트를 이용해 작성했던 알고리즘은 모든 사람을 서로 비교하여 같은 이름이 있는지 찾아내는 방식으로, 사람수가 n명일 때 계산 복잡도는 O(n2)O(n^2)이었지만, 딕셔너리를 이용해 알고리즘을 작성했을 땐 O(n)O(n)의 시간복잡도를 가지는 것을 알 수 있다.

친구의 친구 찾기(그래프)

친구관계를 이용하여 직접 아는 친구들과 그 친구들의 친구들, 직간접적으로 아는 모든 사람들을 출력하는 프로그램을 작성하려 한다. 친구 관계 문제를 풀기 위해 꼭지점들과 꼭지점 사이를 연결한 선의 집합을 이용한 그래프를 이용해 친구관계를 선으로 표현할 수 있다.

친구관계

1. Summer와 John은 친구 관계 입니다.
2. Summer와 Justin은 친구 관계 입니다.
3. Summer와 Mike는 친구 관계 입니다.
4. Justion과 May는 친구 관계 입니다.
5. May와 Kim은 친구 관계 입니다.
6. John과 Justin은 친구 관계 입니다.
7. Justin과 Mike는 친구 관계 입니다.
8. Tom과 Jerry는 친구 관계 입니다.

그래프 표현


(출처 : https://stricky.tistory.com/196)

친구 정보 프로그램

fr_info = {
    'Summer' : ['John', 'Justin', 'Mike'],
    'John' : ['Summer', 'Justin'],
    'Justin' : ['John', 'Summer', 'Mike', 'May'],
    'Mike' : ['Summer', 'Justin'],
    'May' : ['Justin', 'Kim'],
    'Kim' : ['May'],
    'Tom' : ['Jerry'],
    'Jerry' : ['Tom']    
}

모든 친구를 찾는 알고리즘

def all_friends(g, start):
    qu = []
    done = set()
    
    qu.append(start)
    done.add(start)
    
    while qu:
        p = qu.pop(0)
        print(p)
        for x in g[p]:
            if x not in done:
                qu.append(x)
                done.add(x)

처리할 사람을 저장할 큐qu를 만들고, 큐에 이미 추가한 사람을 저장할 집합done을 만들어 큐에사람이 남아 있다면 큐에서 처리할 사람을 꺼내 출력한 후, 큐에 추가된 적이 없는 사람을 골라 집합에 추가하는 과정을 반복하는 방식으로 코드를 구현할 수 있다.

친밀도 계산 알고리즘

A와 B가 친구이고, B와 C가 친구라고 가정할 때, A-B(1), B-c(1)의 친밀도를 가진다. A와 C는 B를 통해 친구의 친구가 되었으므로 A를 기준으로 C의 친밀도는 2라는 것을 알 수 있다. 이 성질을 이용해 친구들을 큐에 넣을 때 친밀도를 증가시키면서 친밀도 계산 알고리즘을 구현할 수 있다.

def print_all_friends(g, start): 
    qu = [] 
    done = set()
    
    qu.append((start, 0)) 
    done.add(start)
    while qu:
        (p, d) = qu.pop(0)
        print(p, d) 
        for x in g[p]:
            if x not in done: 
                qu.append((x, d + 1))
                done.add(x)

연습문제

# 13_1
def solution(s):
    s = s.upper()
    size = len(s)
    
    if s == s[::-1]:
        return True
    else:
        return False

# 14_1
def solution(info, num):
    if num in info:
        return info
    else:
        return "?"

# 15_1
def sulution(g, start):
    qu = []
    done = set()
    
    qu.append(start)
    done.add(start)
    
    while qu:
        p = qu.pop(0)
        print(p)
        for x in g[p]:
            if x not in done:
                qu.append(x)
                done.add(x)

[다섯째마당] 응용문제

미로 찾기 알고리즘

미로의 형태와 출발점과 도착점이 주어졌을 때, 최단 경로를 찾는 것을 컴퓨터로 통해 구현하려면 어떻게 해야할까?
이때 필요한 것이 모델링이다. 모델링이란 주어진 문제를 정형화라거나 단순화해서 수학이나 프로그램으로 설명할 수 있도록 다시 표현하는 것을 말한다.

모델링

미로 정보를 그래프로 나타내고, 이를 딕셔너리로 바꾸면 미로문제를 모델링할 수 있다.

maze = { 
        'a' : ['e'], 
        'b' : ['c','f'], 
        'c' : ['b','d'], 
        'd' : ['c'], 
        'e' : ['a','i'], 
        'f' : ['b','g','j'], 
        'g' : ['f','h'], 
        'h' : ['g','l'], 
        'i' : ['e','m'], 
        'j' : ['f','k','n'], 
        'k' : ['j','o'], 
        'l' : ['h','p'], 
        'm' : ['i','n'], 
        'n' : ['m','j'], 
        'o' : ['k'], 
        'p' : ['l'] 
        }

미로찾기 알고리즘

def solve_maze(g, start, end):
    qu = []
    done = set()
    
    qu.append(start)
    done.add(start)
    
    while qu:
        p = qu.pop(0)
        v = p[-1]
        
        if v == end:
            return p
        
        for x in g[v]:
            if x not in done:
                qu.append(p + x)
                done.add(x)
                
    return "?"

가짜동전 찾기 알고리즘

겉보기에는 같은 동전 n개에서 싸고 가벼운 재료로 만들어진 가짜동전을 양팔저울을 이용해 찾아내는 알고리즘

저울질에 해당하는 기능 구현

a부터 b까지 동전을 저울의 왼쪽, c에서 d까지 동전을 저울의 오른쪽에 올려 저울질하는 함수이다. 왼쪽이 가볍다면 왼쪽에 양팔저울이 있다는 것이고 -1을 리턴하고, 오른쪽에 있으면 1을 리턴한다. 양쪽 무게가 같다면 어느 쪽에도 가짜 동전이 없는 것이고 결과값을 0을 리턴하는데, 이는 저울에 올리지 않은 동전 중에 가짜 동전이 있다는 것이다.

def weigh(a, b, c, d):
    fake = 29 # 가짜동전의 위치, 알고리즘은 weigh함수를 이용해 값을 맞춰야한다.
    
    if a <= fake and fake <= b:
        return -1
    
    if c <= fake and fake <= d:
        return 1
    
    return 0

동전 찾기

모든 동전을 하나씩 올려놓고 비교할 수 있지만, 이분 탐색을 활용해 반씩 그룹을 나누어 비교하면 더욱 효율적으로 알고리즘을 작성할 수 있다.

def find_fakecoin(left, right):
    # 종료 조건 : 가짜 동전이 있을 범위 안에 동전이 한 개일때
    if left == right:
        return left

    half = (right - left + 1) // 2
    g1_left = left
    g1_right = left + half - 1
    g2_left = left + half
    g2_right = g2_left + half - 1

    result = weigh(g1_left, g1_right, g2_left, g2_right)
    if result == -1: # 그룹 1이 가벼움
        return find_fakecoin(g1_left, g1_right)
    elif result == 1: # 그룹 2가 가벼움
        return find_fakecoin(g2_left, g2_right)
    else: 
        return right 

알고리즘 분석

동전을 하나씩 비교할 경우 계산복잡도는 O(n)O(n)이지만, 동전을 절반씩 나누어 후보를 좁히며 비교하면 O(logn)O(logn) 으로 더욱 효율적으로 구현할 수 있다. 리스트 탐색에서의 이분탐색과 가짜동전문제는 겉으로 볼 때 다른문제로 보이지만, 잘 생각해보면 비슷한 문제임을 알 수 있다.

최대 수익 알고리즘

어떤 주식에 대해 특정 기간동안 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고 팔아 얻을 수 있는 최대 수익계산 알고리즘

알고리즘

가능한 모든 경우를 비교하면 직관적이지만, 불필요한 비교를 너무 많이해 비교횟수가 커지게 된다.
주식을 사는 날이 아닌 파는 날을 중심으로 이전 날들의 주가 중 최솟값을 알면 최대 수익을 쉽게 계산할 수 있다.

def max_profit(prices):
    n = len(prices)
    max_profit = 0         
    min_price = prices[0]  # 첫째 날의 주가를 주가의 최솟값으로 기억

    for i in range(1, n): 
        # 지금까지의 최솟값에 주식을 사서 i날에 팔 때의 수익
        profit = prices[i] - min_price
        if profit > max_profit:    
            max_profit = profit
            
        if prices[i] < min_price:  
            min_price = prices[i]

    return max_profit
profile
Done is better than perfect

0개의 댓글