3 알고리즘의 효율분석

3-1 시간 복잡도란?

입력값과 연산 횟수의 상관관계에 따라 성능을 측정하는 것
알고리즘의 성능을 나타내느 지표,
낮으면 낮을 수록 좋다.

1차원 배열 검색하기

값을 가장 빨리 찾는 경우는 찾고자하는 값이 배열 1번째 위치해 있을 경우
값을 가장 늦게 찾는 경우는 찾고자하는 값이 없거나 배열 맨 마지막에 위치하는 경우

알고리즘 수행 시간을 측정하는 방법

절대 시간 츶정하는 방법, 시간 복잡도로 측정하는 방법

절대 시간을 측정하는 방법

말 그대로 시간을 측정하는 방식

시간 복잡도를 측정하는 방법

연산 횟수와 관련있음
시간 복잡도를 측정한 결과는 최선, 보통, 최악으로 나눔
점근적 표기법이란 ? 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내는 방식으로 입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도를 표현하는 방법

최악의 경우 시간 복잡도를 표현하는 빅오표기법

상한선을 활용하는 방법인 점근적 표기법을 빅오 표기법이라함
함수의 최고차항을 남기고 차수를 지워 O(...)와 같이 표기하면됨
n^2+3n+5 를 코드로 표현

def solution(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    for k in range(n):
        count += 1
    for i in range(2*n):
        count += 1
    for i in range(5):
        count += 1
    print(count)

solution(6) # n이 6일 때, 6^2 + 6 + 2*6 + 5 = 59

시간 복잡도는 기울기?

3-2 시간 복잡도 계산해보기

문제 정의
연산 횟수 측정
시간 복잡도 분석

별찍기 문제

f(N) = 1 + 2 + ... + N = N(N+1)/2

박테리아 수명 문제

Y년 후의 박테리아 수 : (1/2)^Y*N
logN의 시간 복잡도를 가짐

4 코딩 테스트 필수 문법

4-1 빌트인 데이터타입

빌트인 데이터 타입(언어 자체에서 제공하는 데이터 타입) : 정수형, 부동 소수형, 문자열 타입
컬렉션 데이터타입: 리스트 튜플, 셋, 딕셔너리 등

정수형 비트 연산

a = 13
b = 4

print(a & b) # 마지막 수가 출력된다.
print(a | b) # or 처음의 수가 출력된다.

print(a ^ b) # XOR
~a
a << 2  # 2bit left shift
a >> 1

a and b   # a & b 와 같음
a or b    # a | b 와 같음
not a     # 결과는 True, False

부동 소수형

4-2 컬렉션 데이터타입

변경할 수 있는 객체(뮤터블), 변경할 수 없는 객체(이뮤터블)로 구분함

뮤터블 객체

리스트, 딕셔너리 ,셋

이뮤터블 객체

정수, 부동소수점, 문자열, 튜플

4-3 함수

# 함수 정의
def function_name(param1, param2):
    # ...
    return result # 반환값

# 함수 호출
def add(num1,num2):
    result = num1 + num2
    return result

ret = add(2, 3)
print(ret) # 15

람다식

함수를 더 간단히 표현하는 방법
한번만 사용하거나 함수를 인자로 넘겨야할 경우 유용함!

lambda x, y : x + y # x와 y를 받아서 더한 값을 반환하는 람다식

변수에 람다식을 할당하고 람다식 실행이 필요한 경우, 변수 (a, b)

add = lambda x, y : x + y
print(add(5,4)) # 9

인수로 람다식을 넘기는 방법

num = [1,2,3,4,5]
aquares = list(map(lambda x: x**2, num))
print(squares) # [1, 4, 9, 16, 25]

코딩 테스트 코드 구현 노하우

조기반환하기

def total_price(quantity, price):
    total = quantity * price # 1
    if total > 100: # 2 total이 100보다 크면
        return total * 0.9 # 3 조기반환
    return total

print(total_price(4, 50))

보호구문 guard clauses

본격적인 로직을 진행하기 전 예외 처리 코드를 추가하는 기법

def calculate_average(nums):
    if nums is None: # 1 값이 없으면 종료(예외)
        return None
    if not isinstance(nums, list): # 2 nums가 리스트가 아니면 종료(예외)
        return None
    if len(nums) == 0: # 3 nums가 길이가 0이면 종료(예외)
        return None

    total = sum(nums) # 4 예외를 잘 고려한 후 동작 구현에만 집중하기
    average = total / len(nums)
    return average

예외처리 습관화하기!

합성함수 composite method

2개 이상의 함수를 활용하여 함수를 추가로 만드는 기법

def add_three(x): # 1
    return x + 3

def square(x): # 2
    return x * x

composed_function = lambda x : square(add_three(x)) # 3
print(composed_function(3)) # 4  (3 + 3)^2 = 36

1,2에서 2개의 함수를 정의한 후 3에서 합성하여 하나의 함수를 활용하는 것처럼 호출함
작은 기능은 분리해서 코드를 작성함으로 관리자는 코드를 쉽게 관리하고 함수를 사용하는 사용자는 코드를 쉽게 사용할 수 있다.

5 배열

5-1 배열 개념

익덱스와 값을 일대일 대응해 관리하는 자료구조

# 배열 선언
arr = [0,0,0]
arr = [0] * 3 # 위랑 결과값 동일

# 리스트 생성자를 사용하는 방법
arr = list(range(6)) # [0, 1, 2, 3, 4, 5]

# 리스트 컴프리헨션을 활용하는 방법
arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0]

배열과 차원

배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당된다.

2차원 배열

1차원 배열을 확장한 것

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# arr[2][3]에 저장된 값 출력
print(arr[2][3]) # 12

# arr[2][3]에 저장된 값을 15로 변경
arr[2][3] = 15

print(arr[2][3]) # 15

리스트 컴프리헨션 활용하여 크기가 3 * 4인 리스트 선언

arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

5-2 배열의 효율성

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있으므로 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.
배열은 데이터를 어디에 저장하냐에 따라 추가 연산에 대한 시간 복잡도가 달라짐
데이터를 맨뒤에 삽입할 경우 다른 데이터에 영향을 주지않으므로 시간복잡도는 O(1)이지만 맨 앞이나 중간에 삽입할 경우는 삽입할 데이터 뒤 인덱스인 데이터의 개수를 N개라 했을 때 시간 복잡도는 O(N)이다.
현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 하기 때문

배열을 선택할 때 고려할 점

할당할 수 있는 메모리 크기를 확인해야한다.
중간에 데이터 삽입이 많은지 확인해야 한다.

5-3 자주 활용하는 리스트 기법

리스트에 데이터 추가

append()
+ 연산자
insert()

리스트에서 데이터 삭제

pop()
remove()

리스트 컴프리헨션으로 데이터에 특정 연산 적용

리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐 연산 대상 리스트를 바꾸지 않는다.

nums = [1, 2, 3, 4, 5]
squares = [ num**2 for num in nums ] # [1, 4, 9, 16, 25]

특정 데이터가 처음 등장한 인덱스를 반환하는 index() 없으면 -1 반환

코딩테스트 합격자되기 3,4,5장 [with 묘공단]