[한 권으로 끝내는 코딩테스트 with 파이썬] Chapter2. 자료 구조

배열

• 배열은 같은 데이터 타입들의 원소로만 이루어지지만, 파이썬은 다른 데이터 타입이어도 한 배열에 담을 수 있다. 
• 파이썬에서는 배열의 최대길이를 지정하지 않기 때문에 데이터를 추가하고 삭제하기 편리하다. 
• 배열 인덱스에 접근하는 데 소요되는 시간: O(1)
• 배열의 중간에 삽입하는 데 소요되는 시간: O(n)
  • 뒷부분에 있는 데이터를 한 칸씩 shift한 후에 데이터를 넣어야하기 때문 
  • 리스트 끝에 데이터를 삽입하는 경우: O(1)
• 장점
  • 구현이 쉽고, 참조를 위한 추가 메모리가 필요 없음
  • 연속적이므로 메모리 관리에 편리
  • 인덱스를 통한 빠른 검색
• 단점
  • 배열의 크기를 변경할 수 없고 사용하지 않는 공간으로 인한 메모리 낭비
    >> 파이썬의 리스트는 이런 단점을 보완함 

문자열

• 문자들의 집합
  • 문자를 저장하고 있는 "자료형" 
• 인덱스는 관리하는 문자의 위치에 대응된다. 
• 파이썬에서는 여러 개의 문자열 연결하기, 문자열 길이 구하기, 인덱싱 및 슬라이싱 등을 지원한다. 
• 파이썬의 객체는 가변, 불변으로 나뉘는데 문자열은 불변이다.

# 1. 초기할당
a = "abc"

# 2. 재할당
a = "bcd"

# 3. 값 변경 -> 에러
a[1] = "b"

 

같은 이름의 변수에 재할당하는 것은 가능하지만, 값을 변경하는 것은 불가능하다. 

인덱스를 이용해서는 접근만 가능하다. 

딕셔너리

• 데이터를 {키(key): 값(value)} 형식으로 저장할 수 있는 자료 구조다. 
• 배열이나 리스트처럼 순차적으로 해당 요솟값을 구하지 않고 키를 통해 값을 얻는다. 
• 주로 문자열과 숫자를 한 쌍으로 처리할 때 사용하고 문자열을 key, 숫자를 value로 지정한다.
• 가변 데이터 타입이기 때문에 사전을 선언한 후 자유롭게 새로운 키에 값을 추가하거나 기존 키의 값을 삭제하거나 변경할 수 있다. 
• 키 값은 불변 객체 타입이 와야 한다.
  • 리스트 등은 키가 될 수 없다. 
• 키 값은 중복될 수 없다. 
  • 동일한 키를 추가하면 기존의 키와 값이 나중에 추가된 키와 값으로 변경된다. 

큐

• 큐는 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기 시킬 때 사용한다. 
• 삽입(Enqueue)와 삭제(Dequeue) 기능을 제공한다.
  • 스택은 push와 pop이다.