배열, 연결리스트, 파이썬 리스트 자료형,스택

 

 

 

• 선수지식으로 확률과 통계가 강의 진행상으로는 끝났지만 솔직히 제대로 이해를 못했다...
• 따로 보충을 계속 해주어야 겠다ㅜㅜ 어렵누
• 다음 선수지식으로 자료구조에 대해서 배우게 되었다
• 이 부분은 예전에 해본 적이 있기 때문에 수월하게 할 수 있을 것이라 믿어 의심치 않는다😎

 

 

---

 

 

1. 자료구조

• 자료구조는 다수의 자료(data)를 담기 위한 구조다
• 프로그램의 요구사항에 맞게 적절한 자료구조를 선택하게 된다면 불필요한 메모리 낭비를 막을 수 있다
• 자료구조의 종류에는 크게 두가지가 있다
  1. 선형 구조(linear data structure)
     • 배열(array)
     • 연결 리스트(linked list)
     • 스택(stack) 
     • 큐(queue)
  2. 비선형 구조(non-linear data structure)
     • 트리(tree)
     • 그래프(graph)

1-1. 선형 자료구조 (Linear Data Structure)

• 선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조다
• 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다
• 예시) 배열, 연결 리스트(linked list), 스택(stack), 큐, 덱(deque)

1-2. 비선형 자료구조 (Non-linear Data Structure)

• 비선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조다
• 데이터가 일직선상으로 연결되어 있지 않아도 된다
• 예시) 트리(tree), 그래프(graph)

1-3. 시간 복잡도, 공간 복잡도

• 프로그램의 성능을 측정할 때는 시간 복잡도와 공간 복잡도를 사용할 수 있다
• 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다
• 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다
• 공간을 많이 사용할지라도 시간을 단축하는 방법이 흔히 사용된다

1-4. Big-O 표기법

• 복잡도를 표현할 때는 Big-O 표기법을 사용한다
• 𝑂(𝑛)의 시간 복잡도는 실행하는데 최악의 경우 n개의 데이터를 모두 순회해야하는 경우를 말한다
• 이처럼 항상 최악의 경우의 수를 기준으로 한다
• Big-O 표기법으로 시간 복잡도를 표기할 때는 가장 영향력이 큰 항만을 표시한다
  $O(3n^{2} + n) = O(n^{2})$

1-4-1. 예시

• 다음 알고리즘은 𝑂(𝑛)의 시간 복잡도를 가진다

n = 10
summary = 0
for i in range(n):
	summary += i
print(summary)

• 다음 알고리즘은 $O(n^{2})$의 시간 복잡도를 가진다

n = 9
for i in range(1, n + 1):
	for j in range(1, n + 1):
		print(f"{i} X {j} = {i * j}")

• 일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다

2. 배열

• 여러 개의 변수를 담는 공간으로 이해할 수 있다
• 배열은 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다
• 특정한 인덱스에 직접적으로 접근 가능 → 수행 시간: 𝑂(1)
• 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다
• 장점: 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다
  단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다

메모리 주소	0x0000	0x0004	0x0008
인덱스	0	1	2
값	25	87	34

2-1. 파이썬에서 배열 초기화하기

• 파이썬에서 임의의 크기를 가지는 배열을 만드는 것을 리스트 컴프리헨션(List Comprehension)이라고 부른다
• 크기가 𝑁인 1차원 배열을 만드는 방법은 다음과 같다

# [0, 0, 0, 0, 0]
n = 5
arr = [0] * n
print(arr)

# [0, 1, 2, 3, 4]
n = 5
arr = [i for i in range(n)]
print(arr)

• 2차원 배열이 필요할 때는 다음과 같이 초기화한다

n = 3
m = 5
arr = [[0] * m for i in range(n)]
print(arr)

n = 3
m = 5
arr = [[i * m + j for j in range(m)] for i in range(n)]
print(arr)

• 자신이 원하는 임의의 값을 넣어 곧바로 사용할 수 있다

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
print(arr)

2-2. 파이썬에서 배열을 초기화할 때 유의할 점

• 리스트는 기본적으로 메모리 주소를 반환한다
• 따라서 단순히 $[[0] * m] * n$ 형태로 배열을 초기화하면 안 된다
  → 이렇게 초기화를 하게 되면, 𝑛개의 [0] ∗ 𝑚 리스트는 모두 같은 객체로 인식된다
  → 다시 말해, 같은 메모리를(동일한 리스트를) 가리키는 𝑛개의 원소를 담는 리스트가 된다

n = 3
m = 5
arr1 = [[0] * m] * n
arr2 = [[0] * m for i in range(n)]

arr1[1][3] = 7
arr2[1][3] = 7

print(arr1)
print(arr2)

• 위에서의 처음과 같이 잘못된 방법으로 배열을 초기화하면 같은 리스트가 중복이 되는 것을 알 수 있다

3. 연결리스트

• 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다
• 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다
• 장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다
  단점: 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다

• 연결 리스트는 각 노드가 한 줄로 연결되어 있는 자료 구조다
• 각 노드는 (데이터, 포인터) 형태를 가진다
• 포인터: 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다

• 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다

3-1. 파이썬으로 연결리스트 구현해보기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    # 가장 뒤에 노드 삽입
    def append(self, data):
        # 헤드(head)가 비어있는 경우
        if self.head == None:
            self.head = Node(data)
            return
        # 마지막 위치에 새로운 노드 추가
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    # 모든 노드를 하나씩 출력
    def show(self):
        cur = self.head
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

    # 특정 인덱스(index)의 노드 찾기
    def search(self, index):
        node = self.head
        for _ in range(index):
            node = node.next
        return node

    # 특정 인덱스(index)에 노드 삽입
    def insert(self, index, data):
        new = Node(data)
        # 첫 위치에 추가하는 경우
        if index == 0:
            new.next = self.head
            self.head = new
            return
        # 삽입할 위치의 앞 노드
        node = self.search(index - 1)
        next = node.next
        node.next = new
        new.next = next

    # 특정 인덱스(index)의 노드 삭제
    def remove(self, index):
        # 첫 위치를 삭제하는 경우
        if index == 0:
            self.head = self.head.next
            return
        # 삭제할 위치의 앞 노드
        front = self.search(index - 1)
        front.next = front.next.next


linked_list = LinkedList()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    linked_list.append(data)

print("전체 노드 출력:", end=" ")
linked_list.show()

linked_list.insert(4, 4)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

linked_list.remove(7)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

linked_list.insert(7, 2)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

4. 파이썬의 리스트(List) 자료형

• 컴퓨터 공학에서의 연결 리스트와 다른 의미를 가진다
• 일반적인 프로그래밍 언어에서의 배열로 이해할 수 있다
• 파이썬의 리스트는 배열처럼 임의의 인덱스를 이용해 직접적인 접근이 가능하다
• 파이썬의 리스트 자료형은 동적 배열이며 용량이 부족하면 자동으로 크기를 증가시킨다
• 내부적으로 포인터(pointer)를 사용하여, 연결 리스트의 장점도 가지고 있다
• 배열(array) 혹은 스택(stack)의 기능이 필요할 때 리스트 자료형을 그대로 사용할 수 있다
• 큐(queue)의 기능을 제공하지 못한다 (비효율적)

4-1. 파이썬의 리스트 자료형 메서드

연산	시간 복잡도	사용 예제	설명
Indexing	𝑂(1)	arr[i]	리스트의 특정 인덱스의 값 얻기
Storing	𝑂(1)	arr[i] = x	리스트의 특정 인덱스에 값 저장하기
Append	𝑂(1)	arr.append(5)	리스트의 가장 뒤에 데이터 넣기
Pop	𝑂(1)	arr.pop()	리스트의 가장 뒤에서 원소 꺼내기
Length	𝑂(1)	len(arr)	리스트의 길이 얻기
Clear	𝑂(1)	arr.clear()	리스트 내 모든 원소 제거하기
Slicing	𝑂(𝑏 − 𝑎)	arr[a:b]	리스트에서 인덱스 a부터 b-1까지의 원소만 꺼내 새 리스트 만들기
Extend	𝑂(𝑙𝑒𝑛(𝑜𝑡ℎ𝑒𝑟))	arr.extend(other)	기존 리스트에 다른 리스트를 이어 붙 이기
Insertion	𝑂(𝑁)	arr.insert(index, x)	특정 인덱스에 데이터 x를 삽입하기
Delete	𝑂(𝑁)	del arr[index]	특정 인덱스의 데이터 삭제하기
Construction	𝑂(𝑙𝑒𝑛(𝑜𝑡ℎ𝑒𝑟))	arr = list(other)	다른 자료구조의 원소들을 이용해 리 스트로 만들기
In	𝑂(𝑁)	x in arr:	데이터 x가 리스트에 존재하는지 확인
Not in	𝑂(𝑁)	x not in arr:	데이터 x가 리스트에 존재하지 않는지 확인
Pop(index)	𝑂(𝑁)	arr.pop(index)	특정 인덱스의 데이터를 꺼내기 / 단, 가장 뒤 원소를 꺼내는 경우 O(1)
Remove	𝑂(𝑁)	arr.remove(x)	리스트 내에 존재하는 데이터 x를 삭제
Copy	𝑂(𝑁)	arr.copy()	리스트를 복제
Min	𝑂(𝑁)	min(arr)	리스트 내에 존재하는 가장 작은 원소
Max	𝑂(𝑁)	max(arr)	리스트 내에 존재하는 가장 큰 원소
Iteration	𝑂(𝑁)	for x in arr:	리스트 내에 존재하는 모든 원소 순회
Multiply	𝑂(𝑘 ∗ 𝑁)	arr * k	리스트를 k번 반복하여 길게 만들기
Sort	𝑂(𝑁𝑙𝑜𝑔𝑁)	arr.sort()	리스트 내 존재하는 원소를 정렬

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(arr[4]) # 인덱싱(indexing)

# 저장(storing)
arr[7] = 10

# 뒤에 붙이기(append)
arr.append(10)
print(arr)

# 뒤에서 꺼내기(pop)
arr.pop()
print(arr)

# 길이(length)
print(len(arr))

# 배열 비우기(clear)
arr.clear()
print(arr)

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
new_arr = arr[2:7] # 슬라이싱(slicing)
print(new_arr)

arr1 = [0, 1, 2, 3, 4]
arr2 = [5, 6, 7, 8, 9]
arr1.extend(arr2) # 확장(extend)
print(arr1)

arr = [0, 1, 2, 3, 4]
arr.insert(3, 7) # 삽입(insertion)
print(arr)

del arr[3] # 삭제(delete)
print(arr)

data = {7, 8, 9}
arr = list(data) # 다른 자료구조로 리스트 만들기
print(arr)

arr = [0, 1, 2, 3, 4]

print(3 in arr) # 존재 여부(in)
print(7 not in arr) # 비존재 여부(not in)

arr.pop(1) # 인덱스 1에 해당하는 원소 꺼내기(pop)
print(arr)

arr.remove(3) # 리스트의 특정 원소 삭제(remove)
print(arr)

new_arr = arr.copy() # 복제(copy)
print(new_arr)

arr = [3, 5, 4, 1, 2]

print(min(arr)) # 최소(min)
print(max(arr)) # 최대(max)

for x in arr: # 원소 순회(iteration)
    print(x, end=" ")
print()

print(arr * 2) # 리스트 반복하여 곱하기(multiply)

arr.sort() # 정렬(sorting)
print(arr)

5. 스택 (Stack)

• 먼저 들어온 데이터가 나중에 나가는 자료구조
• 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다
• 기계 학습 분야뿐 아니라 다양한 프로그램을 개발할 때 빠지지 않고 사용된다

5-1. 스택 자료구조의 시간 복잡도

연산	시간 복잡도	설명
삽입(Push)	𝑂(1)	스택에 원소를 삽입하는 연산
추출(Pop)	𝑂(1)	스택에서 원소를 추출하는 연산
최상위 원소(Top)	𝑂(1)	스택의 최상위 원소(마지막에 들어온 원소) 를 확인하는 연산
Empty	𝑂(1)	스택이 비어 있는지 확인하는 연산

5-2. 파이썬으로 스택 구현해보기

• 파이썬의 기본적인 리스트(List) 자료형은 다음의 두 가지 메서드를 제공한다
• 𝑎𝑝𝑝𝑒𝑛𝑑() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡도는 𝑂(1)이다
• 𝑝𝑜𝑝() 메서드: 마지막 위치에서 원소를 추출하며, 시간 복잡도는 𝑂(1)이다
• 이 두가지 메서드를 활용하여 스택을 구현할 수 있다

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        # 마지막 위치에 원소 삽입
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        # 마지막 원소 추출
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        # 마지막 원소 반환
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)

while not stack.is_empty():
    print(stack.pop())

• 연결리스트로 스택 구현해보기
• 스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 𝑂(1)을 보장한다
• 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다
• head가 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키게 하면 된다

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    # 원소 삽입
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # 원소 추출하기
    def pop(self):
        if self.is_empty():
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    # 최상위 원소(top)
    def top(self):
        if self.is_empty():
            return None
        return self.head.data

    # 먼저 추출할 원소부터 출력
    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next

    # 스택이 비어있는지 확인
    def is_empty(self):
        return self.head is None


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)
stack.show()
print()

while not stack.is_empty():
    print(stack.pop())

 

 

 

 

---