python

자료구조와 알고리즘 학습 Day 1

자료구조와 알고리즘 학습 Day 1입니다. Big-O, Python list, stack, queue, deque, dict, set과 첫날 연습 문제를 정리했습니다.

devmes

• 조회 239

자료구조와 알고리즘 학습 Day 1

Day 1에서는 자료구조를 외우기보다 데이터를 어떻게 담고, 어떤 연산이 얼마나 비싼가를 기준으로 정리한다. Python으로 시작하면 list, dict, set만 제대로 이해해도 이후 stack, queue, hash table, graph 개념으로 넘어가기 쉽다.

Big-O를 먼저 보는 이유

Big-O는 입력 크기가 커질 때 실행 시간이 어떻게 증가하는지 설명하는 표기다. 정확한 초 단위가 아니라 증가 경향을 비교한다.

O(1)      입력 크기와 관계없이 거의 일정
O(log n)  절반씩 줄이며 탐색
O(n)      전체를 한 번 순회
O(n log n) 일반적인 효율적 정렬
O(n^2)    중첩 반복으로 모든 쌍 비교

Python list

Python의 list는 동적 배열이다. index 접근은 빠르지만, 맨 앞 삽입/삭제는 뒤쪽 원소를 이동해야 해서 비용이 커진다.

numbers = [10, 20, 30]

print(numbers[0])      # O(1)
numbers.append(40)     # 평균 O(1)
numbers.pop()          # O(1)
numbers.insert(0, 5)   # O(n)
numbers.pop(0)         # O(n)

Stack

Stack은 마지막에 넣은 데이터를 먼저 꺼내는 LIFO 구조다. Python list의 append, pop으로 간단히 표현할 수 있다.

stack = []
stack.append("login")
stack.append("open dashboard")
stack.append("edit post")

print(stack.pop())  # edit post
print(stack.pop())  # open dashboard

Queue

Queue는 먼저 들어온 데이터를 먼저 처리하는 FIFO 구조다. list의 pop(0)은 비효율적이므로 collections.deque를 사용한다.

from collections import deque

queue = deque()
queue.append("job-1")
queue.append("job-2")
queue.append("job-3")

print(queue.popleft())  # job-1
print(queue.popleft())  # job-2

dict와 set

dict와 set은 hash table 기반이다. 평균적으로 조회가 빠르기 때문에 ID로 데이터 찾기, 중복 제거, membership test에 자주 쓴다.

users = {
    "alice": {"role": "admin"},
    "bob": {"role": "viewer"},
}

print(users["alice"])
print("bob" in users)

tags = ["linux", "python", "linux", "network"]
unique_tags = set(tags)
print(unique_tags)

Day 1 연습 문제

  1. list에 숫자 10개를 넣고 최대값, 최소값, 합계를 직접 구한다.
  2. stack으로 브라우저 뒤로가기 기록을 흉내 낸다.
  3. deque로 작업 큐를 만들고 순서대로 처리한다.
  4. dict로 사용자 이름과 권한을 저장하고 특정 사용자의 권한을 조회한다.
  5. set으로 중복 태그를 제거한다.
BGM EVER