Python으로 시작하는 알고리즘

이 글은 파이썬을 통해 알고리즘 학습을 시작하는 분들을 위한 내용입니다.

시작하기

파이썬 설치부터

파이썬은 공식 사이트인 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.
>>>

IDLE과 PyCharm IDE

Interpreter 언어인 파이썬은 위와 같은 Interactive 모드를 통해 별도의 도구 없이 한 줄 한 줄 프로그래밍 하도록 도와준다.

이 REPL은 매우 유용하지만 앞으로 파이썬 코드를 파일에 작성하고자 한다면 JetBrain의 PyCharm IDE를 사용하는 것을 추천한다.

파이썬에는 파일에 작성하기 위한 기본 도구인 IDLE를 포함하고 있다.

자 뻔한 과정은 생략하고 아래와 같이 Hello World를 출력하는 첫 파이썬 프로그램을 작성해보자.

$ echo "print('Hello World!')" > hello_world.py

파일에 작성된 코드 역시 파이썬 Interpreter에 의해서 실행되며 방법은 아래와 같다. 정상적으로 출력이 된다면 우리는 파이썬 프로그래밍을 위한 모든 준비를 마쳤다!

$ python3 hello_world.py
Hello World!

다양한 알고리즘 문제를 제공하는 사이트들

• Hacker Rank
• LeetCode
• Codility
• Kaggle
• Visualgo
• Algorithm Visualizer

Google과 Facebook은 어떻게 알고리즘 인터뷰를 진행할까?

• Google
• Facebook

알고리즘의 성능을 측정하는 기준들

Time Complexity와 Space Complexity

알고리즘을 테스트하면서 가장 고려할 요소는 Time Complexity와 Space complexity이다.

Time Complexity

Time Complexity(시간 복잡도)는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 표현한다. 얼마나 많은 데이터를 입력 받았는지 그에 따라 CPU는 얼마나 사용하는지 수행 시간은 얼마나 걸리는지를 표현할 수 있다.

가장 많이 쓰이는 표현법으로는 알고리즘의 실행 시간의 상한을 나타내는 Big-O 표기법이 있다.

Big-O Notations

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

• 입력 데이터 양이 많아져도 수행 시간이 조금씩 늘어난다.
• 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.

Binary Search

O(n) - Linear Time

• 입력 데이터 양에 따라 수행 시간이 정비례한다.

선형 탐색, for 문을 통한 탐색을 생각하면 되겠다.

O(n log n) - Linearithmic time

• 입력 데이터 양이 n배 많이 진다면, 수행 시간은 n배 보다 조금 더 많아 진다.
• 정비례하지 않는다.

예를 들면, 이진 트리 정렬은 n 크기의 배열 각 요소를 하나하나 삽입하여 이진 트리를 만든다. 자가 균형 이진 탐색 트리의 삽입 연산은 O(log n)시간이 걸리기 때문에, 전체 알고리즘은 Linearithmic time이 걸린다.

O(n^2) - Quadratic Time

• 입력 데이터의 양에 따라 수행 시간은 제곱에 비례한다.

Bubble Sort

마치며

지금까지 파이썬을 통해 알고리즘을 학습하기 위한 첫 걸음을 띄어보았습니다. 기본적인 알고리즘의 구현, 테스트 코드는 아래의 GitHub링크를 참고하세요. 시작이 반이니 화이팅하세요 :)

https://github.com/stunstunstun/awesome-algorithms