Youngwon

다이나믹 프로그래밍 1

11 min read

알고리즘 준비운동

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

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) 등의 프로그램 코드를 말한다.
  • 그렇다면 코드의 실행횟수가 어떻게 되어야 좋은 알고리즘일까? 당연히 적게 실행된것, 적게 실행되어 결과를 빨리 출력하는 알고리즘이 좋은 알고리즘이다.
  • 시간복잡도에 대한 자세한 사항은 위키피디아를 참조하기를 바란다. 여기서는 아주 간략한 설명만 진행한다.
    Alt text
  • 위 그림은 위키피디아 페이지에 존재하는 그림이다. 가로축은 입력 데이터 수이고 세로축은 실행 횟수이다. 각각의 측정치에는 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. 반복문 두개가 중첩되어 존재한다.
  2. 같은 인덱스의 요소를 비교하는 것을 조건분으로 피한다.
  3. 중복된 요소가 존재하면 중복된 값을 반환하고 존재하지 않으면 -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]
  1. 첫 번째 값을 두번째 값부터 비교하며 검사
  2. 두 번째 값을 세번째 값부터 비교하며 검사
  • 코드는 다음과 같다.
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] 실면배잘알 김형진 강사님

Graph View