자료구조 기초

자료구조 기초

대용량의 다양한 데이터를 효율적으로 처리 및 저장하기 위해 자료구조라는 개념이 개발되었다.

• 효율적 처리란?
  • 자동화
  • 빠른 계산
  • 여러개의 값을 한 번에 처리
  • 값의 변경
  • 특정 변수에 대한 처리
  • 특정 값을 다양한 형태로 보기를 원하는 경우
  • 조건에 따른 처리

기본 자료형

• 숫자, 문자열

• 배열

  • 각각의 변수를 하나의 변수에 여러 개의 인덱스로 묶는 것
  • 파이썬에서는 배열을 리스트와 튜플로 구현하고 활용
  • 특징 : 인덱스를 사용하여 노드에 접근가능

• 파이썬의 리스트
  • 배열과 연결리스트의 특징을 모두 갖고 있다.
  • 파이썬은 모든 것들은 원시타입이 아닌 객체로 존재하기 때문이다. 리스트에 존재하는 구성요소도 객체로 구성되어있으므로 구성요소 간 메모리 주소를 참조할 수 있도록 구성되어있다.

• 파이썬 딕셔너리
  • 해쉬

Big O 표기법

알고리즘 계산 복잡도 종류

• 시간 복잡도 : 알고리즘 실행시간
• 공간 복잡도 : 알고리즘 실행시키는데 필요한 메모리 저장 공간

Big O는 시간 복잡도를 판단할 수 있는 방법으로 입력값이 충분히 커질때, 시간 복잡도 상한선의 추세를 나타낸다.

ADT(추상자료형)와 자료구조

필요한 기능을 나열한 일종의 로직이다.

• 연결리스트

  • 배열의 구성원소인 node가 값과 다음 값의 주소를 가지는 형태
  • 특징 : 인덱스 크기를 자유롭게 확장가능, 서로 다른 자료형을 노드로 갖을 수 있다.

  # 클래스에 연결리스트 구현
  class Node:
    def __init__(self, value):
      self.value = value
      self.next = None
  
  class linked_list:
    def __init__(self, value):
      self.head = Node(value)
  
    def add_node(self, value):
      if self.head == None:
        self.head = Node(value)
  
      else:
        node = self.head
        while node.next:
          node = node.next
        node.next = Node(value) # init함수의 value
  
    # 연결리스트의 삭제구현
    def del_node(self,value):
        if self.head == None:
        # 해당 값에 대한 노드는 없다.
        # 의미없는 조건에서 함수는 아무것도 반환하지 않는다. 
          pass
  
        elif self.head.value == value:
            self.head = self.head.next
  
        # 노드의 위치를 변경시킨다.
        # 변경된 노드에 대해서 삭제를 진행한다.
        else:
          node = self.head
          while node.next:
              if node.next.value == value:
                  node.next = node.next.next
              # 노드의 위치를 변경시킨다.
              # 변경된 노드에 대해서 삭제를 진행한다.
              else : 
                  node = node.next
           # 다음 노드의 위치를 현재 노드에 넣어준다.
  
    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
      node = self.head
      while node:
        print(node.value)
        node = node.next 
  
      # 연결리스트 검색함수
    def search_node(self,value):
      node = self.head
      # 노드가 있는 경우 아래 작업을 반복한다.
      index = 0
      while node:
          if value == node.value:
              return index
          else:
              node = node.next
              index += 1
        # 노드의 값이 현재 값과 같은 경우
          #노드를 반환한다.
        # 노드의 값이 다른 경우
          # 다른 노드의 위치를 현재 노드에 넣어준다.

• Queue

  • 항목을 선입선출로 저장하는 자료구조
  • enqueue : 항목 삽입
  • dequeue : 항목 추출
  • 파이썬의 리스트로 구현가능

  class Queue:
      def __init__(self):
          self.front = None #첫 번째 노드
          self.rear = None #마지막 노드
      def enqueue(self, item):
          new_node = LinkedListNode(item)
          # 큐가 비어있는지 체크
          if self.rear is None:
              self.front = new_node
              self.rear = new_node
          else:
              # 새로운 노드를 rear 다음에 삽입
              self.rear.next = new_node
              # 새로운 노드를 rear 재할당
              self.rear = new_node
      def dequeue(self):
          # 큐가 비어있는지 체크
          if self.front is not None:
              # front값을 old front에 삽입
              old_front = self.front
              # old front 다음 값을 front값에 삽입
              self.front = old_front.next
  
          # 큐가 비어있는지 체크
          if self.front is None:
              # rear를 None으로 지정한다.
              self.rear = None
  
          return old_front

• Deque

  • 큐에서 양방향으로 데이터를 처리한다는 의미
  • 파이썬의 리스트로 구현가능
  • 파이썬의 collections.deque을 사용하여 구현가능

  # 리스트 메소드를 사용해서 큐를 만들어보기
  
  from collections import deque
  queue = deque(["Eric", "John", "Michael"])
  queue.append("Terry")           
  queue.append("Graham")          
  print('queue.popleft() ',queue.popleft())
  
  print('queue.popleft() ',queue.popleft())
  
  print('queue ', queue)        

• Stack

  • queue와 다르게 선입후출 방식
  • 파이썬의 리스트로 구현가능

  class Stack:
      def __init__(self):
          self.data = []
  
      def push(self, item):
          self.data.append(item)
  
      def pop(self):
          if len(self.data) > 0:
              return self.data.pop()
          return "The stack is empty"