알고리즘(1) - 자료구조 기초

안녕하세요.

 

오늘은 알고리즘을 배우기 위해 필요한 자료구조 기초에 대해서 알아보려고 합니다.

 

 

자료구조 ( Data Structure )

 

• 자료를 쉽게 관리하기 위해 다양한 구조로 묶는 것 입니다.
• 각각의 자료구조마다 장단점이 존재(효율성)해서 다양한 구조가 있습니다.

 

자료구조의 단위

 

처리 절차의 대상의 되는 것이 자료 = 데이터입니다.

 

변수

• 데이터 처리를 실시하는 가장 기본적인 구조 입니다.

데이터의 처리 과정

• 데이터 -> 입력 -> 컴퓨터(가공)-출력 -> 가공된 데이터

메모리

• 데이터는 메모리에 저장됩니다.
• 메모리 용량이 커졌습니다. 

Address

• 어느 서랍(메모리)에 어떤 데이터를 저장했는지 기억해서 주소를 지정합니다.

배열

• 같은 데이터 형태의 여러 변수를 모아 관리하는 구조 입니다.
• 배열을 사용하면 한줄로 여러 변수를 동시에 선언하는 것과 같은 결과를 얻을 수 있습니다.

 

빅오표기법

• 시간복잡도와 공간복잡도를 통하여 효율성을 구하는 방법
• 현재 공간복잡도는 하드웨어의 발전으로 인하여 크게 중요치 않게 되었습니다.

 

시간복잡도(Time complexity)

 

N은 데이터의 크기

1. O(1) : constant time 상수시간
   - 입력데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
2. O(N) : Linear time 선형 시간
   - 입력데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
3. O(N^2) quadratic time 제곱시간
   - 반복문의 중첩사용
4. O(logN) logarithmic time
   - 대표적 알고리즘 -> 이진탐색
   - 이진탐색-> 정렬을 기본전제로 한다.

 

Data structure(자료구조)의 구성

 

1. 선형 자료구조 - 자료를 순차적으로 나열

• 배열 (정적인 배열)
  - 정적 -> 크기에 대해서 미리 결정하는 배열입니다. (파이썬 예외)
• 동적 배열 (파이썬에서의 list와 같습니다.)
• 연결리스트

 

❄️ 동적 배열과 연결리스트에 대해서 좀더 정확하고 자세한 정보는 링크를 통해 확인해보세요.

동적배열(인덱스) 구조

연결리스트의 구조

위의 링크를 통해서 확인할 수 있는 내용을 요약해보겠습니다.

 

위에 그림에서 보이듯이 동적배열의 구조는 인덱스를 바탕으로하여 값을 저장하는 방법이고, 연결리스트는 하나의 노드안에 데이터와 주소라는 부분이 있어 주소부분에 다음 노드의 주소를 넣어 연결시키는 구조입니다.

 

간단하게 하나의 데이터를 추가 한다고 할때 벌어지는 상황을 보면서 특징을 살펴볼게요.

 

•  동적배열의 경우 1~1000개의 데이터가 있다고 할 때, 2번 인덱스의 값을 추가하려고 한다면 그 뒤에 모든 데이터의 인덱스가 변경되고 다시 저장되는 순서를 거칩니다. 그렇기에 대규모 데이터에서 효율성이 떨어집니다.
•  연결리스트의 경우에도 1~1000개의 데이터가 있을 때, 어느 사이에 데이터를 추가한다고 해도 앞의 노드의 주소와 추가하려는 데이터의 주소만 변경해주면 다른 데이터들에 영향을 주지 않고 데이터를 변경할 수 있기 때문에 대규모 데이터에서 효율적입니다.

 

 

2. 비선형 자료구조 - 하나의 자료뒤에 다수의 자료가 올 수 있는 형태

• 트리
• 그래프

 

3. 추상적 데이터 타입(ADT)-Abstract Data Type

• 코드로 정의 된것이 아닌 행동양식만 규정된 자료구조입니다.
• 진짜 자료구조에 적용 가능하여 사용 할 수 있습니다.

 

 

오늘은 이중에서 선형 자료구조인 연결리스트(Linked-list)와 추상적 데이터 타입에 대해서 알아보려고 합니다.

 

 

연결리스트(Linked-list)

• 연결은 프로그래밍에서 참조의 기능으로 구현되고, 연결리스트는 리스트의 길이를 별도로 지정해줄 필요없습니다.
• 위에서 보는 것처럼 연결리스트는 별도의 인덱스를 지정할 필요없이 연결되는 구조입니다.

# 클래스에 연결리스트 구현
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
          node.next.next=None
        else : 
         # 다음 노드의 위치를 현재 노드에 넣어준다.
          node = node.next
  # 연결리스트의 노드출력을 위한 기능
  def ord_desc(self):
    node = self.head
    while node:
      print(node.value)
      node = node.next

 

 

추상화(Abstract)란?

• 필요한 부분, 중요한 부분을 통합하여 하나로 만드는 것입니다. (요약)
• 수학적 추상화 참고해주세요.

 

Stack(스택)

• 배열이 수직으로 쌓여있습니다.
• 맨위에서부터 추가 혹은 삭제 가능(LiFo) last in, first out
• Push, Pop과 같은 메소드가 있습니다.
• Ex) 홈페이지 undo(뒤로가기)

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

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

    def push(self, data):
        # 신규 노드 생성
        new_node = LinkedListNode(data)
        # 최상단의 노드를 신규 노드 다음 노드로 삽입
        new_node.next = self.top
        # 신규 노드를 최상단에 삽입
        self.top = new_node
        return new_node.data

    def pop(self):
        # 스택이 비어있는지 확인
        if self.top is not None:
            # 최상단의 노드를 삭제할 노드로 삽입
            popped_node = self.top
            # 삭제할 노드 다음 노드를 최상단의 노드로 삽입
            self.top = popped_node.next
            # 삭제할 노드로부터 값 리턴
            return popped_node.data

    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
        node = self.top
        while node:
            print(node.data)
            node = node.next

 

Queue(큐)

• 버스에 줄서는 것과 같습니다.
• 맨 앞의 요소만 읽거나 삭제 가능하고 맨마지막 요소 뒤에 추가가 가능합니다.
• 가장 먼저 들어간 데이터가 가장먼저 나옴 (FiFo) first in, first out
• Front(출력부분), Back(Rear,입력부분)으로 나뉘어져 있습니다.
• Enqueue(값을 집어넣는 함수), Dequeue(값을 빼내는 함수)메소드가 있습니다.
• Ex) 푸쉬, 쇼핑몰 주문, 콜센터 백엔드 (순서대로 일을 처리)

# 연결리스트를 이용한 큐 구현
class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

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
        return new_node.data

    # 대기열에서 빼기(큐에서 값을 빼내는 함수)
    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.data
    
    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
        node = self.front
        while node:
            print(node.data)
            node = node.next

 

deque(덱,데크)

• 양방향 큐 형식
• Front, rear 부분 각각에서 추가,삭제가 가능합니다.

 

 

위의 사용된 코드들은 모두 연결리스트를 통해 큐,스택을 구현해본 방식이며 파이썬에서 기본으로 제공하는 리스트 메소드를 사용하여 더 쉽게 구현할 수 있습니다.

 

그뿐만 아니라 from collections import deque 라이브러리를 통해서 더 쉽게 메소드들을 사용할 수 있습니다.