다이나믹 프로그래밍 1

알고리즘 준비운동

목적 : 알고리즘 문제풀이에 필요한 파이썬의 접근방식을 익혀보자!
선수과목 : 자료구조, 알고리즘

1. 알고리즘을 작성에 대한 고려사항

주어진 문제를 프로그래밍 언어로 작성해서 원하는 결과를 출력하게 만들면 모두 좋은 알고리즘일까?
당연히 아니다! 컴퓨터는 한정된 자원(CPU,RAM,..)을 바탕으로 작업(연산)을 진행한다. 그러므로 알고리즘을 작성할때는 자원의 사용을 최소화하는 알고리즘이 무엇인지 항상 생각해야한다.
그렇다면 효율적인 알고리즘을 판단하는 요소는 무엇일까? 그것은 바로 시간복잡도(time complexity)와 공간복잡도(space complexity)이다!
시간복잡도 https://en.wikipedia.org/wiki/Time_complexity
공간복잡도 https://en.wikipedia.org/wiki/Space_complexity
BigO Notation Cheetsheet! http://www.bigocheatsheet.com
발전된 하드웨어 스펙으로인해 최근에는 공간복잡도에 대한 최적화가 시간복잡도보다는 덜 이루어진다.
여기서는 시간복잡도에 대한 접근 방식을 살펴보겠다.

2. 시간복잡도

시간복잡도는 쉽게 말해 코드의 실행 횟수를 계산한것이다.
여기서 말하는 코드란 반복문(for), 조건문(if) 등의 프로그램 코드를 말한다.
그렇다면 코드의 실행횟수가 어떻게 되어야 좋은 알고리즘일까? 당연히 적게 실행된것, 적게 실행되어 결과를 빨리 출력하는 알고리즘이 좋은 알고리즘이다.
시간복잡도에 대한 자세한 사항은 위키피디아를 참조하기를 바란다. 여기서는 아주 간략한 설명만 진행한다.
위 그림은 위키피디아 페이지에 존재하는 그림이다. 가로축은 입력 데이터 수이고 세로축은 실행 횟수이다. 각각의 측정치에는 n!, 2^n, n^2.. 등이 보인다.
즉 n개의 데이터를 입력할 경우 연산이 얼마나 이루어지나를 나타낸것이다. 위 그래프에서는 n!이 최악의 성능을 나타내고 1이 최고의 성능을 나타낸다. 이것은 조금만 생각해보면 당연히 알수 있는 내용이다.
이러한 표기법을 Big-O 표기법이라한다. 이 표기법은 다항식에서 가장 높은 차수의 항만을 표기한다.ex) 4n^3 + 12n^2 + 3 = O(n^3), 3nlogn + 4 = nlogn
그럼 문제를 통해 Big-O 표기법과 이를 최적화(최소화)하는 방법을 살펴보자.

3. 실전 문제

그럼 간단한 문제를 풀어보자. 다음과 같이 중복된 값이 오직 한개만 존재하는 배열이 존재 할 때 중복된 요소는 어떻게 찾을 수 있을까?
- [6, 23, 5, 12, 46, 71, 9, 23]
먼저 시간복잡도를 고려하지 않고 가장 쉽게 생각하면 다음과 같지 않을까?
먼저 배열의 첫 번째 요소를 나머지 요소 전부와 비교해서 똑같은 값이 있는지 검사한다. 다음은 두 번째 요소와 나머지 요소 전부와 비교해서 똑같은 값이 있는지 검사한다. … 마지막 요소를 나머지 요소와 비교해서 똑같은 값이 있는지 검사한다.
위와 같은 알고리즘을 파이썬으로 표현하면 다음과 같다.

def checkDuplcation(arr):
    length = len(arr)
    for i in range(length):
        for j in range(length):            
            if i == j:
            continue
        elif arr[i] == arr[j]:                
            return arr[i]
    return -1


def main():
    arr = [6, 23, 5, 12, 46, 71, 9, 23]
    print(checkDuplcation(arr))

if __name__ == "__main__":
    main()

위의 알고리즘을 설명하면 다음과 같다.

반복문 두개가 중첩되어 존재한다.
같은 인덱스의 요소를 비교하는 것을 조건분으로 피한다.
중복된 요소가 존재하면 중복된 값을 반환하고 존재하지 않으면 -1을 반환한다.

위의 알고리즘은 어떠한 배열(문제에서 제시한 특성을 가지는)이 와도 중복된 요소를 찾을 수 있다.
그렇다면 성능적인 면에서 봤을 때 효율적일까? 조금만 생각해보면 다음과 같이 중복된 연산이 일어나는 것을 알 수있다.바깥 i가 0일때 arr[0]과 arr[1]을 비교했는데 i가 1일때 arr[1]과 arr[0]의 비교가 또 이루어진다. 즉 중복된 연산이 이루어진다.
그렇다면 가장중요한 Big-O 표기법의 결과는 어떻게 될까? for문을 가지고 계산해보자.
j가 i만큼 반복된다. j와 i는 모두 length만큼 진행하므로 O(n^2)이라는 것을 알 수있다!

4. 개선1 - 중복연산제거

여기서는 앞에서 설명한 중복된 연산을 제거해보자.
어떻게 중복된 연산을 제거할 수 있을까… 계속 생각해보자…첫 번째 요소와 나머지 요소를 연산한 후 다음 요소부터는 첫번째 요소와 검사 할 필요가 없다. 즉, 두번째 요소를 검사할때는 첫번째가 아닌 두번째 부터 중복여부를 검사하면된다. 하지만 두번째 요소또한 같은 요소를 비교하는 것이기 때문에 검사할 필요가 없다.
- [6, 23, 5, 12, 46, 71, 9, 23]

첫 번째 값을 두번째 값부터 비교하며 검사
두 번째 값을 세번째 값부터 비교하며 검사

코드는 다음과 같다.

def checkDuplcation(arr):
    length = len(arr)
    for i in range(length):
        for j in range(i+1, length):
            if arr[i] == arr[j]:                
            return arr[i]
    return -1


def main():
    arr = [6, 23, 5, 12, 46, 71, 9, 23]
    print(checkDuplcation(arr))

if __name__ == "__main__":
    main()

앞코드에서 발생한 중복된 연산을 깔끔히 제거하였다. 그렇다면 가장 중요한 시간복잡도는 어떻게 될까?
실제 반복수는 n + (n-1) + (n-2) + … + 1 이다. 즉 n^2-(1+2+..+(n-1)) 이다.
안탑깝지만 이경우도 Big-O 표기법에서는 O(n^2)이다.
중복연산을 제거했다고 생각했는데 정말 같은 시간복잡도를 가지는 알고리즘이라고 판단해야되는 것일까? 같은 알고리즘이라고 판단해도 좋다. 이유는 n이 커지면 커질수록 O(n^2)의 특성을 가지기 때문이다.

5. 개선2 - 자료구조 이용하기

이번에는 자료구조를 사용해보자.
좀더 개선하기 위해서는 어떤 자료구조를 사용하면 좋을까?
이전의 개선과 같이 계속 생각해보자… 계속 생각해보자…
답을 먼저 말하면 해시(hash)를 이용하는 것이다.
코드는 다음과 같다.

def checkDuplcation(arr):
    dic = {}
    length = len(arr)
    for i in range(length):
        if arr[i] in dic:
        return arr[i]
    else:
        dic[arr[i]] = 1
    return -1


def main():
    arr = [6, 23, 5, 12, 46, 71, 9, 23]
    print(checkDuplcation(arr))

if __name__ == "__main__":
    main()

여기서 중요한 사실은 파이썬의 딕셔너리는 해쉬로 작동한다는 점이다. 해시는 O(1)을 가지는 자료구조이다.
위와 같은 상황에서 반복문은 최대 n번만 수행된다. 즉 위의 알고리즘음 O(n)이다!
이번 설명은 사실 이 부분을 강조하기 위한 것 이였다.

5. 마무리

위 문제를 개선하던 중 코드레벨의 가장 큰 변화는 무엇일까?
그것은 2중 반복문을 한개로 축소시킨것이다. 이것은 알고리즘의 시간복잡도를 줄이는 가장큰 역활을 한다.
또한 언어의 스펙을 알면 좀더 성능이 좋은 코드를 작성 할 수 있다는 것을 알 수 있었다.
최신 기술의 프레임워크, 라이브러리도 좋지만 프로그램의 본질인 자료구조와 알고리즘을 꾸준히 학습해서 좋은 개발자가 되자.
여러가지 언어보다는 한 가지 언어의 스펙을 상세히 공부하면 좀더 깊이있는 코드를 작성할 수 있다.

References

[elice.io] 실면배잘알 김형진 강사님