[파이썬] 자료구조 개념 복습 _ 자료형, 투포인터

자료구조의 분류

선형 자료구조

• 데이터를 일렬로 나열한 자료구조
• 배열, 연결 리스트, 스택, 큐

비선형 자료구조

• 데이터의 순서에 상관 없이 계층 구조나 그래프 구조로 연결하는 자료구조
• 트리, 그래프 등

파이썬의 자료형

구분	유형
불변형(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]

 

참고 : https://wikidocs.net/224917