알고리즘 공부 시작

서정윤·2022년 4월 9일

알고리고리

목록 보기

1/3

알고리즘이란 몰까,,,

1.1 알고리즘이란?

알고리즘....

어떤 문제를 컴퓨터로 풀기 위한 효율적인 절차
문제를 푸는 단계별 절차 를 명확하게 기술

알고리즘은 왜 해야하나...

문제를 컴퓨터로 해결하는 방법을 공부하기 위해서
프로그래밍 언어나 문법과는 무관

문제와 해답

문제란? 해답을 찾으려고 물어보는 질문
파라미터란? 문제에서 특정한 값이 지정되어 있지 않은 변수
입력 사례는? 문제의 파라미터에 지정된 특정한 값

알고리즘

어떤 문제의 모든 입력 사례 에 대해서 해답을 찾아주는 단계별 절차
입력 파라미터에 어떤 입력 사례가 주어지더라도 해답을 찾을 수 있어야됨,,,

순차 탐색 문제

문제:어떤 수 x가 n개의 수로 구성된 리스트 S에 존재하는가?
해답:x가 존재하면 x의 인덱스, 없으면 0이 해답
파라미터:정수n(>0), 리스트S(인덱스 범위 1~n), 원소 x
입력 사례:S=[0 ,10 , 7, 11, 5, 13, 8]
입력 사례에 대한 해답:location=4
알고리즘:모든 S에 대해서 x의 인덱스를 찾아주는 단계별 절차
- S의 첫번째 원소에서 시작~~ x를 찾을 때 까지
- 각 원소를 차례대로 x와 비교
- 만약 x를 찾으면 x의 인덱스를 리턴
- x를 찾지 못하면 0을 리턴

def seqsearch (n, S, x):

    location = 1
    while (location <= n and S[location] != x):
        location += 1
    if (location > n):
        location = 0
    return location

리스트(배열)원소의 합 구하기

def sum (n, S):
    result = 0
    for i in range(1, n + 1):
        result = result + S[i]
    return result

리스트 정렬 문제

문제:n개의 수로 구성된 리스트 S를 비내림차순으로 정렬
알고리즘
- 교환정렬, 삽입정렬, 선택정렬, 합병정렬, 퀵 정렬 등등...

def exchange (S):
    n = len(S)
    for i in range(n - 1):

        for j in range(i + 1, n):

            if (S[i] > S[j]):

                S[i], S[j] = S[j], S[i] # swap

i번째 자리에 있는 수와 (i+1)번째부터 n번째 자리에 있는 수를 차례로 비교
주어진 자리의 수가 i번째 자리에 있는 수보다 작으면, 두 수를 교환
for-i루프를 한 번 수행하면 그 중 가장 작은 수가 첫번째 자리에 들어감
두번째 루프를 수행하면 둘째 자리에 둘째로 작은 수가 들어감
for-i 루프 모두 수행되면 비내림차순 정렬이 됨

행렬의 곱셈 문제

C = A * B, cij = ai1b1j+ai2b2j

def matrixmult (A, B):

    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):

        for j in range(n):

            for k in range(n):

                C[i][j] += A[i][k] * B[k][j]

    return C

1.2 알고리즘의 효율성

알고리즘의 효율성

알고리즘의 성능이란? 시간과 공간 사용량의 효율성
알고리즘 성능은 컴퓨터의 실행 속도나 메모리의 가격에 무관하다~

순차탐색 vs 이분검색

입력리스트의 조건에 따라 알고리즘의 선택이 달라짐

정렬되지 않은 리스트에서 키 찾기:순차탐색
정렬된 리스트에서 키 찾기:이분검색

이분검색

주어진 리스트S와 키x에 대해서
1. 먼저 x를 리스트의 중앙에 위치한 원소와 비교
2. 만약 같으면, 알고리즘 종료(찾았다)
3. 만약 x가 그 원소보다 작으면, x는 왼쪽에 있을것이다
  -> 왼쪽 리스트에 대해서 이진 탐색
4. 만약 x가 그 원소보다 크면 x는 오른쪽에 있을 것이다
  -> 오른쪽 리스트에 대해서 이진 탐색
5. 더 이상 찾을 리스트 없으면 알고리즘 종료

<Binary Search (Iterative)

def binsearch(n, S, x):
    low = 1
    high = n
    location = 0
    while (low <= high and location == 0):
        mid = (low + high) // 2
        if (x == S[mid]):
            location = mid
        elif (x < S[mid]):
            high = mid - 1
        else:
            low = mid + 1
    return location

순차 탐색과 이분 검색 알고리즘의 효율성 비교

순차탐색은 크기가 n인 리스트에서 n번 의 비교
이분검색은 크기가 n인 리스트에서 lgn+1번의 비교

리스트의 크기	순차 탐색의 비교 횟수	이분 검색의 비교 횟수
128	128	8
1024	1024	11
1,048,576	1,048,576	21
4,294,987,296	4,294,987,296	33

피보나치 수열의 n번째 항 구하기

피보나치 수열을 재귀함수로 구하기

<Finding the n-th Fibonacci Term (REcursive)

def fib (n):

    if (n <= 1):
        return n

    else:
        return fib(n - 1) + fib(n - 2)

그치만 이 알고리즘은 같은 값을 계속 중복해서 계산하므로 비효율적,,
중복해서 계산 안하려면 어떻게 해야할까
이미 계산한 피보나치 항의 값을 저장하면 되지 않을까

<Finding the n-rh Fibonacci Term (Iterative)

def fib2 (n):

    f = [0] * (n + 1)
    if (n > 0):
        f[1] = 1
        for i in range(2, n + 1):
            f[i] = f[i - 1] + f[i - 2]
    return f[n]

위의 알고리즘에서 리스트를 사용하지 않고 반복문으로 구하려면?
나중ㅇㅔ 알아보자,,,!!

1.3 알고리즘 분석

어떤 알고리즘에 대한 두가지 질문!!!

정확한가? 모든 입력 사례 에 대해서 해답 을 찾을 수 있는가
효율적인가? 입력 크기가 커지면 성능 이 어떻게 변화하나?

알고리즘의 분석

정확성 분석 :모든 입력 사례에 대해서 정확한 해답을 찾는다는 것을 증명
효율석 분석 : 입력 크기가 커지는 정도에 따라 성능 변화량을 증명
- 시간 복잡도(time complexity):시간을 기준으로 알고리즘의 효율성 분석
- 공간 복잡도(space complexity):공간을 기준으로 알고리즘의 효율성 분석

알고리즘의 성능 분석

퍼포먼스 측정:실행 시간을 직접 측정 or 실행 명령의 숫자 세기
-> 컴퓨터의 성능이나 프로그래밍 언어에 따라 달라짐!!
복잡도 분석:컴퓨터나 프로그래밍 언어와 무관하게 성능 분석
-> 입력 크기에 따른 단위 연산의 실행 횟수 세보자

복잡도 분석

입력 크기:문제가 가진 파라미터, (입력 사례의 크기)
단위 연산:알고리즘 실행의 기본이 되는 명령어들의 집합

def sum (S):
    n = len(S)
    result = 0
    for i in range(n):
        result += S[i]
    return result

위의 배열 원소 합을 구하는 알고리즘의 시간복잡도를 분석해보자.
입력 크기 는 리스트S의 원소 개수(n)이고,
단위 연산 은 리스트의 원소를 result에 더하는 것
for문은 항상 n번 실행하므로 시간복잡도는?? T(n) = n

배열 원소의 합을 구하는 알고리즘의 시간복잡도
T(n) = n

교환정렬의 시간 복잡도 분석

def exchange (S):
    n = len(S)
    for i in range(n - 1):

        for j in range(i + 1, n):

            if (S[i] > S[j]):

                S[i], S[j] = S[j], S[i] # swap

그럼 앞에서 봤던 exchange sort의 시간복잡도를 분석해보자~~
단위 연산 은 S[i]와 S[j]를 비교하는 것
입력 크기 는 정렬할 리스트S 의 원소 개수 = n
3중 for루프가 항상 n번 실행됨
그러므로 시간복잡도는 T(n) = n n n = n^3

근데,, 위의 단위 연산의 실행 횟수가 항상 일정할까?
순차 탐색은 찾는 원소가 어디 있느냐에 따라 다름!!

그럼 입력 사례에 따른 시간 복잡도를 분석해보자

일정 시간 복잡도:입력 사례에 따라 달라지지 않는 경우
최악, 최적, 평균 시간 복잡도 분석:입력 사례에 따라 달라짐

순차탐색의 시간 복잡도 분석

def seqsearch (n, S, x):

    location = 1
    while (location <= n and S[location] != x):
        location += 1
    if (location > n):
        location = 0
    return location

다시 보자.
단위 연산 은 리스트의 원소와 주어진 키x와 비교하는 것이고,
입력 크기 는 리스트 원소의 개수 n이다
최악의 경우 는 리스트의 모든 원소와 x를 비교하는 것,
최적의 경우는 찾는 원소가 리스트의 제일 앞에 있어서 한번만 비교하는 것,

최악의 경우 W(n) = n
최적의 경우 B(n) = 1

평균의 경우 는 뭘까 그러면?
주어진 키 x가 k번째에 있으면 k번을 비교해야 한다.
어떤 키 x가 리스트S에 골고루 분포해있다고 가정하면,

1.4 알고리즘의 차수

어떤 알고리즘이 (궁극적으로) 더 빠른가?

시간 복잡도:입력 크기(n)에 대한 단위 연산 횟수의 함수 f(n)
시간 복잡도가 f(n) = n인 알고리즘과 g(n) = n^2인 알고리즘
만약 단위 연산의 실행이 g(n)은 t고 f(n)은 1000t인 경우, 전자가 1000배 느리지만 전체 실행으로 보면?
n 1000t, n^2 t 이므로
n 1000t < n^2 t 이 성립하려면, n > 1000
즉, n이 1000보다 크면 f(n)이 g(n)보다 궁극적으로 더 빠르다고 할 수 있다

알고리즘의 차수

차수(Order):알고리즘의 궁극적인 성능 분류
- 1차 시간 알고리즘:시간 복잡도가 1차함수인 알고리즘
- 2차 시간 알고리즘:시간 복잡도가 2차 함수인 알고리즘
- 근본 원리: 모든 1차 시간 알고리즘은 궁극적으로 2차 시간 알고리즘보다 빠르다
따라서, 시간 복잡도 함수의 차수로 알고리즘의 성능을 분류 할 수 있다