DevCourse TIL Day2 Week2

Day2 학습 내용 정리

지난 시간에 이어 자료구조들에 대해 알아보고자 한다.

✅ 자료구조

추상적 자료구조

• Data : 정수, 문자열, 레코드
• A set of operations : 삽입, 삭제, 순회, 정렬, 탐색, etc

🎈 Linked List

각 노드는 Data와 Link(next)로 이루어져 있고 Data는 다른 구조로 이루어질 수 있다.
알아두면 좋은 용어들을 추가로 살펴보면 다음과 같다.

• Head : 리스트의 맨 앞
• tail : 리스트의 맨 끝 (리스트 원소 추가 시 끝 tail 값 아는 것이 유리)
• @ of node : node 개수

-> 원소의 삽입/삭제가 빈번히 일어나는 응용에서 많이 이용되며 OS 내부에서도 Head로 원소를 줄줄이 엮어 표현되는 연결 리스트가 여러 곳에서 이용된다. (각 노드가 링크로 연결되어 있으므로 임의의 위치에 저장가능)
-> 단, array에 비해 메모리 용량이 커지는 단점이 발생할 수 있다.

✍️ 연결리스트에서의 연산

# 노드 생성 
class Node:
    def __init__(self, item):
        self.data = item
        self.next = None
# LinkedList class 생성 
class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None
    # 리스트를 print로 출력할 때 빈 경우 empty 출력
    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        while curr is not None:
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
            curr = curr.next
        return s
	# 연결 리스트에서 pos번째 노드 찾기
    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr
	# 연결리스트에서의 삽입
    def insertAt(self, pos, newNode):
    	# 주어진 범위가 아니면 False
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        # newNode 위치가 Head인 경우 O(1)
        if pos == 1:
            newNode.next = self.head
            self.head = newNode
        else:
            # newNode 위치가 head가 아닌 경우, tail이면 prev는 tail이 된다.
            if pos == self.nodeCount + 1:
                prev = self.tail
            # 유일한 위치인 경우 O(n)
            else: 
                prev = self.getAt(pos - 1)
            # 새로운 노드의 next는 기존 연결리스트 prev의 next
            newNode.next = prev.next
            # 기존의 next는 새로운 노드
            prev.next = newNode
        # tail인 경우 연결리스트 전체의 tail을 새로운 노드로 변화
        if pos == self.nodeCount + 1:
            self.tail = newNode
        # 노드 수 + 1
        self.nodeCount += 1
        return True
    # 연결리스트 길이 얻기
    def getLength(self):
        return self.nodeCount
    # 연결리스트를 리스트로 변환 후 원소 추가
    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result
    # 두 리스트 연결
    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount
    # 연결 리스트에서 노드 삭제
    def popAt(self, pos):
        # 주어진 범위 아니면 False
        if pos < 1 or pos > self.nodeCount:
            return False
        # 삭제할 노드가 Head면
        if pos == 1:
            remove_node = self.head
            self.head = self.head.next
            # 노드 수 - 1 진행해 비어있으면 tail 역시 None 처리 필요
            self.nodeCount -= 1
            if not self.nodeCount:
                self.tail = None
            return remove_node.data
        # Head가 아닌 경우
        else:
            prev = self.getAt(pos - 1)
            # pos 번째 노드는 결국 pos-1의 다음
            remove_node = prev.next
            prev.next = remove_node.next
            # 삭제 노드가 tail이면 이전 노드를 tail처리
            if pos == self.nodeCount:
                self.tail = prev
            self.nodeCount -= 1
            return remove_node.data

• 삽입/삭제가 유연한 LinkedList에서 앞서 본 코드에서 prev를 구하기 위해 결국 worst case로 n번탐색이 필요하다.

✍️ Dummy Node 추가로 유연한 삽입/삭제

이는 dummy node를 head에 추가하여 새로운 메서드 생성으로 해결할 수 있다.
< dummy node 생성 >

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

이후 삽입/삭제 과정이 prev를 parameter로 넣은 함수 insertAtter, popAfter덕에 연산에 더 유연해진다.

앞서, 한 방향으로만 prev, curr, next로 변수를 지정해 연결리스트에 대해 알아보았다.
지금부터 역방향 탐색을 포함해 (reverse, Before etc.) 양방향 연결리스트에 대해 알아보고자 한다.

✅ Doubled LinkedList

말 그대로 양쪽으로 링크를 연결한 노드로 기존 Node의 구조를 확장할 필요가 있다.
+) dummy node를 head와 tail에 추가 必

Doubled LinkedList를 구현한 코드는 다음과 같다.

# Node 클래스 생성
class Node:
	def __init__(self, item):
    	self.data = item
        self.prev = None
        self.tail = None
# 양방향 빈 연결리스트 생성 (dummy node Head, Tail에 저장)
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.next = None
    self.tail.prev = self.head
	# 빈 연결리스트면 empty로 표시, print로 출력 결과 확인 가능토록 함수 구축
    def __regr__(self):
    	if self.nodeCount == 0:
        	return 'LinkedList: empty'
        s = ''
        curr = self.head
        while curr.next.next:
        	curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
            	s += ' -> '
        return s
    # 연결리스트 길이 확인
    def getLength(self):
    	return self.nodeCount
    # 리스트 순회 (빈 리스트는 진행 X)
    def traverse(self):
    	result = []
        curr = self.head
        while curr.next.next:
        	curr = curr.next
            result.append(curr.data)
        return result
    # 리스트 역순회 (빈 리스트 진행 X)
    def reverse(self):
    	result = []
        curr = self.tail
        while curr.prev.prev:
        	curr = curr.prev
            result.append(curr.data)
        return result
    # pos번째 노드 얻기 
    def getAt(self, pos):
    	if pos < 0 or pos > self.nodeCount:
        	return None
        # 효율성 극대화 위해 이분 탐색 진행
        # 절반보다 pos가 크면 tail에 가까운 쪽에서 탐색 진행
        if pos > self.nodeCount//2:
        	i = 0 
            curr = self.tail
            while i < self.nodeCount - (pos - 1):
            	curr = curr.prev
                i += 1
        # 절반보다 pos가 작거나 같으면 head에 가까운 쪽에서 탐색 진행
        else:
        	i = 0
            curr = self.head
            while i < pos:
            	curr = curr.next
                i += 1
        return curr
    # 특정 노드 이후에 노드에 원소 삽입 case
    def insertAfter(self, prev, newNode):
       	next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
    # 특정 노드 이전 노드에 원소 삽입
    def insertBefore(self, next, newNode):
       	prev = next.prev
        newNode.prev = prev
        newNode.next = next
        prev.next = next
        next.prev = prev
        self.nodeCount += 1
        return True
    # 특정 pos 위치에 노드 삽입
    def insertAt(self, pos):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        prev = self.getAt(pos - 1)
        return self.insertAfter(prev)
    # 특정 노드(prev) 이후 노드 리턴 값 뽑고 삭제
    def popAfter(self, prev):
        # 삭제하려는 노드가 tail인 경우 None처리
        if prev.next == self.tail:
            return None
        remove_node = prev.next
        next = remove_node.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return remove_node.data
    # 특정 노드 (next) 이전 노드 리턴 값 뽑고 삭제
    def popBefore(self, next):
       	# 삭제하려는 노드가 head인 경우 None 처리
        if next.prev == self.head:
			return None
        remove_node = next.prev
        prev = remove_node.prev
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return remove_node.data
    # 특정 (pos)번째 위치한 노드 삭제
    def popAt(self, pos):
      	if pos < 1 or pos > self.nodeCount:
            return False
        prev = self.getAt(pos - 1)
        return self.popAfter(prev)
    # 두 연결리스트 병합
    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        if L.tail:
           	self.tail = L.tail
        self.nodeCount += L.nodeCount 

🎇 LinkedList 정리

지금까지 연결리스트 연산 과정에 대해 python 코드로 직접 실습해보며 구현하는 시간을 가졌다. 기존에 공부하던 알고리즘과 달리 class를 활용한 OOP 실습이어서 구현하는데 시간이 많이 소요되었고, prev (이전 노드)를 구하는 과정에서의 n번 탐색하는 과정을 효과적으로 구현하기 위해 After, Before를 사용하는 과정, dummy node를 head, tail에 추가하여 양방향 연결리스트를 구현하는 과정에 대해 학습해보았다.

확실히 이론적인 내용만 알고 있다가 코드로 직접 구현해보며 정리하는 시간을 가지니 이해하는데 수월한 편이었다🙌

✅ stack

• 자료를 보관할 수 있는 선형 구조로 push, pop 연산이 존재한다.
• queue와 다르게 LIFO 특징을 가짐

< 연습문제를 통해 스택 구현 >

# 라이브러리, 기존 생성했던 class import 
import sys
import os
sys.path.append('C:/Users/wnrrh/PycharmProjects/Algorithm_study/DevCourse')
import doublylinkedlist
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
# 스택 구현
# 빈 리스트로 스택 생성
class ArrayStack:
    def __init__(self):
        self.data = []
	# 길이 출력하는 함수
    def size(self):
        return len(self.data)
	# 비어있나 여부 확인
    def isEmpty(self):
        return self.size() == 0
	# 스택에 item 추가
    def push(self, item):
        self.data.append(item)
	# 스택에서 젤 끝 원소 제거
    def pop(self):
        return self.data.pop()
	# 스택 젤 마지막 원소 찾기
    def peek(self):
        return self.data[-1]

# 주어진 문자열 exprStr split하여 끊어서 리스트로 표현
def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
			# 괄호, 연산 추가
            tokens.append(c)
    # 마지막 숫자 추가
    if valProcessing:
        tokens.append(val)
    return tokens
# 후위표현식으로 연산자, 피연산자 순서대로 늘어놓게 만들기
def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }
	# 연산자 저장하는 스택 생성
    opStack = ArrayStack()
    # 최종 결과 리스트로 생성
    postfixList = []
    for i in tokenList:
    	# 숫자에 한해 리스트에 추가
        if type(i) is int:
            postfixList.append(i)
        # 괄호 시작하면 연산자 스택에 push
        elif i == '(':
            opStack.push(i)
       	# 괄호 닫히면, ( 전까지의 연산들 최종 결과 리스트에 추가
        elif i == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            # ( 제거
            opStack.pop()
        # 나머지 *, /, +, - 연산에 대해서
        else:
        	# 연산자 스택이 비어있지 않고, 우선 연산 되어야 하는 것들에 한해 리스트에 추가
            while not opStack.isEmpty() and prec[opStack.peek()] >= prec[i]:
                postfixList.append(opStack.pop())
            # 조건 벗어나는 경우 연산자 스택에 push
            opStack.push(i)
    # 괄호 다 돌고 연산 남아있는 경우 최종 결과에 추가해 후위표기 리스트 생성
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return postfixList

# 후위표기로 변환된 리스트 연산하기
def postfixEval(tokenList):
	# 빈 스택 생성
    valStack = ArrayStack()
    for i in tokenList:
		# 숫자면 valStack에 push
        if type(i) is int:
            valStack.push(i)
		# 숫자가 아니고 연산인 경우
        else:
			# pop 2번 진행해 숫자 뽑고 각 연산 진행한 이후 연산한 값 다시 push
            b = valStack.pop()
            a = valStack.pop()
            if i == '*':
                valStack.push(a*b)
            elif i == '/':
                valStack.push(a/b)
            elif i == '+':
                valStack.push(a+b)
            elif i == '-':
                valStack.push(a-b)
	# size 계산해 1이상이면 pop 아니면 None 처리
    if valStack.size() >= 1:
        return valStack.pop()
    else:
        return None

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val

🎇 stack 정리

스택 역시 기존에 학습한 방식과 달리 class와 더불어 push, pop, peek 등 직접 함수를 생성하는 경험을 처음 해보면서 구현되는 방식에 대해 더 깊게 이해할 수 있는 시간을 가졌다.

앞서 LinkedList와 마찬가지로 기존 스타일대로 학습한 방식이 아니기에 구현하는데 상당히 오래걸렸던.... 😭

Fighting❗❗❗