[n514] 필수적인 자료 구조

파이썬의 리스트

• 자료구조의 기본은 배열이라 할 수 있고, 파이썬에서는 리스트와 튜플로 구현할 수 있다.
• 리스트나 튜플의 핵심은 인덱스를 사용하는 것이다.

# 리스트 인덱싱/슬라이싱 예시

example = [10, 20, 30, 40, 50]

print('example[0:3] 결과:', example[0:3])
print('example[::2] 결과:', example[::2])
print('example[0:1:3] 결과:', example[0:1:3])
print('example[-3] 결과:', example[-3])
print('example[-3:-1] 결과:', example[-3:-1])

example[0:3] 결과: [10, 20, 30]
example[::2] 결과: [10, 30, 50]
example[0:1:3] 결과: [10]
example[-3] 결과: 30
example[-3:-1] 결과: [30, 40]

 

 

Big O 표기법(notation)

[시간 복잡도] 알고리즘 복잡도 표현 방법

• 알고리즘 실행 효율성을 측정하기 위한 알고리즘 계산 복잡도
  • 시간 복잡도 : 최악의 케이스일 때 실행 시간을 측정.
  • 공간 복잡도 : 필요한 메모리 공간을 측정. 최근에는 하드웨어 고성능으로 인해서 중요도가 낮아졌다. 거의 사용하지 않는다. 

• Contanst Time(상수시간) : O(1) - 입력 값에 상관 없이 한번 실행 하는 경우

def print_one_item(items):
    print(items[1])       # 상수시간(단순하게 하나의 출력)

print_one_item([0,1,2])

 

• Linear Time(선형시간) : O(n) - 입력 값에 따라서 실행 시간도 증가한다. 

def print_every_item(items):
    for item in items:  # 하나의 반복문
        print(item)

print_every_item([0,1,2])

 

• Quadratic Time(제곱시간) : O(n^2) 

def print_pairs(items):
    for item_one in items:      # 중첩반복문
        for item_two in items:
            print(item_one, item_two)

print_pairs([0,1,2])