[TIL] 95. python 자료구조 및 알고리즘 기본

키워드

• 자료구조
• 알고리즘
• 복잡도, Big O

자료구조

• 데이터를 효율적으로 관리하기 위한 다양한 구조
• 자료구조를 체계적으로 정립하기 위해 프로그래밍 언어별로 다양한 자료형이 발생
• 그 중 가장 기본적인 형태로 배열이 등장하였고, 파이썬에서는 리스트와 튜플을 통해 배열을 구현

 

[자료구조] 리스트(in python)

• 파이썬에서의 리스트는 배열과 연결리스트의 특징을 모두 갖고 있음
• 일반적인 자료구조의 배열 : 인덱스를 통해 노드에 접근 가능
• 연결리스트 : 인덱스의 크기를 자유롭게 확장 가능, 서로 다른 자료형을 가질 수 있음

알고리즘

• 컴퓨터에 내리는 명령의 절차
• 처리의 대상이 되는 것은 입력값 데이터
• 데이터가 메모리에 저장된 후 사용(변수, 함수, 클래스 등에 객체로 저장)

복잡도

1. 공간 복잡도 : 얼마나 많은 저장공간이 필요한지
2. 시간 복잡도 : 얼마나 많은 시간이 걸리는지

• 좋은 알고리즘 : 저장 공간은 적게 쓰되 실행 시간은 짧은(속도가 빠른) 알고리즘
• 공간 복잡도와 시간 복잡도는 반비례하며, 최근엔 하드웨어의 발달로 공간 복잡도보단 시간 복잡도를 우선으로 코드 작성

[복잡도] 시간 복잡도(Big O)

Big O

• 알고리즘의 시간 복잡도를 표현하기 위한 표기법
• Big O 표기법만으로 알고리즘 성능을 예측할 수는 없으나 성능에 대한 정보를 직관적으로 이해할 수 있음

 

간단한 시간복잡도 예시

arr = [1, 2, 3, 4, 5]

# O(1)
def O1(arr):
    print(arr[0])

# O(logN) -> 이중탐색
def Ologn(arr):
    low = 0
    high = len(arr) - 1
    target = int(input())
    if target < arr[low] or target > arr[high]:
        return '값이 범위를 벗어났습니다.'
    else:
        while True:
            mid = (low + high) // 2
            if target < arr[mid]:
                high = mid - 1
            elif target > arr[mid]:
                low = mid + 1
            else:
                return mid

# O(N)
def ON(arr):
    for value in arr:
        print(value)

# O(N^2) -> 이중 반복문
def ON2(arr):
    for value1 in arr:
        for value2 in arr:
            print(value1 * value2)

---

시간 복잡도를 너무 복잡하게 생각하지말고 직관적으로 입력값이 들어갔을 때 알고리즘 내에서 자료가 어떻게 다뤄지는지 생각해보면 편하다!
또한, 시간복잡도를 표현할 때는 보통 최악의 경우를 가정한 시간 복잡도를 나타낸다.(그렇게 해야 대부분의 상황에 대처가 가능하니)