시간복잡도

데이터 케이스에 따라, 작성한 코드가 완료되기까지 시간이 얼마나 걸리는지를 나타낸 값.

블리츠크랭크: "시간이. 얼마나. 걸리는지."

빅오메가 표기법과 빅오 표기법이 존재한다.
빅오메가는 가장 효율적일 때의 시간복잡도를 나타내고, 빅오는 가장 비효율적일 때의 시간복잡도를 나타낸다. 우리는 주로 빅오 표기법을 사용한다.

표기할 때 상수는 크게 의미없다.
데이터 케이스가 무한으로 커진다고 가정한다면, 상수는 먼지에 수렴한다.

일반적으로 이중반복문이면 N^2으로 착각하는 경향이 있는데, 이는 잘못된 계산이다. 반복문의 횟수가 상수값일 수도 있고, 이진탐색처럼 log일 수도 있다.

링크드 리스트

Node라는 구조체로 연결된 리스트 형태의 자료구조.

Node = Data + Next Node(pointer)

연결 리스트라고도 불린다. C에서 Pointer를 배울 때 함께 알게된 자료구조였는데, 배열과는 다르게 붙이고, 자르고 를 자유롭게 할 수 있다는 점이 매력적이었다. (덕분에 Pointer 개념도 잘 이해할 수 있었다.)

링크드 리스트 형태의 Queue나 Stack을 만들 때 사용되기도 한다.

업그레이드 버전으로, 이중 연결 리스트도 있다. Node안에 이전 노드의 포인터가 추가된 형태다.

재귀함수

함수 내부에서, 함수 자신을 다시 호출하는 형식의 함수.

대표적인 예시로 factorial, fibonacci, 회문검사 등이 있다.
f(N) = n ∙ f(N - 1) 로 표현되는 문제들은 재귀로 해결할 수 있다. 큰 문제는 결국 작은 문제들의 연속이라는 것만 파악하면, 생각보다 난이도가 어렵지 않게 느껴진다.
일반적인 단점으로, 함수스택을 여러 개 쌓고 푸는 과정에서 자원소모가 크다는 것이다. 그리고 반복문으로 구현할 수 있다는 점에서, 성능상 이슈를 고려한다면 재귀를 많이 사용하진 않는 듯 하다.

# 팩토리얼

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

이진탐색

범위의 절반을 기준으로 up & down 방식으로 탐색하는 방법.

개인적으로 처음 알게되었을 때 충격적인 탐색법이었다.
엄청난 속도로 원하는 값을 찾아내는 과정에서 감탄할 수 밖에 없었다.
겁나 빠르지만 사용 조건으로, 정렬된 상태 여야한다.

# 이진 탐색으로 target이 되는 수 찾기

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    arr_min = array[0]
    arr_max = array[len(array) - 1]
    while arr_min <= arr_max:
        arr_mid = (arr_min + arr_max) // 2
        if target > arr_mid:
            arr_min = arr_mid + 1
        elif target < arr_mid:
            arr_max = arr_mid - 1
        else:
            return True
    else:
        return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

기타

python 문법

• 함수 내부에서 전역 변수를 사용
  : 변수명 앞에 global 추가.
• for문 n번 만큼 반복
  : for i in range(len(n)):
• 배열 for 문에서 index와 value 모두 접근하는 방법

for i, value in enumerate(array):
  print(i, data)

for data in enumerate(array):
  print(type(data))	# tuple

• swap
  : a,b = b,a
• for문 index 역순

for i in range(5, -1, -1):	# range(start, end, step)
  print(i)			# 4, 3, 2, 1, 0