리스트·배열·문자열·딕셔너리의 역할

같은 숫자라도 어떤 형태로 담느냐에 따라 알고리즘이 할 일이 달라집니다. 목표는 배열식 인덱스 접근, 문자열 위치, 이름을 키로 쓰는 조회를 구분하는 것입니다. Python의 리스트와 반복을 복습하세요.

개념과 약속

추상적인 배열은 정해진 순서의 칸을 인덱스로 바로 선택하는 자료 구조입니다. Python list는 크기가 늘어날 수 있는 배열 계열의 구현이며 원소를 가리키는 참조들을 담습니다. values[i]는 i번째 칸, len(values)는 칸 수입니다. append는 끝에 붙이고 pop()은 끝을 꺼냅니다. 중간 삽입·삭제는 뒤쪽 원소를 옮길 수 있어 O(n)입니다. 리스트를 노드가 연결된 연결 리스트와 혼동하지 마세요.

문자열은 문자들의 순서이며 변경할 수 없습니다. Python 문자열의 인덱스는 유니코드 코드 포인트 단위여서 화면의 한 글자 묶음과 항상 같지는 않습니다. 딕셔너리는 위치보다 키로 값을 찾습니다. distance['A']처럼 이름과 상태를 연결할 때 사용합니다. 뒤의 스택·큐·힙·그래프는 이러한 도구 위에 특정한 넣기·꺼내기 약속을 세운 구조입니다.

손으로 상태 추적하기

alias와 numbers가 같은 리스트를 가리키면 한쪽 변경이 다른 쪽에서도 보입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

numbers = [10, 20, 30]
copy = numbers[1:3]
whole_copy = list(numbers)
text = "가나다"
scores = {"민수": 90, "지수": 85}
print(numbers[1], copy)
print(text[0])
print(scores["민수"])
alias = numbers
alias.append(40)
print(numbers)
print(whole_copy)

실행 결과:

20 [20, 30]
가
90
[10, 20, 30, 40]
[10, 20, 30]

왜 맞고 언제 끝나는가

슬라이스는 정해진 범위의 원소를 새 리스트에 복사하므로 이후 원본에 40을 붙여도 복사는 그대로입니다. 딕셔너리의 조회 키는 문자열로 약속했습니다. 없는 키를 scores['하늘']로 바로 조회하면 KeyError가 나며 get으로 기본값을 정할 수 있습니다.

비용과 적용 범위

리스트 인덱스 조회는 O(1), k개 슬라이스 복사는 O(k), 끝 추가는 분할상환 O(1)입니다. 분할상환은 가끔 큰 재할당 비용을 여러 추가에 나누어 본다는 뜻입니다. 딕셔너리 조회는 일반적인 해시 분포에서 평균 O(1)이며 모든 입력의 엄격한 최악 O(1)을 보장하는 말은 아닙니다.

스스로 풀어 보기

1. 리스트 길이가 3일 때 유효한 음수가 아닌 인덱스를 모두 쓰세요.
2. copy = numbers로 바꾼 뒤 끝에 40을 붙이면 copy의 내용과 마지막 두 출력(numbers, whole_copy)은 각각 무엇인가요?

힌트

1. 0부터 시작합니다.
2. 새로운 목록이 만들어지는 식인지 보세요.

해설

1. 0, 1, 2입니다. 인덱스 3은 범위 밖입니다.
2. copy와 numbers는 같은 리스트를 가리켜 둘 다 [10,20,30,40]입니다. 마지막 두 출력은 numbers의 [10,20,30,40]과 별도로 복사한 whole_copy의 [10,20,30]입니다. 중첩 목록에서는 얕은 복사의 내부 공유도 별도로 확인해야 합니다.

흔한 오해

자료 구조와 Python 문법은 같은 것이 아닙니다. 큐를 리스트로 흉내낼 수 있어도 맨 앞 pop(0)의 비용이 바뀌지는 않습니다.

복습과 다음 연결

다음 순차 탐색에서 순서를 그대로 읽고, 스택·DFS와 큐·BFS에서 꺼내기 약속을 분명히 합니다.