이 글은 파이썬을 통해 알고리즘 학습을 시작하는 분들을 위한 내용입니다.
파이썬은 공식 사이트인 python.org에서 다운로드할 수 있다. 설치가 매우 간단하며 OSX 사용자라면 이미 파이썬이 설치되어 있을 것이다.
가능하면 가장 최신의 버전의 python3를 설치하는 것을 권장한다. 설치 후 커맨드 라인에서 아래와 같이 입력하면, 파이썬 Interpeter를 통해 프로그래밍할 수 있는 환경이 갖추어진다.
$ python3
Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>
Interpreter 언어인 파이썬은 위와 같은 Interactive 모드를 통해 별도의 도구 없이 한 줄 한 줄 프로그래밍 하도록 도와준다.
이 REPL은 매우 유용하지만 앞으로 파이썬 코드를 파일에 작성하고자 한다면 JetBrain의 PyCharm IDE를 사용하는 것을 추천한다.
파이썬에는 파일에 작성하기 위한 기본 도구인 IDLE를 포함하고 있다.
자 뻔한 과정은 생략하고 아래와 같이 Hello World를 출력하는 첫 파이썬 프로그램을 작성해보자.
$ echo "print('Hello World!')" > hello_world.py
파일에 작성된 코드 역시 파이썬 Interpreter에 의해서 실행되며 방법은 아래와 같다. 정상적으로 출력이 된다면 우리는 파이썬 프로그래밍을 위한 모든 준비를 마쳤다!
$ python3 hello_world.py
Hello World!
알고리즘을 테스트하면서 가장 고려할 요소는 Time Complexity와 Space complexity이다.
Time Complexity(시간 복잡도)는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 표현한다. 얼마나 많은 데이터를 입력 받았는지 그에 따라 CPU는 얼마나 사용하는지 수행 시간은 얼마나 걸리는지를 표현할 수 있다.
가장 많이 쓰이는 표현법으로는 알고리즘의 실행 시간의 상한을 나타내는 Big-O 표기법이 있다.
| Big-O | Operations for 10 things | Operations for 100 things |
|---|---|---|
| O(1) | 1 | 1 |
| O(log n) | 3 | 7 |
| O(n log n) | 30 | 700 |
| 0(n^2) | 100 | 10000 |
Solutions - https://www.martinkysel.com/codility-solutions/
O(1) - Constant Time
입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
O(log n) - Logarithmic Time
Binary Search
O(n) - Linear Time
선형 탐색, for 문을 통한 탐색을 생각하면 되겠다.
O(n log n) - Linearithmic time
예를 들면, 이진 트리 정렬은 n 크기의 배열 각 요소를 하나하나 삽입하여 이진 트리를 만든다. 자가 균형 이진 탐색 트리의 삽입 연산은 O(log n)시간이 걸리기 때문에, 전체 알고리즘은 Linearithmic time이 걸린다.
O(n^2) - Quadratic Time
Bubble Sort
지금까지 파이썬을 통해 알고리즘을 학습하기 위한 첫 걸음을 띄어보았습니다. 기본적인 알고리즘의 구현, 테스트 코드는 아래의 GitHub링크를 참고하세요. 시작이 반이니 화이팅하세요 :)