[자료구조] 3.리스트와 집합

1. 리스트 & 집합 & 배열

리스트는 순서가 있는 항목들을 담을 수 있는 자료구조로, 각 항목은 인덱스를 가지고 있습니다. 리스트는 항목을 추가, 삭제, 수정할 수 있는 장점이 있지만, 중간에 삽입 또는 삭제를 할 경우에는 항목을 옮겨야 하는 단점이 있습니다.

[코드] - 리스트(List)는 대괄호([])를 사용하여 생성합니다. 예를 들어, 다음과 같이 문자열 리스트를 생성할 수 있습니다.

# 문자열 리스트
list1 = ['apple', 'banana', 'orange']
# 리스트 안에 다른 자료형 데이터도 함께 저장가능
#정수형과 문자열을 함께 담은 리스트
list2 = [1,2,3,'apple','banana','orange']

집합은 중복되지 않는 값을 담을 수 있는 자료구조로, 순서가 없습니다. 집합은 합집합, 교집합, 차집합 등의 연산을 지원하며, 데이터 중복을 방지할 수 있는 장점이 있습니다. 집합은 배열보다 검색 속도는 느리지만, 중복을 방지하고 집합 연산을 지원하는 등의 장점이 있습니다.

[코드] - 집합(Set)은 중괄호 ({})를 사용하여 생성합니다.

# 중복되는 값 사용 불가
# 순서 상관없음
# 집합 연산 지원
set1 = {'apple', 'banana', 'orange'}

배열은 같은 자료형의 변수들이 일렬로 늘어선 형태의 자료구조로, 각 변수는 인덱스를 이용하여 접근할 수 있습니다. 배열은 데이터의 크기가 고정되어 있습니다. 배열은 요소의 추가, 삭제가 불가능하며, 요소의 수정만 가능

[코드] - 파이썬에서 배열(Array)은 Numpy패키지를 사용하여 생성 가능

import numpy as np

arr = np.array([1,2,3,4,5])

# 배열 연산을 위해 함께 사용되는 메서드
# np.zeros() - 모든 원소가 0인 배열 생성
# np.ones() - 모든 원소가 1인 배열 생성
# reshape() - 배열의 크기나 모양을 변경

2. 추상 자료형

추상 자료형(Abstract Data Type)은 데이터의 추상적인 동작을 나타내는 수학적 모델로, 데이터의 저장 방법이나 구현 방법에 대한 제약이 없습니다. 따라서, 추상 자료형은 프로그래밍 언어나 컴퓨터 아키텍처와는 독립적으로 정의할 수 있습니다.

리스트는 추상 자료형의 하나로, 데이터를 순서대로 담는 동작을 나타내는 추상화된 모델입니다. 리스트는 데이터를 추가하거나 삭제할 수 있으며, 인덱스를 사용하여 데이터에 접근할 수 있습니다. 또한, 리스트의 크기는 동적으로 변할 수 있습니다.

추상 자료형은 이론적인 모델일 뿐 구체적인 구현 방법은 정해지지 않습니다. 따라서, 추상 자료형으로 리스트를 정의하면 다양한 프로그래밍 언어나 컴퓨터 아키텍처에서도 구현할 수 있습니다. 예를 들어, 파이썬에서는 리스트를 대괄호([])로 생성하며, C 언어에서는 배열과 유사한 구조를 가진 리스트를 구현할 수 있습니다.

배열 구조와 연결된 구조

배열(Array) 구조와 연결된 구조(Linked Structure)는 데이터를 저장하고 접근하는 방식에서 차이가 있습니다.

배열은 같은 자료형의 데이터를 일정한 크기의 메모리 블록에 연속적으로 저장하는 구조입니다. 각각의 데이터는 인덱스(첨자)를 이용하여 빠르게 접근할 수 있습니다. 배열은 데이터 검색과 정렬과 같은 작업에서 효율적이지만, 크기가 고정되어 있고 삽입/삭제 작업이 불편합니다.

반면에 연결된 구조는 데이터를 여러 개의 노드(Node)로 분할하여 저장하는 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크(Link)를 포함하고 있습니다. 연결된 구조는 데이터의 크기가 동적으로 변할 수 있고, 삽입/삭제 작업이 빠르며, 검색 작업에서는 일반적으로 배열보다 느립니다.

따라서, 배열은 데이터의 크기가 고정되어 있고 검색 작업이 자주 일어나는 경우에 적합하며, 연결된 구조는 데이터의 크기가 동적으로 변하고 삽입/삭제 작업이 빈번한 경우에 적합합니다.

[노드&링크]

노드(Node)는 연결된 구조(Linked Structure)에서 데이터를 저장하는 단위입니다. 각각의 노드는 데이터와 다음 노드를 가리키는 링크(Link)를 포함합니다. 링크는 다음 노드를 가리키는 포인터(pointer)로 구현됩니다.

class Node:
    def __init__(self, data = None):
		# data는 노드에 저장될 데이터, next는 다음 노드를 가리키는 링크
        self.data = data
        self.next = None

파이썬 리스트

파이썬 리스트(List)는 가변 길이 배열로, 내부적으로 **동적 배열(Dynamic Array)**로 구현됩니다. 동적 배열은 크기가 자동으로 조정되는 배열로, 초기에는 작은 크기의 배열을 생성하고 데이터가 추가될 때마다 배열의 크기를 동적으로 조정합니다.

파이썬 리스트는 연속된 메모리 공간에 데이터를 저장합니다. 리스트의 각 요소는 배열의 *인덱스를 사용하여 접근*할 수 있습니다. 리스트의 크기가 변경되면, 새로운 메모리 공간을 할당하고 기존 데이터를 복사하여 새로운 배열에 저장합니다. 이러한 과정을 “재할당“이라고 합니다.

파이썬 리스트는 삽입, 삭제, 탐색 등 다양한 연산을 지원합니다. 삽입과 삭제 연산은 리스트의 중간 요소에 대해서도 지원되며, 이 경우에는 새로운 배열을 할당하고 기존 요소를 복사하는 비용이 추가됩니다.

파이썬 리스트는 다른 언어에서 제공하는 배열과는 달리 서로 다른 자료형의 데이터를 함께 저장할 수 있습니다. 또한, 파이썬 리스트는 각 요소가 객체로 구성되어 있으므로, 객체의 참조값을 저장하는 식으로 요소를 추가할 수도 있습니다.

파이썬 리스트는 파이썬의 기본 자료구조 중 하나로, 다양한 기능과 편리한 문법을 제공합니다.

구현

자료구조 리스트

파이썬에서는 리스트(List)를 이미 기본적으로 제공하고 있으므로, 별도의 구현 없이 파이썬 리스트를 이용하여 자료구조 리스트를 구현할 수 있습니다.

# 리스트에 정수형 데이터 저장
lst = [3,7,1,9,2]
# 리스트의 요소에 접근
print(lst[0]) # 3출력
# 리스트의 요소 추가, 삭제, 수정
lst.append(5) # [3,7,1,9,2,5] 출력
# 리스트의 요소 삭제
del lst[2] # [3,7,9,2,5]
lst.remove(7) # [3,9,2,5]
# 리스트 요소 수정
lst[1] = 8 # [3,8,2,5]

배열로 구현한 리스트(클래스 버전)

class ArrayList:
    # 선언
    def __init__(self):
        self.items = []
    # 삽입
    def insert(self, pos, elem):
        self.items.insert(pos, elem)
    # 삭제
    def delete(self, pos):
        return self.items.pop(pos)
    # 공백확인
    def isEmpty(self):
        return self.size() == 0
    # 특정 위치 데이터 반환
    def getEntry(self, pos):
        return self.items[pos]
    # 사이즈
    def size(self):
        return len(self.items)
    # 전체 제거
    def clear(self):
        self.items = []
    # 찾기
    def find(self, item):
        return self.items.index(item)
    # 교환
    def replace(self, pos, elem):
        self.items[pos] = elem
    # 정렬
    def sort(self):
        self.items.sort()
    # 추가(리스트)
    def merge(self, lst):
        self.items.extend(lst)
    # 출력
    def display(self, msg="ArrayList: "):
        print(msg, '항목수 = ', self.size(), self.items)

집합의 구현

# 리스트를 이용한 구현
class Set:
    def __init__(self):
        self.items = []
    def size(self):
        return len(self.items)
    def display(self, msg):
        print(msg, self.items)
    def contains(self, item):
        return item in self.items
    def contains2(self, item):
        for i in range(len(self.items)):
            if self.items[i] == item:
                return True
        return False
    def insert(self, elem):
        if elem not in self.items:
            self.items.append(elem)
    def delete(self, elem):
        if elem in self.items:
            self.items.remove(elem)
    def union(self, setB):
        setC = Set()
        setC.items = list(self.items)
        for elem in setB.items:
            if elem not in self.items:
                setC.items.append(elem)
        return setC
    def intersect(self, setB):
        setC = Set()
        for elem in setB.items:
            if elem in self.items:
                setC.items.append(elem)
        return setC
    def difference(self, setB):
        setC = Set()
        for elem in self.items:
            if elem not in setB.items:
                setC.items.append(elem)
        return setC

시간복잡도

시간 복잡도를 공부하는 데에는 파이썬 코드로 작성된 여러 예시를 이용할 수 있습니다.

리스트의 정렬

lst = [3, 7, 1, 9, 2]
lst.sort()

위 코드에서 sort() 메서드를 사용하여 리스트를 정렬합니다. 이 코드의 시간 복잡도는 평균적으로 O(n log n)입니다. 이는 퀵 정렬(Quick Sort) 알고리즘이 사용되기 때문입니다. 최악의 경우 시간 복잡도는 O(n^2)이 될 수도 있습니다.

이진 탐색

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5

def binary_search(lst, target):
    left = 0
    right = len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search(lst, target)) # 4