[코테] 알고리즘 공부 Cheat sheet - 0 (자료구조)

Cheat sheet 1 부터 쓰기 시작했는데, 기본 자료 구조 정리를 안해서 이번 편은 0 편이라고 썼습니다.

파이썬 자료 구조 간단 정리 시간을 가져보죠 !

 

 

리스트

가장 많이 쓰이는 동적 배열 자료구조는 리스트(list) 죠

• 순서가 있다.
  • 리스트는 시퀀스형(sequence type) 으로, 요소의 순서가 유지된다.
• 자유로운 추가(append), 삭제(remove), 검색 가능(in, index)
  • append(): 맨 뒤에 요소 추가
  • remove(val): 값이 처음 나타나는 항목 제거
  • in: 존재 여부 확인
  • index(val): 값의 인덱스(위치) 찾기 (단, 값이 없으면 ValueError 발생)
    • in은 존재 여부 확인에 유용하지만, 해당 요소가 어디 있는지를 알고 싶다면 .index()를 써야 합니다.
    • index()는 해당 값이 없을 경우 ValueError를 일으키므로, 존재 확인 후 사용하는 것이 안전합니다
    • ex) if val in my_list: idx = my_list.index(val)

 

• 다양한 자료형 및 중복 허용
  • 정수, 문자열, 리스트 등 어떤 자료형도 요소로 넣을 수 있으며
  • 동일한 값이 여러 번 들어가도 된다.
• in 연산자의 용도 이해가 중요하다
  • for val in my_list: 반복(iteration)
  • val in my_list: 특정 값의 존재 여부 확인

 

# 생성
my_list = [1, 2, 3, 4, 5]

# 추가
my_list.append(6)

# 추가 (여러개를 리스트로 받아서 끝에)
my_list.extend([6, 7])

# 접근
value = my_list[0] # value 는 1

# 검색 (index)
print(my_list.index(5)) #4

# 삭제
my_list.remove(3) # 값이 3인 요소 삭제

# 개수
size = len(my_list)

# 검색 (in)
print(8 in my_list) # False

# 검색 (in + if 조건)
print([value for value in my_list if value < 3])   # [1,2]

 

 

C++ 및 자바에서 봤던 자료구조인 벡터, 스택등을 리스트로 구현해보자

 

 

벡터

Python의 list는 이미 벡터와 비슷한 구조입니다. 크기가 자동으로 늘어나고, 임의 접근도 가능해요.

paired 형식이 필요하면 list 안에 tuple을 넣으면 됨

v = []
v.append((1,2))
v.append((3,4))
print(len(v))
# 2
for p in v:
    print(p)
#(1,2)
#(3,4)

 

 

여기서 잠깐,

이럴거면 우리가 알고 있는 dictionary 를 쓰면 되지않나요?

 

요점 비교

항목	list of tuple	dictionary
예시	[(1, "a"), (2, "b")]	{1: "a", 2: "b"}
순서	유지됨 (삽입 순서 기준)	Python 3.7+ 부터는 유지됨
중복 키	허용됨 (같은 키 여러 개 가능)	불가능 (키는 유일해야 함)
키 기반 접근	불편 (for x in lst if x[0]==...)	빠름 (d[1])
값 변경	튜플이라 변경 불가 (재할당 필요)	가능 (d[1] = "new")
정렬 등 조작	리스트처럼 정렬, 슬라이싱 가능	키/값 단위 조작 위주

 

어떤 상황에 무엇을 써야 할까?

list of tuple이 적합한 경우:

• 중복 키 허용해야 함
• 정렬이 중요함 (예: 점수순 정렬 등)
• 순차 처리가 많음 (e.g., for 루프에서 첫 값, 두 번째 값 등)

 

students = [("Tom", 90), ("Jane", 85), ("Tom", 92)] # 이름 중복 허용

students.sort(key=lambda x: x[1], reverse=True) # 점수순 정렬

 

 

dict가 적합한 경우:

• 키가 유일해야 함
• 키로 빠르게 값을 찾고 싶을 때 (O(1) 접근)
• 값을 자주 갱신하거나 접근할 일이 많을 때

grades = {"Tom": 90, "Jane": 85} grades["Tom"] = 95 # 쉽게 갱신

print(grades["Tom"]) # 빠르게 접근

 

 

 

 

스택

그냥 리스트로 구현 후,  접근시 my_list[-1],  삭제시 my_list.pop(-1) 으로 빼면 됩니다.

(참고로 python 에서 음수 인덱스는 리스트나 문자열에서 역순으로 접근을 가능하게 하는 방법입니다.)

s = []
s.append(1)
s.append(2)
s.append(3)
print(len(s))
# 3
while len(s) > 0 :
    print(s[-1])
    s.pop(-1)
# 3
# 2
# 1

 

큐

deque

thread safe 한 Queue 보다 빠름.  앞, 뒤로 넣고 빼고 다 됨

  

메서드	설명	예시
append(x)	오른쪽에 추가	dq.append(1)
appendleft(x)	왼쪽에 추가	dq.appendleft(2)
pop()	오른쪽에서 꺼냄	dq.pop()
popleft()	왼쪽에서 꺼냄	dq.popleft()

 

from collections import deque

q = deque()
q.append(1)
q.appendleft(2)
q.pop()
q.popleft()

 

heapq

우선순위 큐를 써야할 땐? - heapq 를 쓰면 되죠

import heapq

pq = [1,2,8]

heapq.heappush(pq, 6)
while pq:
    print(heapq.heappop(pq))
# 1
# 2
# 6
# 8

 

위와 같이 파이썬의 heapq 는 기본이 최소 힙(min heap) 이므로, 최대 힙은 아래와 같이 편법으로 사용 가능하다.

from heapq import heappush, heappop
import heapq

nums = [1,2,6,8]

### 방법 1
heap = []

for num in nums:
	heappush(heap, (-num, num)) # (우선순위, 값) pair 값을 넣더라도 앞자리부터 소팅해주는 점을 이용한 것
  
while heap:
	print(heappop(heap)[1])
# 8
# 6 
# 2
# 1

### 방법 2
max_heap = [-num for num in nums]

heapq.heapify(max_heap)

while max_heap:
    print(-heappop(max_heap))
# 8
# 6 
# 2
# 1

 

맵

C++ 에서 키, 값으로 이루어진 맵 구조는 위에서 잠깐 나왔던 dict 로 구현할 수 있다

단, 해시기반이라 immutable 한 객체면 (int 같은 값. 그리고 tuple 은 됨) 키로 쓸 수 있다

• 선언은 {} 나 dict() 로 가능
• 추가 my_dict["키"] = value, 읽기 my_dict["키"] 으로 가능
• 순서는 보장하지 않는다고 생각하자
• for key in my_dict 하면 키카 튀어나옴
• for val in my_dict.values() 하면 값이 튀어나옴
• for k, v in my_dict.items() 하면 둘 다 튀어나옴
• 'key' in my_dict : 유무 True/False
• 삭제 del my_dict['key'] 

 

# 딕셔너리 예시
my_dict = {'a': 1, 'b': 2, 'c': 3}

# 1. for key in my_dict → 키만 순회
for key in my_dict:
    print(key)  # 'a', 'b', 'c'

# 2. for val in my_dict.values() → 값만 순회
for val in my_dict.values():
    print(val)  # 1, 2, 3

# 3. for k, v in my_dict.items() → 키와 값 쌍 순회
for k, v in my_dict.items():
    print(k, v)  # ('a', 1), ('b', 2), ...

# 4. 'key' in my_dict → 키 존재 여부 확인
print('a' in my_dict)  # True
print('z' in my_dict)  # False

# 5. del my_dict['key'] → 키-값 쌍 삭제
del my_dict['a']  # 'a': 1 항목이 삭제됨

 

딕셔너리를 제대로 알고 가시려면 여기로~~~

https://ohollama.tistory.com/107

파이썬 딕셔너리, 제대로 알자. 해시 구조부터 실전 까지

 

 

 

 

set 도 중요하니 별도의 글에서 다뤄볼까요?

 

https://ohollama.tistory.com/103

[코테] set