Review 7 - Python Algorithm design & Testing & Debugging

https://eglife.tistory.com/74

Review 6 - Python Recursion & Merge Sort

 

나에게 주어진 무기가 망치밖에 없으면,

 

세상의 모든 것이 못으로 보인다.

 

무기를 늘려야 다채로운 문제를 풀 수 있다는 것

 

 

알고리즘을 설계하기 전에, 소통과 협업을 인간의 언어로 진행하는 것은 필수다.

 

즉, 알고리즘을 디자인하는 과정을 평가받는 경우가 굉장히 많다.

 

각종 기업에서 프로그래머를 평가하는 절차

컴퓨팅 1에서 배우는 자료구조, 알고리즘을 배우는데 그것들을 잘 익히자.

 

단순히 외우는 수준을 넘어서 언제든 활용할 수 있도록 문제를 많이 풀어보자.

 

문제 만이 풀 수 있는 사이트

 

1. https://leetcode.com/ 미국에선 300-400문제 푸는 수준이면 IT기업 입사 가능. Medium / Hard 난이도까지 풀면 구글,애플도 가능..

 

2. 한국에선 https://www.acmicpc.net/ 백준도 많이 쓴다.

 

알고리즘 문제 하나 풀어보기

 

 - Two Sum 문제

 

다양한 방법으로 문제를 풀 수 있는데, 어떻게 코드를 짜냐에 따라 Time complexity가 천차만별이다.

 

int로 이루어진 list와, target value를 input으로 받아서 list 안 숫자 중 두 가지를 더해서 target value를 만들 수 있는 조합을 찾고 그 숫자 2개의 list 내에서 index를 반환하는 문제다.

 

# for loop 2번
def two_sum1(L:list, v:int) -> int :
    for i in range(len(L)):
        for j in range(i+1,len(L)):
            if L[i]+L[j] == v :
                return i,j
# for loop 1번씩 *2
def two_sum2(L:list, v:int) -> int :
    dic = {}
    for i in range(len(L)):
        dic[L[i]] = i
    
    for j in range(len(L)):
        temp = v - L[j]
        if temp in dic and j != dic[temp] :
            return j,dic[temp]

 

import random
import time
L = list(range(10000))
random.shuffle(L)
t_start = time.perf_counter()
two_sum1(L,1)
t_end = time.perf_counter()
print((t_end-t_start)*1000)
t_start = time.perf_counter()
two_sum2(L,1)
t_end = time.perf_counter()
print((t_end-t_start)*1000)
2414.179899962619
0.8797000045888126

 

two_sum1 , two_sum2 이 두 함수는 코드는 비슷해보이지만, L의 개수가 커지면 이렇게나 크게 시간차이가 발생한다는 것이다. 얼마나 효율적으로 코드를 짜느냐가 얼마나 중요한지! 알 수 있는 덕목이다.

0.5 * N^2 인데, Big O 관점에선 사실 1번 Version과 비슷하다.

 

 

Dictionary를 쓰는 발상의 전환을 보여준다면 Time Complexity가 O(N)으로 비약적으로 줄어드는 대신 Dict를 만들어줘야 하니까 Space 를 O(N) 쓰게 된다.

 

그래도 시간소모를 확연히 줄일 수 있기에 아주 강력한 Solution이라고 봐도 된다.

 

def two_sum3(L:list, v:int) -> int :
    dic = {}
    for i in range(len(L)):
        if L[i] in dic and i != dic[L[i]] :
            return dic[L[i]] , i
        temp = v - L[i]
        dic[temp] = i
    
    return -1

 

심지어 이렇게 dictionary를 쓸 때, for문을 하나만 써서도 구현할 수 있다.

Big O 관점에선 Time complexity가 2N이나 N이나 크게 상관은 없지만

 

그래도 최적화된 솔루션이다. 완벽하다고 생각했던 알고리즘을, 또 뛰어넘는 알고리즘이 존재하는게 프로그래밍의 세계이다 ㅎㅎ;;

 

위 그림에서 complement는 미래에 뜨면 Getya! 할 수 있는 항목들이라 차곡차곡 dict에 넣어준다.

 

그 complement가 발견되면, 과거에 걔를 저장했던 index와 지금 발견된 index를 rerturn 하면 되고,

 

발견되지 않으면 그냥 return -1로 종료!

 

만약에 여기서 list가 sorting이 되어 있다면?

 

Two pointer를 쓴다.

 

 

코드를 edge case 포함해서 좀 다듬으면(같은 index 2개 반환 x 등) 아래와 같을듯하다.

이것은 dictionary를 쓰지 않아서 memory complexity가 없다!

def two_sum4(L:list,v:int) -> int:
    i, j = 0, len(L)-1
    while L[i] + L[j] != v and i < j:
        if L[i] + L[j] < v :
            i+=1
        else : j-=1
    if i >= j : return -1
    else : return i, j
--------------------------
lst = [0,1,6,7,9]
target = 16
two_sum4(lst,target)
(3, 4)

 

알고리즘 설계엔 set, dictionary를 쓸 수 있냐 없냐가 많은 것을 좌지우지한다.

 

다양한 자료구조, 알고리즘을 쓸 수 있도록 겅부하장

 

 

- Testing and Debugging

 

프로그래밍을 할 때, QA ( Quality Assurance )가 중요한 이유

 

test case를 만드는 가이드라인이다.

 

이런 것들을 다 커버하는 테스트를 통과해야 안정성있는 코드를 짤 수 있드아

 

- E. O. D -