공부정리

python에서 배열을 순회할때 인덱스와 값을 같이 가져올 수 있습니다.

javascript에서 forEach, map 과 같이 순회하는 함수에서 또한 value, index를 같이 가져올수 있습니다.

enumerate 내장함수를 이용하면 됩니다.

l = [1,2,3]

for index, val in enumerate(l) :
	print(index, val)
    

# 0 1
# 1 2
# 2 3

두개의 배열을 같이 순회하면서 같은 인덱스의 값을 비교하고 싶을때도 있을수 있습니다.

그때는 zip 내장함수를 이용하면 됩니다.

a = [1,1,1]
b = [2,2,2]

for i,j in zip(a, b) :
  print(i,j)
  
  
 # 1 2
 # 1 2
 # 1 2

아래 문제를 풀면서 python format 관련하여 정리한 내용입니다.

https://dkrnfls.tistory.com/140

javascript의 template literal을 굉장히 편하게 쓰고 있다. 

python에도 있을까 찾아봤는데 역시나 있었다. 아래의 이미지 처럼 사용하면 됩니다.

python에서 소수점을 출력할 때마다 항상 구글링을 통해서 찾아보았다. 

앞으로는 좀 더 머리에 각인 시키기 위해 정리를 해보자

"{파라미터 위치:전체자릿수:소수점 이하 자릿수}".format(parameter)

전체 자릿수에는 .을 포함합니다. 07이면 .을 포함한 7자리 이므로 40.0000 으로 출력이 됩니다.

0을 입력해주지 않으면 빈자리로 채워줍니다. 

3.141592 를 반올림하여 소수점 4번째 자리까지 출력하는 코드는????? (드래그하면 보입니다)

print("{0:.4f}".format(round(3.141592, 4)))  or  print("{}".format(round(3.141592, 4)))

* 잘못된 정보가 있으면 말씀해주세요. 빠른 반영 하겠습니다!

이진탐색을 사용하면 O(logn)의 시간복잡도를 가지게 되는데요

[0, 10, 20, 30, 40, 41, 42, 42, 43, 44, 45, 50, 60, 61] 의 배열이 있다고 가정하겠습니다

50을 찾겠습니다.

1. 중간값 42와 50을 비교 -> 42보다 50이 큼 -> [42, 43, 44, 45, 50, 60, 61]에서 찾음

2. [42, 43, 44, 45, 50, 60]의 중간값 44 와 50을 비교 -> 44보다 50이 큼 -> [45, 50, 60, 61]에서 찾음

3. [45, 50, 60, 61] 의 중간값 60과 50을 비교 -> 60이 50보다 큼 -> [45, 50]에서 찾음

4. [45, 50]의 중간값 45와 50을 비교 -> 45가 50보다 작음 -> [50]에서 찾음

5. [50]의 중간값 50과 50을 비교 -> 찾음

이진 탐색이란 이름이 붙은 이유는 

배열의 크기가 절반씩 줄어들기 때문입니다.

배열의 크기가 14, 7, 4, 2, 1 로 절반씩 줄어드는 것을 확인할수 있습니다.

시간 복잡도를 살펴보자면 

연산의 횟수가 곧 시간 복잡도가 될것입니다.

N, N/2, N/4, N/8, .....1 로 줄어드는 것을 확인할 수 있고

1 에 2^x 를 하면 N이 될것입니다.

2^x = N 여기에 밑이 2인 log를 곱해주면

x = logN 가 되겠지요 

따라서 이진 탐색의 시간복잡도는 O(logN)이 되게 됩니다.

아래에서 코드로 살펴보겠습니다.

from bisect import bisect_left, bisect_right

# 재귀호출로 구현한 이진 탐색입니다.
def binary_search_with_recursion(array, target, start, end):
  mid = (start + end) // 2
  if array[mid] == target :
    return mid
  if array[mid] > target :
    return binary_search_with_recursion(array, target, start, mid - 1)
  elif array[mid] < target :
    return binary_search_with_recursion(array, target, mid, end)

# while문으로 구현한 이진 탐색입니다.
def binary_search_with_while(array, target):
  start, end = 0, len(array) - 1
  while start < end :
    mid = (start + end) // 2
    if array[mid] > target :
      end = mid - 1
    elif array[mid] < target :
      start = mid
    else :
      start = end = mid
  return end

array = [0, 10, 20, 30, 40, 41, 42, 42, 43, 44, 45, 50, 60, 61]

print(bisect_left(array, 50)) # 11
print(bisect_right(array, 50)) # 12
print(binary_search_with_recursion(array, 50, 0, len(array) - 1)) # 11
print(binary_search_with_while(array, 50)) # 11

이진탐색을 구현한 4개의 방법을 알아보겠습니다.

1번은 재귀호출로 구현한 코드

2번은 while문으로 구현한 코드

재귀 함수 호출과 while문을 선택해서 사용할 수 있는 경우라면 while문을 이용하여 구현하는것이 좋습니다.

재귀 함수 호출은 함수가 호출될때마다 함수의 매개변수에 대한 위치정보와 리턴 값에 대한 위치정보가 계속해서 쌓이게 됩니다

100   a = 3

99     b = 3

98     return = 1 (최종 나가는 위치)

97     a = 4

96     b = 4

95     return = 100

94     a = 5

95     b = 5

94     return = 97

이런식으로 (정확한 예시는 아닙니다. 좀 더 공부하고 잘 표현할수 있도록 수정할게요) 스택이 계속 차지하게 되고 스택이 터지면 스택 오버플로우가 발생할 거에요,

또한 함수가 호출되고 나서 종료될때 스택부분을 해제해야하는데 이것에 대한 오버헤드가 발생하게 될거에요. 미묘하지만 작은게 모이면 부하가 걸릴겁니다.

반복문은 지역변수들이 호출될때 한번만 할당되기 때문에 그리고 스택내부에 할당된 변수들의 값만 반복문이 실행되면서 갱신해주기 때문에 다른 요인이 아닌 이상 스택이 터지는 경우는 발생하지 않을겁니다.

경우에 따라 사용하시면 될것 같아요. 저는 재귀호출을 선호합니다 ㅎㅎ 

3번은 bisect 라이브러리의 bisect_left 메소드

* 타겟값의 왼쪽 인덱스를 반환해 줍니다.

4번은 bisect 라이브러리의 bisect_right 메소드

* 타겟값의 왼쪽 인덱스를 반환해 줍니다.

https://docs.python.org/ko/3/library/bisect.html

python에서 Filter   

javascript에서 filter를 즐겨 쓰다보니 python에서도 filter를 계속 찾게된다.    
아직 익숙치 않아 매번 블로그 뒤지고 있어서 이 참에 한번 깔끔하게 정리해보자    

실제 활용 예시 먼저!!!   

import re

s = "one2three4five6"
print(list(re.split('(\d)', s))) # ['one', '2', 'three', '4', 'five', '6', '']

print(list(filter(lambda x: x != '', list(re.split('(\d)', s))))) # ['one', '2', 'three', '4', 'five', '6']

• 최근 정규 표현식 라이브러리를 사용하려 하고 있다. 
• re.split을 하면 split 구문이기 때문에 경우에 따라 뒤에 ''가 들어온다. (split안의 내용은 구문중 숫자로 구문을 split한다는 거다)  
• 이걸 해결하기 위해 filter를 사용한다.  

python의 filter

아래는 파이썬 도큐에 나와있는 filter에 관한 내용

filter(function, iterable)
Construct an iterator from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator. If function is None, the identity function is assumed, that is, all elements of iterable that are false are removed.

Note that filter(function, iterable) is equivalent to the generator expression (item for item in iterable if function(item)) if function is not None and (item for item in iterable if item) if function is None.

See itertools.filterfalse() for the complementary function that returns elements of iterable for which function returns false.

앞에 Function이 들어온다. 그걸 lambda로 대신해주었다. (lambda는 아직 익숙치 않다....)

function을 사용한 예시를 살펴보자

def func(x) :
  if x > 0 :
    return True
  else :
    return False

array = [-2, -1, 0, 1, 2]
print(list(filter(func, array))) # [1,2]
print(list(filter(lambda x: x > 0, array))) # [1,2]

코드에 두가지 예시를 넣어두었다. function을 넣은것과 lambda를 이용한 것

출처: https://docs.python.org/3/library/ast.html#ast.literal_eval