데이터 공부/Python
[파이썬] 자료구조 개념 복습 _ 자료형, 투포인터
민몽
2025. 2. 27. 17:43
자료구조의 분류
선형 자료구조
- 데이터를 일렬로 나열한 자료구조
- 배열, 연결 리스트, 스택, 큐
비선형 자료구조
- 데이터의 순서에 상관 없이 계층 구조나 그래프 구조로 연결하는 자료구조
- 트리, 그래프 등
파이썬의 자료형
| 구분 | 유형 |
| 불변형(immutable) | int, float, str, tuple |
| 가변형(mutable) | list, dict |
- 리스트, 튜플, 문자열 : 시퀀스이자 이터러블이다.
- dict : 키에 대한 순서가 없으므로 이터러블이지만 시퀀스는 아니다.
- Sequence : 각 원소의 순서가 정해진 객체
- Iterable: 반복 가능한 객체로, 한 번에 하나씩 원소를 반환할 수 있다.
배열
- 같은 종류의 자료를 연속한 메모리에 저장한다.
- 배열의 인덱스를 통해 원하는 원소에 즉시 접근할 수 있다.
- 원소를 추가하거나 삭제할 때 전체 배열 구조를 변경해야 하므로 시간이 많이 소요된다.
- 스택, 큐, 힙, 해시 테이블, 행렬 등 다양한 자료 구조의 기본으로 사용된다.
파이썬의 리스트는 동적 배열이다.
- 배열과 달리 크기가 가변적이고, 다양한 자료형을 저장할 수 있다.
튜플
- 정적 배열 : 한 번 생성되면 크기와 원소를 변경할 수 없다.
- 변경되지 않아야 하는 데이터를 저장하는데 적합하다.
투 포인터 (Two Pointers)
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 처리하는 알고리즘
- 시작점과 끝점 2개의 점으로 접근할 데이터의 범위 표현
예시1 - 회문(앞으로 읽어도, 뒤로 읽어도 같은 단어) 찾기
- 왼쪽 포인터는 문자열의 첫 번째 인덱스, 오른쪽 포인터는 마지막 인덱스에 위치한다.
- 왼쪽 포인터가 오른쪽 포인터보다 작을 동안, 두 포인터가 가리키는 문자 비교
- 다른 경우가 생기면 False 리턴, 끝까지 통과하면 True 반환
def is_palindromes(str):
left = 0
right = len(str) - 1
while left < right:
if str[left] == str[right]:
left += 1
right -= 1
else:
return False
return True예시2 - 0과 1로 구성된 배열 정리하기
- left가 right보다 작으면 반복
- left가 1, right가 0이면 교환
- left만 1인 경우 -> right가 0이 나올때까지 왼쪽으로 이동
- right만 0인 경우 -> left가 1이 나올때까지 오른쪽 이동
def sort_zero_to_one(arr):
left = 0
right = len(arr)-1
while left < right:
if (arr[left] == 1) & (arr[right] == 0):
arr[left], arr[right] = 0, 1
left, right = left + 1 , right - 1
elif left < len(arr) and arr[left] == 1: # 포인터가 배열을 넘어가지 않도록
right -= 1
elif right >= 0 and arr[right] == 0:
left += 1
return arr예시3 - 제시된 합을 가진 부분 배열 구하기
- 이중 반복문을 사용해도 되지만 투포인터를 사용하면 시간 복잡도를 O(N)으로 줄일 수 있음.
- 왼쪽 포인터 = 0, 오른쪽 포인터 = 1로 설정
- 오른쪽 포인터를 오른쪽으로 이동시키면서 해당 위치의 배열 원소를 더한다.
- 더한 값이 타겟 값보다 작으면, 오른쪽 포인터 증가
- 더한 값이 타겟 값보다 크면, S와 같거나 작아질 때까지 왼쪽 포인터가 가리키는 값을 뺀다.
- 타겟 값과 같아지면 [왼쪽 포인터 + 1, 오른쪽 포인터 + 1] 반환
- 배열 끝까지 갔는데도 같은 값이 없으면 [-1] 반환
def find_sub_array(arr, s):
left = 0
sub = 0
for right in range(len(arr)):
sub += arr[right]
while left < right and sub > s:
sub -= arr[left]
left += 1
if sub == s:
return [left+1, right+1]
return [-1]