[데이터 엔지니어링 데브코스 2기] TIL-2주차-파트02 자료구조와 알고리즘

1. 추상데이터타입(Abstract Data Structure)이란?

내부 정보는 숨기며 외부 인터페이스를 제공하는 데이터 타입이다. 예시로 연결 리스트가 있다. 크게 Data와 Operation으로 구성되어 있다.

2. 연결 리스트(Linked List)

연결 리스트란 (1번노드)데이터/포인터 -> (2번노드)데이터/포인터 -> (3번노드)데이터/포인터 -> .. 처럼 데이터/포인터 쌍의 노드가 연결되어 있는 구조를 뜻한다.
Node의 구성 요소는 다음과 같다.

• data
• next(다음 노드를 가리키는 링크)

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

1) 연결 리스트의 데이터 요소

• head (리스트의 맨 앞 노드를 가리킴)
• tail (리스트의 맨 마지막 노드를 가리킴)
• # of nodes (리스트에 포함된 노드의 수)

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

2) 연결 리스트의 연산 요소

1. pos번 째 node 참조하기
2. 리스트 전체 순회하기
3. 리스트의 길이 get하기
4. 특정 위치에 원소 삽입하기
5. 특정 원소 pop하기
6. 두 개의 리스트를 병합하기

clas LinkedList:
	def __init__(self):
    	self.head = None
        self.tail = None
        self.nodeCount = 0
    
    def getAt(self, pos): # pos에 위치한 노드를 get한다.
    
    def traverse(self): # 리스트의 전체를 순회한다.
    
    def getLength(self): # 리스트의 길이를 리턴한다.
    
    def insertAt(self, pos, newNode): # pos에 newNode를 삽입한다.
    
    def popAt(self, pos): # pos에 위치한 node를 pop한다.
    
    def concat(self, L): # 다른 연결 리스트 L을 병합한다.

3) 배열 vs. 연결 리스트

배열이 있음에도 불구하고 연결 리스트를 사용하는 이유는 연결 리스트는 삽입, 삭제, 리스트 병합이 유연하기 때문이다. 그리고 이를 위해서 dummy Node, popAfter(prev), insertAfter(prev, newNode) 등이 필요하다.

배열과 연결리스트의 차이점

	배열	연결 리스트
저장 공간	연속한 위치	임의의 위치
특정 원소 참조	O(1)	O(n)

4) 연결 리스트의 시간 복잡도

	삽입	삭제
맨 앞 원소	O(1)	O(1)
중간 원소	O(n)	O(n)
맨 끝 원소	O(1)	O(n)

일반적인 연결 리스트의 경우, 삽입과 삭제가 O(n)의 시간복잡도를 가지는 경우가 있다. 따라서, 이를 보완하기 위해 dummy Node, popAfter(prev), insertAfter(prev, newNode) 등이 추가로 필요하며, 이중 연결 리스트(Doubly Linked List)가 필요하다.

5) dummy Node(더미 노드)가 추가된 연결 리스트

dummy Node(더미 노드)란 쓰레기 값을 갖는 노드로, 기존과 달리 head에 더미 노드가 입력됨으로써, popAfter, insertAfter 등의 연산을 용이하게 한다.

class LinkedList:
	def __init__(self):
    	self.head = Node(None)
        self.tail = None
        self.head.next = self.tail
        self.nodeCount = 0
     
    def getAt(self, pos): # pos에 위치한 노드를 get한다.
    
    def traverse(self): # 리스트의 전체를 순회한다.
    
    def getLength(self): # 리스트의 길이를 리턴한다.
    
    def insertAt(self, pos, newNode): # pos에 newNode를 삽입한다.
    
    def popAt(self, pos): # pos에 위치한 node를 pop한다.
    
    def concat(self, L): # 다른 연결 리스트 L을 병합한다.
    
    def insertAfter(self, prev, newNode): # prev 다음 위치에 newNode를 삽입한다.
    
    def popAfter(self, prev): # prev 다음의 노드를 pop한다.
    

일부 연산이 추가됨으로써, 기존에 있던 불필요한 연산들을 줄일 수가 있다.

하지만, 아직 연결 리스트(Linked List)는 단방향으로만 움직일 수 있다는 단점이 존재한다. 따라서 이를 보완하기 위해 이중 연결 리스트(Doubly Linked List)가 나왔다.

3. 이중 연결 리스트(Doubly Linked List)

연결 리스트의 단 방향으로만 이동 가능하다는 단점을 보완하기 위해 나왔다. prev/data/next로 구성된 노드로 구성되어있다.

class Node:
	def __init__(self, data):
    	self.prev = None # 이전 노드를 가리킴.
        self.next = None # 다음 노드를 가리킴.
        self.data = data

이로 인해 양방향으로 노드의 이동이 가능하다는 장점이 있다. 그리고 기존의 연결 리스트처럼 head와 tail에 dummy node를 입력함으로써, 유연한 연산이 가능하다는 장점이 존재한다.

1) 이중 연결 리스트의 구성 요소

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

class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None
        
    def traverse(self):

    def reverse(self):

    def insertAfter(self, prev, newNode):

    def getAt(self, pos):
    
    def insertAt(self, pos, newNode):

    def insertBefore(self, next, newNode):

    def popAfter(self, prev):

    def popBefore(self, next):

    def popAt(self, pos):

    def concat(self, L):

4. 스택(Stack)

자료를 보관할 수 있는 선형 구조의 데이터 타입으로, LIFO(Last In First Out)의 특징이 있다.

Stack의 method는 다음과 같다.

• size() : 데이터 원소의 수 반환
• isEmpty() : 빈 스택인지 확인
• push(x) : 스택에 x를 추가
• pop() : 스택의 마지막 원소를 제거 후 반환
• peek() : 스택의 마지막 원소 반환

Stack에는 크게 두 가지의 에러가 존재한다.

1. Stack Underflow : 빈 stack을 pop하는 경우에 발생
2. Stack Overflow : 꽉 찬 stack에 push하는 경우에 발생

5. 후위 표기법(Postfix Notation)

중위 표기법(infix notation)	후위 표기법(infix notation)
A*B+C	AB*C+

연산자를 기준으로 후위에 표기하는 방법으로, 스택을 활용하여 쉽게 구현할 수 있다.

중위 표기법을 후위 표기법으로 변환하는 규칙은 다음과 같다.
앞에서부터 차례대로 읽으며 다음 조건에 대해서 적용한다.

1. 피연산자를 만나면 그대로 표기한다
2. '('를 만나면 Stack에 push한다.
3. ')'를 만나면 '('를 만날 때까지 Stack에서 pop한 원소들을 표기한다.
4. 연산자를 만나면 Stack의 맨 위의 연산자가 해당 연산자보다 우선순위가 낮아질 때까지 pop하여 표기한다. 이후, 해당 연산자를 Stack에 push한다.
5. Stack에 남아있는 모든 원소를 pop하여 차례대로 표기한다.

6. 후위 표기 수식 계산

후위 표기법의 수식을 연산하는 규칙은 다음과 같다.
앞에서부터 차례대로 읽으며 다음 조건에 대해서 적용한다.

1. 피연산자를 만나면 스택에 push한다.
2. 연산자가 나오면 스택에서 2개의 피연산자를 pop하여 연산한 후, 해당 결과값을 스택에 push한다.
3. 스택의 마지막 원소(최종 결과)를 pop한다.