환영합니다!

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software Engineer

알고리즘과 자료 구조의 중요성

  • 자료 구조와 알고리즘은 다음을 가능하게 합니다
    • 일상적 문제 해결
    • 효율적 코드 사용
  • 이 과정은 어떤 프로그래밍 언어로도 가르칠 수 있습니다
Python으로 배우는 자료구조와 알고리즘

알고리즘과 자료 구조

  • 알고리즘: 문제를 해결하는 지시문의 집합

    1. _설계_

      알고리즘 설계를 도식화한 그림.

    2. _코드_

      알고리즘 코드를 도식화한 그림.

  • 자료 구조: 알고리즘 실행 시 데이터를 보관·조작
    • 고급 자료 구조: 연결 리스트, 스택, 큐...
Python으로 배우는 자료구조와 알고리즘

연결 리스트

빵을 만드는 단계를 담은 연결 리스트의 시각적 예.

  • 링크로 연결된 데이터의 시퀀스
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

연결 리스트의 노드를 나타내는 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

연결 리스트의 노드를 나타내며 첫 부분에 "DATA"가 적힌 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

연결 리스트의 노드를 나타내며 첫 부분에 "DATA", 두 번째 부분에 포인터가 있는 "NEXT"가 적힌 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

연결로 이어진 연결 리스트의 두 노드를 나타내는 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

여러 노드가 연결로 이어진 연결 리스트를 나타내는 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

마지막 노드가 null을 가리키는 연결 리스트를 나타내는 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

첫 번째 노드에 "HEAD"가 적힌 연결 리스트의 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 구조

마지막 노드에 "TAIL"이 적힌 연결 리스트의 그림.

  • 데이터는 연속된 메모리 블록에 저장될 필요가 없습니다
  • 데이터는 임의의 사용 가능한 주소에 위치할 수 있습니다
Python으로 배우는 자료구조와 알고리즘

단일 연결 리스트

단일 연결 리스트 표현.

  • 링크 하나: 단일 연결 리스트
Python으로 배우는 자료구조와 알고리즘

이중 연결 리스트

이중 연결 리스트 표현.

  • 양방향 두 링크: 이중 연결 리스트
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 실제 활용

  • 다른 자료 구조 구현:
    • 스택
    • 큐
    • 그래프
  • 앞뒤로 탐색하며 정보 접근
    • 웹 브라우저
    • 음악 재생목록
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - Node 클래스

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - LinkedList 클래스

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 메서드

  • insert_at_beginning()
  • remove_at_beginning()
  • insert_at_end()
  • remove_at_end()
  • insert_at()
  • remove_at()
  • search()
  • ...
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_beginning

단일 연결 리스트 표현.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_beginning

단일 연결 리스트와 새 노드의 그림,

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_beginning

새 노드가 연결된 단일 연결 리스트의 그림.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_beginning

새 노드가 연결되고 이 노드에 "HEAD"가 표시된 단일 연결 리스트 그림.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_beginning

비어 있는 연결 리스트에 새 노드를 추가한 그림.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

첫 번째 노드를 가리키는 "current_node"가 표시된 단일 연결 리스트 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

두 번째 노드를 가리키는 "current_node"가 표시된 단일 연결 리스트 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

세 번째 노드를 가리키는 "current_node"가 표시된 단일 연결 리스트 그림.

Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 예시

비어 있는 연결 리스트에 새 노드를 추가한 그림.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 예시

연결 리스트 끝에 새 노드가 추가된 그림.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 예시

연결 리스트 시작에 새 노드가 추가된 그림.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")
Python으로 배우는 자료구조와 알고리즘

연결 리스트 - 예시

연결 리스트를 나타내는 그림.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False
Python으로 배우는 자료구조와 알고리즘

Ayo berlatih!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...