이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

리스트 & 딕셔너리 연산자 정리

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

선형탐색 알고리즘 평가하기

각 변수선언, 함수들을 한 줄씩 보면, 모두 리스트의 크기(n)과는 상관없이 일어나므로 O(1)이 소요된다.

while 반복문 또한, 한번 일어났다고 가정하면, n과 관계없으므로 반복횟수 X O(1)이 소요된다.

이 때, Best 경우 반복문 1번만에 = 첫 원소가 찾는 element인 경우,
걸리는 시간은 4 * O(1) = O(4) 역시 O(1)라 할 수 있다.

최악의 Worst 경우 반복문 n(0~n-1)번 돌아도 찾는 element가 리스트에 없는 경우로서,
걸리는 시간은 3*O(1) + O(1)*n이며, O(1) * n은 O(n)으로 나타낼 수 있다. ( 리스트의 개수만큼 반복된다. n이 관여)
즉, O(n +3)이 된다. 하지만, 점근표기법에서는 3은 없애줘도 되므로 O(n)이 된다.

이진탐색 알고리즘 평가하기

Best의 경우는 아래와 같이 반복문이 1번 도는 시간으로서, O(4) = O(1)이다.

하지만, 이진탐색의 Worst(리스트에 없는 경우) 는 반복문이 몇번 돌까?

loga(b) = xlog2(x) = y의 의미 :

    혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.
    컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.
    log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.
    예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.

리스트의 원소길이 n 을 2로 몇번나누어야 1이 나오는지 횟수 = log2(n) 으로 나타낸다.
즉, lg(n) = n(리스트의 길이)를 몇번을 2로 나누면 1이 나오는지 = 몇번 반토막 내면 1이 나오는지라고 하였다.

그렇다면, 이진탐색의 Worst는 [ 반복문1회(O(1)) * lg(n) ] + O(3) = O(lg(n))이다.

정리하자면, 아래와 같다.

알고리즘에서는 보수적이라 최악의 경우를 자주 살핀다. 그러므로 아래와 같이 부른다.

  1. 선형탐색 = Big-O of n 알고리즘
  2. 이진탐색 = Big-O of lg(n)알고리즘

나의 정리

  1. 알고리즘 최악의 경우는 element가 list에 없어서 반복문(회당 O(1))을 모두 돈 경우로서, n과 관련된다.
  2. 선택탐색은 n번 / 이진탐색은 log2(n)번 반복문을 돈다. ( n은 리스트의 원소 개수)

알고리즘 평가시 주의사항

코드의 모든 줄은 O(1)인가요?

아닙니다!
인풋 크기와 상관 없이 실행되는 코드만 O(1)입니다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 합니다.
예를 들어서 sorted 함수나 list.sort 메소드를 사용하면 내부적으로 O(nlgn)의 정렬이 이루어집니다.

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어집니다.

파이썬의 내장된 정렬 알고리즘은 timsort라는 것입니다. 최악 or 평균의 경우 O(n lg n), 최고의 경우 O(n)이라고 하네요.
합병 정렬과 퀵 정렬도 평균 O(n lg n)입니다.

4. 가변길이 인수목록받기 args,kwargs

참고 사이트 : Intermediate python (http://book.pythontips.com/en/latest/)
참고 블로그 : https://3months.tistory.com/347?category=753896

*agrs 정의

  • *args : non-keyworded arguments로 요소 나열 or *리스트이 들어가 함수내부에서 리스트로 사용
    1) 함수 정의시 *를 붙혀서 인자로 만들고, 함수 내부에서는 리스트로 사용한다.
    2) 함수 호출시, 여러요소를 나열해서 넣어준다.
    3) 함수 호출시, 정의해논 리스트를 넣어줄려면 *를 붙혀서 넣어준다.

normal arg + *args

  • 함수호출시, 여러요소를 리스트처럼 나열해서 넣어 사용 ( [ ] 리스트는 넣으면 안됨)
In [2]:
def test_var_args(first_arg, *args):
    print('첫번째 변수 : ' , first_arg)
    
    for arg in args:
        print('*args 목록 : ', arg)
In [3]:
test_var_args('조재성', '김석영', '조재경', '조아라')
첫번째 변수 :  조재성
*args 목록 :  김석영
*args 목록 :  조재경
*args 목록 :  조아라

미리 만든 리스트를 * 붙혀서 전달하기

In [4]:
param = ['김석영', '조재경','조아라']
test_var_args('조재성', *param)
첫번째 변수 :  조재성
*args 목록 :  김석영
*args 목록 :  조재경
*args 목록 :  조아라

만약 안붙힌 리스트를 \args 자리에 전달하면?

  • 함수내부에서 리스트로서 사용이 안되고, 덩어리체 붙어있다
  • 나열해서 넣어주든지, *를 붙힌 리스트를 넣어준다
In [5]:
test_var_args('조재성', param)
첫번째 변수 :  조재성
*args 목록 :  ['김석영', '조재경', '조아라']

**kwargs의 정의

  • **kwargs : keyworded arguments로 key1=value1, key2=value2 의 요소 나열 or **딕셔너리이 들어가 함수내부에서 딕셔너리로 사용
    1) 함수 정의시 **를 붙혀서 인자로 만들고, 함수 내부에서는 딕셔너리로 사용한다.
    2) 함수 호출시, 여러 요소를 key1=value1 형태로 나열해서 넣어준다.
    3) 함수 호출시, 정의된 딕셔너리를 넣어줄려면 **를 붙혀서 넣어준다.
In [7]:
def greet_me(**kwargs):
    print('kwargs.items() : ',kwargs.items())
    for key, value in kwargs.items():
        print( f'{ key } (key) = { value } (value)')

key=value 형태로 요소를 나열하는 경우

In [8]:
greet_me(name = '조재성', 학교 = '동신대')
kwargs.items() :  dict_items([('name', '조재성'), ('학교', '동신대')])
name (key) = 조재성 (value)
학교 (key) = 동신대 (value)

미리 정의한 딕셔너리에 **를 붙혀 대입

In [9]:
kwargs = { 
         'name' : '조재성',
         '학교' : 'dsu'
}
greet_me(**kwargs)
kwargs.items() :  dict_items([('name', '조재성'), ('학교', 'dsu')])
name (key) = 조재성 (value)
학교 (key) = dsu (value)

만약 딕셔너리만 그대로 넣어버리면?

In [10]:
greet_me(kwargs)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-10-8adf3a7faafc> in <module>
----> 1 greet_me(kwargs)

TypeError: greet_me() takes 0 positional arguments but 1 was given
In [ ]:
 

decorator + 가변길이 인수목록(args, kwargs) 같이 사용하기

decorator복습

  1. decorator함수는 그것을 필요로하는 함수를 인자로 받아, 중복되는 내용과 함께 배치한다.
  2. 중복되는 내용을 decorator로 해결하고 싶은 함수는, @decorator함수 와 같이 정의한다.
  3. 함수를 실행해주면, decorator가 실행된다.

decorator의 문제점

  1. 데코당할 함수의 인자 개수가 같을 때만, 중복으로 사용할 수 있다.
  2. 만약, 함수1과 함수2의 인자 개수가 다를 때는, decorator를 반복해서 사용할 수 없다.

**kwargs 나 *args를 이용하여, 함수1과 함수2의 인자수가 다르더라도 반복해서 decorator를 사용할 수 있다.

  1. decorator로 들어오는 함수를 반복되는 내용으로 wrapper해주는 wrapper함수의 인자를 넣어준다-> 내부에서 중복내용과 배치되는, 들어오는 함수도 인자를 넣어준다.

    • 기존에는 들어오는 함수자체가 인자가 없는 함수를 넣어서 wrapper함수안에서도 함수의 인자 사용안하고 print만 했었다.
  2. func(*args, **kwargs)로 인자를 주면, 순서에 상관없이 *리스트**딕셔너리 아무거나 대입해서 알아서 처리되는 특징

    • 함수의 인자가 한개라도 알아서 처리된다.
    • 인자가 여러개 일 때는, *리스트나 **딕셔너리를 활용한다
    • 인자가 3개이더라도, 초기값만 설정되어있다면, 2개만 넣어줘도 알아서 처리된다.
In [20]:
# decorator 정의
def logging_decorator(func):
    def wrapper_function( *args, **kwargs):
        print( func.__name__ + " 함수가 호출되었습니다.")
        print( "함수호출 결과 : ", func(*args, **kwargs))
    return wrapper_function

# 함수1 정의 with 데코레이터 
@logging_decorator
def square_number(x):
    return x**2

# 함수2 정의 with 데코레이터 
@logging_decorator
def add_numbers(x=3, y=4):
    return x+y

# 함수3 정의 with 데코레이터 
@logging_decorator
def add_number(x, y, z=5):
    return x+y
In [4]:
add_number()
add_number 함수가 호출되었습니다.
함수호출 결과 :  7
In [5]:
# 인자가 한개라도 알아서 처리된다.
square_number(2)
square_number 함수가 호출되었습니다.
함수호출 결과 :  4
In [6]:
add_number(2, 3)
add_number 함수가 호출되었습니다.
함수호출 결과 :  5
In [17]:
# 인자가 여러개  일 때는, *리스트나 **딕셔너리를 활용한다

# 딕셔너리를 대입
add_numbers( **{"x" :6, "y":4})

# 리스트를 대입
add_numbers( *[3, 2])
add_numbers 함수가 호출되었습니다.
함수호출 결과 :  10
add_numbers 함수가 호출되었습니다.
함수호출 결과 :  5
In [21]:
# 인자가 3개이더라도, 초기값만 설정되어있다면, 2개만 넣어줘도 알아서 처리된다.
add_number(1, 2)
add_number 함수가 호출되었습니다.
함수호출 결과 :  3
In [ ]:
 
3. Decorator

Decorator의 정의

  • 각자 다른 함수인데도, 매번 중복해야하는 내용이 있다면
  • 각 함수를 인자로 받은 뒤, 그안에 매번 중복되는 내용과 같이 새로운 함수를 정의하고
  • 그 함수를 return해주는 함수를 만든다.

decoration 안할 경우

  • 매 함수마다 before executing a_func() / after executing a_func() 를 출력하고 싶은데
  • 항상 써줘야한다.
In [22]:
def a_function_requiring_decoration(): 
    print("I am the function which needs some decoration to remove my foul smell") 
 
# 첫줄과 3번째줄은 항상 중복해서 실행시키고 싶다
def b_function(): 
    print("I am doing some boring work before executing a_func()") 
    print("I am the function which needs some decoration to remove my foul smell")   
    print("I am doing some boring work after executing a_func()")
In [5]:
a_function_requiring_decoration()
I am the function which needs some decoration to remove my foul smell
In [6]:
b_function()
I am doing some boring work before executing a_func()
I am the function which needs some decoration to remove my foul smell
I am doing some boring work after executing a_func()
In [ ]:
 

decoration을 쓸 경우

In [27]:
# 1. 중복내용이 필요한 함수(a_func)를 인자로 받는 decorator 함수를 정의한다.
def a_new_decorator(a_func):

    # 2. 들어온 함수와 함꼐 중복해야하는 내용까지 같이 수행하는 내부함수를 새롭게 정의한다.
    def wrapTheFunction(): 
        print("I am doing some boring work before executing a_func()") 
        a_func() 
        print("I am doing some boring work after executing a_func()")
        
    # 3. decorator는 중복해야할 내용까지 포함한 함수를 반환해준다. 
    return wrapTheFunction


# 3. 중복해야하는 내용이 필요한 함수 정의
def a_function_requiring_decoration(): 
    print("I am the function which needs some decoration to remove my foul smell")
In [28]:
# 4. decorator 함수에 , 중복해야하는 작업이 필요한 함수를 인자로 넣고, 새로운 함수를 return로 받자.
a_function_requiring_decoration = a_new_decorator(a_function_requiring_decoration) 

# 5. 그 함수를 실행시켜보자.
a_function_requiring_decoration()
I am doing some boring work before executing a_func()
I am the function which needs some decoration to remove my foul smell
I am doing some boring work after executing a_func()
In [ ]:
 
In [ ]:
 

decorator에 기존함수 대입을 @로 구현

  • decorator가 이미 작성된 상태에서
  • @decorator함수명중복내용을 필요로 하는 함수 정의시 def윗줄에 적어준다.

@decorator 없이 일반 함수 정의

In [30]:
def a_function_requiring_decoration(): 
    """Hey you! Decorate me!""" 
    print("I am the function which needs some decoration to " "remove my foul smell") 
    
a_function_requiring_decoration()
I am the function which needs some decoration to remove my foul smell

@decorator와 같이 정의하면 그 함수는 중복해야할 내용까지 같이 수행한다.

In [21]:
## 중복내용함수에 @decotator와 같이 정의
@a_new_decorator
def a_function_requiring_decoration(): 
    """Hey you! Decorate me!""" 
    print("I am the function which needs some decoration to " "remove my foul smell") 
    
a_function_requiring_decoration()
I am doing some boring work before executing a_func()
I am the function which needs some decoration to remove my foul smell
I am doing some boring work after executing a_func()
In [ ]:
 

실습해보기

In [32]:
def decorator_js(need_func):
    print('decorator에 접속')
    def wrapThefunction():
        print('데코레이터로 매번 사용자 체크 중..')
        
        print('들어온 함수 실행')
        need_func()
        
        print('데코레이터 끝')
    return wrapThefunction
In [33]:
def some_func():
    print('***어떤 함수 작동 중***')
In [34]:
some_func()
***어떤 함수 작동 중***
In [35]:
@decorator_js
def some_func_with_deco():
    print('***어떤 함수 with decorator 작동 중***')
decorator에 접속
In [36]:
some_func_with_deco()
데코레이터로 매번 사용자 체크 중..
들어온 함수 실행
***어떤 함수 with decorator 작동 중***
데코레이터 끝
In [ ]:
 

decorator의 사용

authentication_check라는 함수를 decorator로 만들고, 이곳에서는 웹어플리케이션서의 특정 함수마다 중복해서 수행해야할 내용사용자 인증을 체크한다고 하자. 만약 다른 함수를 실행할 때, 그 함수의 위에다가 위에다가 @authentication_check 만 붙이면, authentication을 알아서 해주게 된다. 즉

In [ ]:
 
2. map, filter, reduce for list

참고 블로그 : https://3months.tistory.com/338?category=753896
참고 사이트 : Intermediate python (http://book.pythontips.com/en/latest/)

MAP

  • map(lambda x: 새로운작업 , list)형태로 iterator를 반환하므로 lambda함수로 기존리스트를 수정한 리스트를
    next()로 하나씩 뽑아내거나, list()로 감싸서 한번에 가져올 수 있다.

map 없이새로운 리스트 반환하기

In [2]:
items = [1, 2, 3, 4, 5]
squared = []

for i in items:
    squared.append(i ** 2)

squared
Out[2]:
[1, 4, 9, 16, 25]

map을 사용하여 수정된 리스트를 한번에 반환

In [5]:
items = [1, 2, 3, 4, 5]
(lambda x : x**2, items)
Out[5]:
(<function __main__.<lambda>(x)>, [1, 2, 3, 4, 5])
In [20]:
square_map = map(lambda x : x**2, items)
square_map
Out[20]:
<map at 0x2e668f65f28>
In [37]:
next(map(lambda x : x**2, items))
Out[37]:
1
In [38]:
list(square_map)
Out[38]:
[1, 4, 9, 16, 25]
In [ ]:
 

Filter

  • filter(lambda x : x조건 , list ) 의 형태로 해당 list에서 조건을 만족시키는 요소만 뽑아올 수 있다. 마지막에는 list() 로 감싸줘야 리스트로 가져온다.
  • comprehension 시 if문을 넣는것과 동일 하다
In [39]:
list_ = range(-5, 5)
list_
Out[39]:
range(-5, 5)
In [42]:
filter( lambda x : x <0, list_)
Out[42]:
<filter at 0x2e668f7a4e0>
In [43]:
list( filter( lambda x : x <0, list_) )
Out[43]:
[-5, -4, -3, -2, -1]
In [45]:
## comprehenshion으로 구현
[ x for x in list_ if x<0 ]
Out[45]:
[-5, -4, -3, -2, -1]
In [ ]:
 

Reduce

  • reduce(lambda x, y : x + y, 순서형 자료-**(리스트, 튜플, 문자열)**)의 형태로 순서대로 x와 y에 차면서, 그결과는 x에 누적되고 새로운 순서의 요소는 y에 들어와서 계산.

1부터 100까지 for문으로 합 구하기

In [47]:
sum_ = 0
for i in range(1, 101):
    sum_ += i
    
sum_
Out[47]:
5050

1부터 100까지 reduce로 구하기

In [49]:
from functools import reduce

# (1) + (2) -> 3+ (3)  -> 6+ (4)
reduce(lambda x, y : x+y, range(1, 101))
Out[49]:
5050
In [50]:
# 다른 예제 - 순서형자료에 list대신 문자열
reduce(lambda x, y : y + x, 'abc')
Out[50]:
'cba'

numpy로 쉽게 구하기

  • 리스트들의 합을 np.sum()으로 구하기 마치 칼럼의 합을 쉽게 구하듯이
In [52]:
import numpy as np

np.sum( [x for x in range(1, 101)] )
Out[52]:
5050
In [ ]:
 

+ Recent posts