[멋쟁이사자처럼 데이터분석 부트캠프 3주차]-자료구조

3주차는 자료구조에 대한 내용을 학습했습니다.
다양한 자료구조의 구조와 동작 원리를 이해하고,
python 코드로 직접 구현해 보며 이들이 알고리즘에 어떻게 적용되는지 익혔습니다.
⚠️본 글은 부트캠프 수업 내용을 기반으로 한 개인 학습 기록입니다.

✅ 자료구조

1. 정의

📌 자료구조란?
데이터를 저장하고 효율적으로 다루기 위한 구조와 연산의 집합이다

2. 주요 연산

• 읽기(Read)
• 쓰기(Write)
• 삽입(Insert)
• 삭제(Delete)
• 탐색(Search)

3. 알고리즘

• 정의: 입력 데이터를 가지고 원하는 출력을 만들어내는 논리적 절차
• 9세기 페르시아 수학자 '알 콰리즈미'의 이름에서 유래되었다

4. 알고리즘의 시간 복잡도 (Time Complexity)

• 입력에 대한 기본 연산 횟수
• 모든 입력의 평균을 구하는 것이 정확하나, 계산이 복잡하므로 최악의 경우를 사용
• 다른 입력에 대해서 최악의 경우보다 더 많은 시간이 걸리지 않음을 보장한다는 장점이 있다
  💥 최악의 경우 (Worst Case)란?
• 조건문이 가장 많이 참이 되는 경우
• 가장 많은 갱신이 일어나는 경우

5. 빅오 표기법 (Big-O Notation)

   1) 개념

• 최고차항만으로 시간 복잡도를 간단히 표현
• 함수의 증가율을 결정하는 가장 중요한 항에 집중
• ‘Big’은 대략적으로라는 의미

   2) 표기 규칙

• 최고차항만 남긴다
• 계수는 생략한다
• O()로 감싼다
  • T₁(n) = 2n - 1 → O(n)
  • T₂(n) = 4n + 1 → O(n)
  • T₃(n) = (2/3)n² - (2/3)n + 1 → O(n²)

   3) 표기 예시

• O(1): 상수 시간
  • 입력 크기(n)와 무관하게 항상 같은 시간에 처리
  • 배열의 인덱스 접근에 사용
  • 아무리 n이 커져도 연산 횟수는 1번
• O(log n): 로그 시간
  • 입력 크기를 계속 반으로 나눈다
  • n이 커질수록 증가하긴 하지만 느리게 증가
• O(n): 선형 시간
  • 입력의 모든 요소를 한 번씩 처리
  • 리스트 전체를 순회하면서 합을 구할 때 사용
  • n이 2배면 연산도 2배
• O(n²): 이차 시간
  • 입력마다 중첩 반복 → 총 n x n 번 수행
  • 버블 정렬, 이중 for문에 사용
  • 입력이 커질수록 급격히 느려짐

6. 순차적 자료구조

📌배열, 리스트, 큐, 스택

• 배열 (Array)
  • 데이터들이 순차적으로 저장되는 가장 기본적인 구조
  • 인덱스를 통해 특정 위치의 값에 O(1) 시간에 접근 가능
  • 읽기(Read)와 쓰기(Write)를 지원한다
• 리스트 (List)
  • 파이썬의 리스트는 동적 배열로 구현
  • append(), insert(), pop(), remove() 등의 다양한 메서드 제공
  • 인덱스를 통해 빠르게 접근 가능
• 스택 (Stack)
  • LIFO(Last In First Out): 나중에 들어온 데이터가 먼저 나감
  • Push: 데이터를 스택에 추가
  • Pop: 스택에서 데이터를 제거
• 큐 (Queue)
  • FIFO(First In First Out): 먼저 들어온 데이터가 먼저 나감 -> 스택과 반대
  • Enqueue(인큐): 큐의 뒤쪽(rear)에 데이터 삽입
  • Dequeue(디큐): 큐의 앞쪽(front)에 데이터 제거

from collections import deque

queue_ex = deque()

queue_ex.append(10)   # enqueue
queue_ex.append(20)
queue_ex.append(30)

print(queue_ex)       # deque([10, 20, 30])

queue_ex.popleft()    # dequeue → 10 제거
queue_ex.popleft()    # dequeue → 20 제거
print(queue_ex)       # deque([30])

#Python 클래스 구현

class Queue:
    def __init__ (self):
        self.items = [] #큐 저장 공간 (리스트)
        self.front_index = 0 #다음에 dequeue될 원소 위치

    def enqueue(self, value):
        self.items.append(value) #큐의 뒤에 값 추가

    def dequeue(self):
        if self.front_index == len(self.items): #큐가 비었는지 확인
            print("Queue is empty")
            return None

        else:
            x = self.items[self.front_index] #맨 앞의 값
            self.front_index += 1 #포인터 한 칸 이동
            		          #front_index만 이동하므로, 실제 리스트는 계속 쌓임 (메모리 낭비 발생 가능)
            return x

• ❓배열 vs 연결 리스트
  • 배열: 연속된 메모리 공간, 인덱스 접근 빠름(O(1)), 고정된 크기
  • 연결 리스트: 노드들이 포인터로 연결, 삽입/삭제 유리, 접근 느림(O(n))
• ❓데크(Deque: Double-Ended Queue)
  • 스택과 큐의 기능을 모두 포함
  • 양쪽 끝에서 삽입과 삭제 모두 가능
  • from collection import deque → deque를 사용하기 위해 모듈에서 불러옴
  • 데크의 연산
    
    • appendleft(): 왼쪽 끝에 삽입
    • append(): 오른쪽 끝에 삽입
    • popleft(): 왼쪽 끝에서 삭제
    • pop(): 오른쪽 끝에서 삭제

7. 비선형 자료구조

📌트리, 그래프

• 이진 트리 (Binary Tree)
  • 각 노드가 자식을 없거나, 1개 또는 최대 2개 까지만 가질 수 있는 트리
  • 1) 구성 요소
    • 노드: 트리의 각 구성 요소
    • 링크 또는 엣지: 노드들을 연결하는 선
    • 루프 노드: 맨 위에 있는 최고 조상 노드
    • 리프 노드: 자식이 없는 노드
  • 2) 표현 방법
    • 리스트로 표현
      • 간단하지만 빈 공간이 많을 수 있음
      • 레벨 0부터 시작하여 -> 각 레벨에서 왼쪽부터 오른쪽으로 -> 없는 노드는 None(널)로 표시
    • 재귀적으로 표현 (중첩 리스트)
      • 트리의 구조를 잘 나타냄
      • [노드값, 왼쪽 서브트리, 오른쪽 서브트리]
    • 노드 클래스로 직접 표현
      • 가장 직관적이고 유연
      • key, left, right, parent, value로 구성되어 있다
• 그래프 (Graph)
  • 1) 개념 및 구성요소
    • 가장 일반적이고 복잡한 자료 구조
    • G = (V, E) 로 표현
      • V: 정점(Vertex) 집합
      • E: 엣지(Edge) 집합
    • 정점 또는 노드: 동그라미로 표현되는 각 점
    • 엣지 또는 링크: 노드들을 연결하는 선
  • 2) 종류
    • 무방향 그래프: 엣지에 방향성이 없음 ➡️ 양방향 이동 가능
    • 방향 그래프: 엣지에 방향성이 있음 ➡️ 화살표로 표시
    • 가중치 그래프: 각 엣지에 가중치 값이 있음 ➡️ 비용, 거리, 시간 등 나타낼 수 있음
      • A - B 간선의 가중치가 5이면, A에서 B까지의 거리/비용이 5라는 의미
  • 3) 표현 방법
    • 인접 행렬
      • 2차원 배열로 간선 여부 표시
      • 구현은 단순하나 노드 수가 많으면 메모리를 많이 사용한다는 의미
      • 예) matrix[i][j] = 1 # i번 노드와 j번 노드 사이에 엣지 존재
              matrix[i][j] = 0 # 엣지 없음 
    • 인접 리스트
      • 각 정점이 연결된 정점들을 리스트로 저장
      • 메모리를 효율적으로 사용한다