파이썬 - 처음 시작하는 알고리즘 : intro

목차

시작

좋은 알고리즘

알고리즘 성능 평가

문제를 접근하는 법 : 읽기 전부다. 짝퉁코드. 구현 << 새로운 글?

 

 

시작

우리가 알고리즈(코딩테스트를) 배우는 가장 큰 이유는 취직 때문입니다.

취직을 위해 어느정도 까지 코딩테스트를 준비해야 할 까요?

프로그래머스를 보면 3단계 까지라 되어 있습니다.

저 또한 3단계 까지 진행하면 거의 대부분의 코딩테스트에서 무리없이 합격할 것이라 생각합니다.

 

그래서 처음 알고리즘을 접하는 독학 비전공자들을 위해,

딱! 프로그래머스 3단계까지 진행하는 글입니다.

(참고로 나머지 글들은 "파이썬-알고리즘 기초" 목록에 있습니다.)

 

알고리즘 기초적인 내용과 파이썬 중급 정도의 내용을 다루고 있으며,

프로그래머스 문제풀이까지 담고 있습니다.

 

프로그래머스의 문제로 제작된 이유는 독학 비전공자들이 프로그래머스 플랫폼을 이용하면,

집에서 독학하며 취직할 수 있을 것이라 생각이 되었기 때문입니다.

프로그래머스에서는 방학 인턴 프로그램이나 데브 매칭과 같은 취직 프로그램을 진행하는데,

이를 활용하면 좋은 결과가 있을 것이라 생각합니다.

 

좋은 알고리즘

좋은 알고리즘은 뭘까요?

알고리즘의 좋고 나쁨을 판단하기 위해서는 기준이 필요합니다.

 

컴퓨터 과학에서는 2가지 측면에서 알고리즘을 평가합니다.

시간적인 측면과 공간적인 측면입니다.

시간적인 측면은 얼마나 빠른 시간 안에 문제를 해결하는지를 의미합니다.

공간적인 측면은 문제를 해결하는데 얼마나 많은 메모리를 사용하는지를 의미합니다.

 

예를 통해 감 익히기

그러면 좋은 알고리즘이 뭔지 감을 익히기 위해 예를 봅시다.

양의 정수 n을 인풋으로 받아 1부터 n까지 더한 값을 리턴하는 함수를 구현 한다고 생각 해봅시다.

이를 구현하는 방법은 무진장 많이 존재할 것입니다.

이들 중 개성이 있는 4가지 방법을 구현해 봅시다.

 

1. 일반적으로 처음 생각하는 방법 : 1부터 n까지 더하기

def sum(n):
    result = 0
    for i in range(1,n+1):
        result += i
    return result

2. for loop를 좋아하는 사람의 구현 방법 : 1번 방벙에서 i을 1로 나누어 더하기

def sum(n):
    result = 0
    for i in range(1,n+1):
    	for _ in range(i):
        	result += 1
    return result

3. 고등학교 때 수학 공부를 열심히 한 사람의 구현 방법 : 공식 이용하기.

def sum(n):
    return n*(n+1)//2

note

1부터 n까지 더한 값은 n(n+1)//2이다.

 

4. 준비성이 철저한 분의 구현 방법 : 미리 계산해 놓기. 없으면 계산해서 저장하기

sum = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153,
171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561,
595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176,
1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891,
1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775,
2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403]

def sum_4(n,sum_list):
    if n < len(sum_list): return sum_list[n]
    a = sum_4(n-1, sum_list)
    sum_list.append(a)
    return a + n
    
#필요한 만큼 저장하여 사용하면 된다.
for i in range(10000):
    sum(i*100,sum_list )

 

이 처럼 한 문제 대해서 다양한 구현 방법이 존재하는데...

그러면 누가 가장 잘 구현할 것일까요?

파이썬의 time 모듈을 이용하여 시간을 측정해 봅시다.

import time
sum = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153,
171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561,
595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176,
1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891,
1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775,
2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403]

#필요한 만큼 저장하여 사용하면 된다.
for i in range(10000):
    sum(i*100,sum_list )
    
    
def sum_1(n):
    result = 0
    for i in range(1,n+1):
        result += i
    return result

def sum_2(n):
    result = 0
    for i in range(1,n+1):
    	for _ in range(i):
        	result += 1
    return result


def sum_3(n):
    return n*(n+1)//2


def sum_4(n,sum_list):
    if n < len(sum_list): return sum_list[n]
    a = sum_4(n-1, sum_list)
    sum_list.append(a)
    return a + n

tests = [1, 1000, 10000, 100000, 200000]
for test in tests:
    
    start = time.time()
    sum_1(test)
    end = time.time()
    time_1 = (end - start)* 1000000

    start = time.time()
    sum_2(test)
    end = time.time()
    time_2 = (end - start) *1000000

    start = time.time()
    sum_3(test)
    end = time.time()
    time_3 = (end - start) *1000000

    start = time.time()
    sum_4(test, sum_list)
    end = time.time()
    time_4 = (end - start) *1000000

    print("n", test)
    print("sum_1:",int(time_1),"sum_2:",int(time_2),"sum_3:", int(time_3),"sum_4:", int(time_4))
    print("----------------")
    
---> 출력결과
n 1
sum_1: 2 sum_2: 1 sum_3: 0 sum_4: 1
----------------
n 1000
sum_1: 76 sum_2: 34320 sum_3: 1 sum_4: 1
----------------
n 10000
sum_1: 662 sum_2: 3287307 sum_3: 1 sum_4: 2
----------------
n 100000
sum_1: 7501 sum_2: 345793250 sum_3: 38 sum_4: 3
----------------

 

자 그럼 출력 결과를 분석해 봅시다.

함수	sum_1	sum_2	sum_3	sum_4
인풋 n에 대한 루프	1 중첩	2 중첩	0 중첩	저장된 경우 : 0 중첩 저장이 안된 경우 : 1 중첩
n = 10**4일떄 시간	662	3287307	1	2
n = 10**5일때 시간	7501	345793250	38	3

바로 위의 결과는 n이 증감함에 따라 시간을 측정한 값입니다.

n이 큰 경우를 보면 성능의 차이를 확실히 느낄 수 있습니다.

n이 100000일 때  sum_2는 sum_4보다 1억 배나 느립니다.

 

무엇이 이런 차이를 만드는 것일까요?

위의 결과를 가장 큰 차이를 만드는 것은 바로 for loop입니다.

for loop가 몇 개 중첩되어 있느냐에 따라 성능에 엄청난 영향을 미칩니다.

 

그러면 공간적인 측면에서 분석해 보면 어떨까요?

시간 측면에서 가장 좋은 성능을 보이는 sum_4만 n이 증가함에 따라 공간 사용량이 증가합니다.

함수	sum_1	sum_2	sum_3	sum_4
n = 10**5일떄 대략적인 공간 사용량	1	1	0	x*(10**5), x=0,1,2,3,4

알고리즘 성능 평가

이전 챕터에서 컴퓨터 과학에서 알고리즘 평가 시 사용되는 2가지 변수에 대해서 감을 익혔습니다.

그리고 이를 분석해 보니,

인풋 n에 대하여 loop가 몇 번 중첩되어 있느냐가 시간 측면에서 중요한 역할을 한다는 점을 알았습니다.

이번 챕터에서는 이전 챕터에서 얻은 알고리즘의 시간적 공간적 성능에 대한 감을 이론화해봅시다.

특히 시간적 측면이 코딩 문제 풀이에 중요한 역활을 하기 때문에 시간 복잡도 위주로 알아봅시다.

 

알고리즘의 시간적 측면을 전문용어로 시간 복잡도라 하며,

공간적인 측면을 전문용어로 공간 복잡도라 합니다.

 

시간 복잡도와 공간 복잡도는 주로 Big-O표기법을 이용하여 나타냅니다.

 

여기서 Big-O 란?

Big-O표기법은 대략적으로 함수의 증가 추세를 표현할 때 사용하는 표기법입니다.

만약 f(n) = 2n**3 + 3n이라는 함수가 있다고 생각해 봅시다.

n이 증가함에 따라 가장 큰 영향력을 가지고 있는 n**3만 고려하여,

O(n**3)로 표기하는 방법을 Big-O표기법이라 합니다.

그래서 f(n) = O(n**3) = 2n**3 + 3n이라 생각할 수 있습니다. 

 

시간 복잡도

대부분의 경우 시간 복잡도는 인풋에 대한 연산수를 Big-O표기법을 이용하여 나타냅니다.

왜 시간 성능을 측정하는데 연산수만 카운트하는 것일까요? 

알고리즘의  실행 시간은 컴퓨터의 성능, 사용 언어의 구조 등 다양한 곳에 영향을 받습니다. 하지만 이전 챕터에서 실험해본 경험으로 보면. n이 충분히 클 때는 작성된 코드가 중요한 역할을 한다는 것을 알았습니다.

그렇기에 작성된 코드를 제외한 모든 변수는 시간 복잡도에 포함시키지 않습니다.

 

그러면 이전에 작성한 sum_i() 함수 들에 대해서 Big-O를 구해 봅시다.

함수	sum_1	sum_2	sum_3	sum_4
연산수	n + constant	n *( n+ constant )	constant	저장된 경우 : constant 저장이 안된 경우 : 2n + constant
Big-O	O(n)	O(n**2)	O(1)	O(n) = O(1) or O(n)
n = 10**5일때 시간	7501	345793250	38	3

 

공간 복잡도

공간 복잡도 또한 시간 복잡도와 유사하게 인풋에 대한 공간 사용량을 Big-O표기법을 이용하여 나타냅니다.

이전 예제에서 sum_4의 경우 값을 리스트에 저장하였다 사용하기에 O(n)의 공간 복잡도를 가지지만.

나머지는 O(1)의 공간 복잡도를 가집니다.

 

알고리즘 문제 접근 방법

알고리즘 문제를 어떻게 접근해야 할까요?

 

문제 이해하기

알고리즘 문제를 풀기 위해서는 진짜 진짜 진짜 문제를 잘 읽어야 합니다.

특히 카카오 기출문제를 보면 알겠지만,

지문이 너무 길어요.

그래서 중간 내용을 빼먹고 구현했다가.

맞았는데 왜 틀렸지? (맞왜틀) 할 때가 많습니다.

 

의사코드(pseudocode , 짝퉁코드) 작성

입력이 뭔지 출력이 뭔지 조건이 뭔지 등 문제를 명확하게 이해하고 나서,

어떤 알고리즘과 자료구조를 사용하여 코딩할 것인지,

파이썬 라이브러리를 사용할 건지 말 건지 등.

자신의 전략을 빈종이에 작성해야 합니다.

참고로 수도 코드 작성 전까지!

절대로 키보드에 손을 올리지 않는 것을 추천드립니다.

특히 연습 단계에서는 생각하는 것과 코드로 구현하는 것을 분리해서 진행해야 

학습효과가 좋습니다.

 

코드로 구현

의사 코드(pseudocode, 짝퉁코드)로 작성된 전략을 코드로 구현하는 단계입니다.

연습 단계에서는 오로지 의사 코드를 코드로 옮기는 것에 집중하여 정답 판정받는 것이 중요합니다.

정답 판정을 받은 후에는 다른 사람들의 코드와 비교하며 나의 코드 습관을 최적화해야 합니다.

 

 

다음 글 - 파이썬 시퀀스