Data Structure

---

1. 데이터 구조 전체 그림

1-1. 데이터 구조란?

• 프로그램 안에서 데이터를 어떻게 담아둘지 정해놓은 틀.
• 파이썬에서 자주 쓰는 기본 데이터 구조:
  • 시퀀스(순서 있는 것): str, list, tuple
  • 비시퀀스(순서 중요X): dict, set

같은 데이터를 넣더라도 어떤 구조를 쓰느냐에 따라

• 어떤 작업이 빠른지
• 어떤 문법을 쓸 수 있는지
  이 달라진다.

---

2. 메서드 개념

2-1. 메서드란?

• “객체에 붙어 있는 함수”.
• 문법: 객체.메서드(인자들)
  • 예: 'hello'.capitalize()
• 이 함수는 그 객체를 기준으로 동작한다는 게 포인트.

예를 들어,

text = "hello"
print(text.capitalize())   # "Hello"

여기서 capitalize는 문자열 객체가 스스로 동작하는 느낌이다.

---

3. 시퀀스 데이터 구조 – 문자열(str)

문자열은 “글자들이 순서대로 나열된 것” + 불변(immutable) 이라는 특징이 있다.
즉, 한 번 만들어진 문자열 자체는 바뀌지 않고, 항상 새 문자열을 만들어서 결과를 준다.

3-1. 조회/탐색 계열 메서드

(1) .find(x)

• 문자열 안에서 부분 문자열 x가 처음 등장하는 위치(인덱스)를 반환.
• 못 찾으면 -1.

print('banana'.find('a'))  # 1 (첫 번째 a)
print('banana'.find('z'))  # -1

(2) .index(x)

• 역할은 find와 거의 같지만,
• 못 찾으면 ValueError 예외를 발생시킨다.

print('banana'.index('a'))  # 1
print('banana'.index('z'))  # 에러 발생 (substring not found)

→ 정리:

• “없으면 그냥 -1이면 좋겠다” → find
• “무조건 있어야 하는 값”이라서 없을 때 에러로 잡고 싶다 → index

(3) .isupper(), .islower()

• 문자열이 전부 대문자/소문자인지를 True/False로 반환.

s1 = 'HELLO'
s2 = 'Hello'
s3 = 'hello'

print(s1.isupper())  # True
print(s2.isupper())  # False
print(s3.islower())  # True

(4) .isalpha()

• 문자열이 알파벳 문자로만 구성되어 있는지 확인.

print('hello'.isalpha())  # True
print('hello123'.isalpha())  # False
print('123'.isalpha())  # False

---

3-2. 문자열 조작 메서드

(1) .replace(old, new[, count])

• 문자열에서 old 부분을 찾아 new로 바꾼 새 문자열을 반환.
• count를 쓰면, 앞에서부터 count번까지만 바꾼다.

text = "hello, world, world"
print(text.replace("world", "python"))
# "hello, python, python"

print(text.replace("world", "python", 1))
# "hello, python, world"

(2) .strip([chars])

• 문자열 앞뒤에 있는 공백(또는 지정한 문자들)을 제거한 새 문자열을 만든다.

text = "   hello   "
print(text.strip())   # "hello"

text2 = "!!!hello!!!"
print(text2.strip("!"))  # "hello"

• 앞/뒤 중 한쪽만 제거하고 싶으면 .lstrip(), .rstrip() 도 있다.

(3) .split(sep=None, maxsplit=-1)

• 문자열을 sep 기준으로 잘라서 리스트로 반환.
• sep 없으면 공백(스페이스, 탭, 줄바꿈 등)을 기준으로 쪼갠다.
• maxsplit을 지정하면 그 횟수만큼만 나눈다.

text = "hello world python"
print(text.split())      # ['hello', 'world', 'python']

text2 = "a,b,c,d"
print(text2.split(','))       # ['a', 'b', 'c', 'd']
print(text2.split(',', 2))    # ['a', 'b', 'c,d']

(4) '구분자'.join(iterable)

• 문자열 리스트 등을 특정 구분자로 이어붙일 때 사용.
• 반대로 말하면, split의 역방향 느낌.

words = ['hello', 'world']
print(' '.join(words))   # "hello world"
print(','.join(words))   # "hello,world"

---

4. 리스트(list) – 시퀀스 + 가변(mutable) 구조

리스트는 순서가 있고, 수정 가능한 데이터 구조.
삽입, 삭제, 정렬 등 다양한 메서드를 제공한다.

4-1. 원소 추가/삭제 메서드

(1) .append(x)

• 맨 뒤에 한 요소 추가.

my_list = [1, 2, 3]
my_list.append(4)
print(my_list)  # [1, 2, 3, 4]

(2) .extend(iterable)

• 다른 리스트/튜플 같은 반복 가능한(iterable) 객체의 모든 요소를 뒤에 붙인다.

my_list = [1, 2, 3]
my_list.extend([4, 5, 6])
print(my_list)  # [1, 2, 3, 4, 5, 6]

append vs extend 차이

• append([4, 5, 6]) → 리스트 안에 또 리스트가 하나 들어감: [1, 2, 3, [4, 5, 6]]
• extend([4, 5, 6]) → 요소들이 낱개로 풀려서 들어감: [1, 2, 3, 4, 5, 6]

(3) .insert(i, x)

• 인덱스 i 위치에 x를 끼워 넣는다.

my_list = [1, 2, 3]
my_list.insert(1, 99)   # 인덱스 1 자리에 99 삽입
print(my_list)          # [1, 99, 2, 3]

(4) .remove(x)

• 값이 x인 첫 번째 요소를 삭제.
• 없으면 에러(ValueError).

my_list = [1, 2, 3, 2]
my_list.remove(2)
print(my_list)  # [1, 3, 2]

(5) .pop(i=-1)

• 인덱스 i 위치의 요소를 삭제하면서 그 값을 반환.
• 인덱스를 주지 않으면 맨 뒤(-1)를 삭제.

my_list = [1, 2, 3]
x = my_list.pop()      # 3 삭제 & 반환
print(x)               # 3
print(my_list)         # [1, 2]

y = my_list.pop(0)     # 1 삭제 & 반환
print(y, my_list)      # 1 [2]

(6) .clear()

• 리스트의 모든 요소 삭제(리스트를 빈 리스트로 만든다).

my_list = [1, 2, 3]
my_list.clear()
print(my_list)  # []

---

4-2. 탐색/정렬 메서드

(1) .index(x)

• 리스트에서 값이 x인 첫 요소의 인덱스를 반환.
• 없으면 ValueError.

my_list = [1, 2, 3, 2]
print(my_list.index(2))  # 1

(2) .count(x)

• 리스트 안에 x가 몇 번 등장하는지 반환.

my_list = [1, 2, 2, 3, 2]
print(my_list.count(2))  # 3

(3) .reverse()

• 리스트를 제자리에서 역순으로 뒤집는다.
• 반환값은 None (새 리스트를 돌려주지 않는다).

my_list = [1, 2, 3]
my_list.reverse()
print(my_list)           # [3, 2, 1]

(4) .sort()

• 리스트를 제자리에서 정렬.
• reverse=True 옵션으로 내림차순 가능.

my_list = [3, 1, 2]
my_list.sort()
print(my_list)           # [1, 2, 3]

my_list.sort(reverse=True)
print(my_list)           # [3, 2, 1]

• 새 리스트가 필요하면 sorted(my_list) 사용 (원본 유지).

---

5. 객체와 참조, mutable/immutable, 복사

5-1. mutable vs immutable

• mutable(가변): 내용(내부 값)을 바꿀 수 있는 객체
  • 대표: list, dict, set
• immutable(불변): 한 번 만들어진 값 자체를 바꿀 수 없는 객체
  • 대표: int, float, str, tuple

중요한 포인트

• 파이썬 변수는 “박스에 값을 복사해서 넣는 느낌”이 아니라,
  “객체를 가리키는 이름표를 붙여 놓는 느낌(참조)”이다.

a = [1, 2, 3]
b = a
b.append(4)
print(a)  # [1, 2, 3, 4]
print(b)  # [1, 2, 3, 4]
print(a is b)  # True  (같은 객체를 가리킴)

• a와 b는 같은 리스트를 가리키는 두 개의 이름표일 뿐이라,
  한쪽에서 수정하면 다른 쪽도 바뀐 것처럼 보인다.

---

5-2. 얕은 복사(Shallow Copy)

얕은 복사는 겉껍질만 새로운 객체로 만들고,
그 안에 들어있는 내부 요소(특히 리스트 안의 리스트)는 그대로 공유한다.

구현 방법 예시:

a = [1, 2, 3]
b = a[:]          # 슬라이싱으로 얕은 복사
c = list(a)       # 생성자로 복사

(1) 1차원 리스트일 때

a = [1, 2, 3]
b = a[:]

b[0] = 100
print(a)  # [1, 2, 3]
print(b)  # [100, 2, 3]
print(a is b)  # False

• 이 경우에는 괜찮다. 값 타입이니까 서로 독립적이다.

(2) 2차원 리스트에서 문제

a = [[1, 2], [3, 4]]
b = a[:]   # 얕은 복사

b[0][0] = 100
print(a)  # [[100, 2], [3, 4]]
print(b)  # [[100, 2], [3, 4]]

• 바깥 리스트만 새로 만들었고,
• 내부 리스트( [1, 2], [3, 4] )는 그대로 공유하기 때문에
  한쪽을 수정하면 둘 다 영향을 받는다.

---

5-3. 깊은 복사(Deep Copy)

• 깊은 복사는 내부에 중첩된 객체까지 모두 새로 복사한다.
• copy 모듈의 deepcopy 사용.

import copy

a = [[1, 2], [3, 4]]
b = copy.deepcopy(a)

b[0][0] = 100
print(a)  # [[1, 2], [3, 4]]
print(b)  # [[100, 2], [3, 4]]
print(a is b)         # False
print(a[0] is b[0])   # False  (내부 리스트도 다른 객체)

• 중첩된 자료 구조(리스트 안의 리스트, 딕셔너리 안의 리스트 등)를 쓸 때는
  얕은 복사인지, 깊은 복사인지 항상 신경 써야 버그가 줄어든다.

---

6. List Comprehension – 리스트를 한 줄로 만드는 문법

6-1. 기본형

일반적인 구조:

[표현식 for 변수 in 반복가능객체]
[표현식 for 변수 in 반복가능객체 if 조건]

예시 1) 0~9의 제곱 리스트 만들기

squares = [x * x for x in range(10)]
print(squares)  # [0, 1, 4, 9, ..., 81]

예시 2) 0~9 중 짝수의 제곱만

even_squares = [x * x for x in range(10) if x % 2 == 0]
print(even_squares)  # [0, 4, 16, 36, 64]

같은 로직을 for문으로 쓰면 더 길어진다.

result = []
for x in range(10):
    if x % 2 == 0:
        result.append(x * x)

• 기능은 똑같다.
• list comprehension은 짧게 쓰는 대신, 너무 복잡하게 쓰면 가독성이 떨어지니
  “간단한 경우에만 쓰자”는 기준 잡기.

---

7. 메서드 체이닝(Method Chaining)

메서드 체이닝은 한 객체에 대해 메서드를 연달아 호출하는 패턴이다.

예시:

text = "  hello, world  "
result = text.strip().replace("world", "python").upper()
print(result)  # "HELLO, PYTHON"

동작 순서:

1. text.strip() → "hello, world" (양쪽 공백 제거된 새 문자열)
2. .replace("world", "python") → "hello, python"
3. .upper() → "HELLO, PYTHON"

• 각각의 메서드가 새 객체를 반환하니까, 그 결과에 다시 메서드를 붙일 수 있다.
• 너무 길어지면 중간 변수를 써서 나누는 게 더 읽기 편하다.

---

8. 비시퀀스 데이터 구조 – 딕셔너리(dict)

8-1. 딕셔너리 기본 개념

• {키: 값} 쌍들을 저장하는 자료 구조.
• 키는 중복될 수 없고, 보통 문자열이나 숫자처럼 hashable(해시 가능)한 값만 쓸 수 있다.
• 순서는 파이썬 3.7+에서는 삽입 순서가 유지된다.

예시:

person = {
    "name": "Alice",
    "age": 25,
    "country": "Korea",
}

값 접근:

print(person["name"])  # "Alice"

---

8-2. 주요 딕셔너리 메서드

(1) .get(key[, default])

• 키가 있으면 값을 돌려주고, 없으면 default(기본값은 None)를 반환.

person = {"name": "Alice", "age": 25}

print(person.get("name"))          # "Alice"
print(person.get("country"))       # None
print(person.get("country", "???"))  # "???"

→ 키가 없을 수 있는 상황에서, 에러 없이 안전하게 가져올 때 유용.

---

(2) .keys(), .values(), .items()

person = {"name": "Alice", "age": 25}

print(person.keys())    # dict_keys(['name', 'age'])
print(person.values())  # dict_values(['Alice', 25])
print(person.items())   # dict_items([('name', 'Alice'), ('age', 25)])

for key in person.keys():
    print(key)

for value in person.values():
    print(value)

for key, value in person.items():
    print(key, value)

---

(3) .pop(key[, default])

• 키를 제거하면서 값을 반환.
• 키가 없으면 default가 있으면 그걸, 없으면 KeyError.

person = {"name": "Alice", "age": 25}

age = person.pop("age")
print(age)     # 25
print(person)  # {'name': 'Alice'}

country = person.pop("country", "unknown")
print(country)  # "unknown"

(4) .clear()

• 모든 키-값 쌍 삭제.

person.clear()
print(person)  # {}

(5) .setdefault(key[, default])

• 키가 이미 있으면 값을 그대로 반환.
• 없으면 default를 값으로 새로 추가한 뒤 그 값을 반환.

person = {"name": "Alice", "age": 25}

print(person.setdefault("country", "Korea"))  # "Korea"
print(person)  # {'name': 'Alice', 'age': 25, 'country': 'Korea'}

print(person.setdefault("age", 30))  # 기존 값 25 반환, 딕셔너리는 그대로

(6) .update(other)

• 다른 딕셔너리나 키-값 쌍에서 데이터를 가져와 현재 딕셔너리를 갱신.
• 같은 키가 있으면 새 값으로 덮어쓴다.

person = {"name": "Alice", "age": 25}
update_data = {"age": 30, "country": "Korea"}

person.update(update_data)
print(person)  # {'name': 'Alice', 'age': 30, 'country': 'Korea'}

---

9. 세트(set) – 중복 없는 집합

9-1. 세트의 특징

• 중복 허용 X, 순서 없음.
• {1, 2, 3} 이런 식으로 쓴다.
• 원소는 hashable 해야 한다 (리스트처럼 바뀔 수 있는 건 안 됨).

예:

s = {1, 2, 3, 3, 2}
print(s)  # {1, 2, 3}   (중복 제거됨)

---

9-2. 세트 메서드

(1) .add(x)

• 하나의 원소 추가.

s = {1, 2, 3}
s.add(4)
print(s)  # {1, 2, 3, 4}

(2) .update(iterable)

• 여러 개의 원소를 한 번에 추가.

s = {1, 2, 3}
s.update([3, 4, 5])
print(s)  # {1, 2, 3, 4, 5}

(3) .clear()

• 모든 원소 삭제 → 빈 세트.

s.clear()
print(s)  # set()

(4) .remove(x) vs .discard(x)

s = {1, 2, 3}

s.remove(2)
print(s)  # {1, 3}

s.remove(4)  # KeyError (없으면 에러)

s = {1, 2, 3}
s.discard(2)
s.discard(4)  # 에러 없음
print(s)      # {1, 3}

(5) .pop()

• 임의의 원소를 하나 꺼내서 삭제하고 반환.
• 순서가 없어서 어느 게 나올지 보장되지 않는다.

s = {1, 2, 3}
x = s.pop()
print(x, s)   # 예: 1 {2, 3}

---

9-3. 집합 연산 메서드

세트는 수학에서 배운 합집합, 교집합, 차집합, 포함 관계를 그대로 쓸 수 있다.

set1 = {0, 1, 2, 3, 4}
set2 = {1, 3, 5, 7, 9}

print(set1.difference(set2))   # {0, 2, 4}   (set1 - set2)
print(set1.intersection(set2)) # {1, 3}      (교집합)
print(set1.union(set2))        # {0,1,2,3,4,5,7,9} (합집합)

print(set1.issubset(set2))     # False (부분집합인가?)
print(set1.issuperset(set2))   # False (상위집합인가?)

---

10. 해시와 해시 테이블, hashable

10-1. 해시 테이블 개념

• 해시 테이블은 키(key)를 해시 함수로 숫자로 바꿔서 그 숫자를 이용해
  빠르게 값(value)을 찾아가는 구조.
• 파이썬의 dict와 set은 내부적으로 해시 테이블을 사용한다.

핵심 아이디어:

1. 키를 해시 함수에 넣어서 정수 값(해시 값)을 만든다.
2. 이 값을 인덱스로 사용해서 배열(버킷)에서 값을 아주 빠르게 찾는다.

---

10-2. 해시(Hash)와 해시 함수

• 해시 함수: 임의의 데이터를 입력하면, 고정 길이 정수로 바꿔주는 함수.

조건:

• 같은 입력 → 항상 같은 해시 값.
• 서로 다른 입력 → 될 수 있으면 다른 해시 값.

파이썬의 hash() 함수:

print(hash("hello"))
print(hash(123))
print(hash((1, 2, 3)))

• str, int, tuple 등은 기본적으로 해시 가능하다.

---

10-3. hashable 이라는 말의 의미

• hashable 객체: 해시 값이 변하지 않는 객체.
  • 즉, 한 번 만들면 안에 들어 있는 값이 변하지 않는다.
• 그래서 immutable 타입이 보통 hashable:
  • int, float, str, tuple, frozenset 등.

왜 필요하냐면,

• 해시 테이블의 키로 사용하려면,
• 키의 해시 값이 항상 같아야 빠르게 찾을 수 있기 때문.

그래서 딕셔너리/세트의 규칙:

• 키와 세트의 원소는 변하지 않는 값(immutable)만 허용.
• list나 dict를 키로 쓰면 에러가 난다.

d = {}
d[[1, 2, 3]] = "value"   # TypeError: unhashable type: 'list'

---

11. 파이썬 문법 규격, BNF/EBNF

11-1. 문법 규격이란?

• 프로그래밍 언어가 어떤 형태의 문장을 허용하는지 정해 놓은 약속.
• 이걸 형식 언어로 표현한 것이 BNF, EBNF 같은 규칙이다.

11-2. BNF (Backus–Naur Form)

• 문법 규칙을 표현하기 위한 기초적인 표기법.
• 예를 들면, “식은 숫자 또는 식 + 식이다” 같은 것을 기호로 표현.

11-3. EBNF (Extended BNF)

• BNF에 추가 기호들을 더 붙여서 표현력을 높인 것.
• 예: [], {}, () 등을 써서 “선택적 요소”·“반복 요소” 등을 표현.

예를 들어,

• [] 안에 있는 건 있어도 되고 없어도 되는 부분이라는 식.

이런 식 규격을 만들면,

• 언어 설계자나 컴파일러/인터프리터가
• “어떤 코드가 문법에 맞는지” 자동으로 판별할 수 있다.

---

12. 오늘 복습

• 문자열/리스트는 시퀀스이고, 문자열은 불변, 리스트는 가변이다.
• 문자열/리스트는 메서드를 통해 조회, 변경, 탐색, 정렬 등의 기능을 제공한다.
• 변수는 객체를 가리키는 참조(이름표)이고, 얕은 복사는 겉만, 깊은 복사는 속까지 새로 복사한다.
• 리스트 컴프리헨션으로 짧고 간결하게 리스트를 만들 수 있지만, 너무 복잡하면 오히려 안 좋다.
• 메서드 체이닝으로 “객체.메서드().다른메서드()…” 식으로 자연스럽게 이어서 쓸 수 있다.
• 딕셔너리는 {키: 값} 구조, 세트는 “중복 없는 집합”으로, 둘 다 내부적으로 해시 테이블을 사용한다.
• 해시/해시 테이블/해시 함수 개념을 알면, 왜 딕셔너리/세트가 빠른지, 왜 키가 hashable이어야 하는지 이해할 수 있다.
• BNF/EBNF는 언어 문법을 형식적으로 정의하기 위한 표기법이다.

---