python-algorithms

์ด ๊ณต๊ฐ„์€ Problem Solving ์ดํ•˜ PS ์Šคํ„ฐ๋””๋ฅผ ์œ„ํ•œ ๊ณต๊ฐ„์ž…๋‹ˆ๋‹ค.

Get Started

Install 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!

TDD๋กœ Python ์‹œ์ž‘ํ•˜๊ธฐ

๋งŒ์•ฝ ํŒŒ์ด์ฌ์ด ์ฒ˜์Œ์ด๋ผ๋ฉด TDD๋ฅผ ํ†ตํ•ด ํ”„๋กœ์ ํŠธ๋ฅผ ๊ตฌ์„ฑํ•˜๊ณ  ํŒŒ์ด์ฌ์„ ๋”์šฑ ๋ฉ‹์ง€๊ฒŒ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์•„๋ž˜์˜ ๊ธ€์„ ์ฐธ๊ณ ํ•˜๋„๋ก ํ•˜์ž. ํ”„๋กœ์ ํŠธ์˜ ์†Œ์Šค์ฝ”๋“œ๋Š” ํ˜„์žฌ ์ง€๊ธˆ์˜ Repo ๋˜์‹œ๊ฒ ๋‹ค. ๋„์›€์ด ๋  ๋“ฏํ•˜๋‹ค๋ฉด โ˜… Star๋ฅผ ๋ˆ„๋ฅด๋Š” ์„ผ์Šค๋„ ์žŠ์ง€ ๋ง์ž!

Run

$ python3 -m unittest

How to prepare coding interviews

PS Sites

Contents

Testing

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

Space Complexity

์ดํ•˜ ์ปจํ…์ธ ๋ฅผ ์ฑ„์šฐ๋Š”๋ฐ ํ•จ๊ป˜ํ•˜๊ณ  ์‹ถ์€ ๋ถ„์€ PR์„ ๋ณด๋‚ด์ฃผ์„ธ์š”! ๐Ÿค—

Algorithm Solving Strategies

Divide and Conquer

Dynamic Programming

Greedy Method

Algorithms

Numerical Analysis

Number Theory

Computational Geometry

Data Structures

Bitmask

Dynamic Arra

Linked List

Queue

Stack

String

Tree

Graph

Python Algorithms

Practices to solve problems with Python

Python Algorithms Info

โญ Stars 37
๐Ÿ”— Source Code github.com
๐Ÿ•’ Last Update a year ago
๐Ÿ•’ Created 4 years ago
๐Ÿž Open Issues 1
โž— Star-Issue Ratio 37
๐Ÿ˜Ž Author stunstunstun