[TIL] 자료구조/알고리즘 풀기 (2)

이원진·2023년 4월 11일
TIL데브코스알고리즘
0

데브코스

목록 보기
2/54
post-thumbnail

학습 주제

  1. 연결 리스트(Linked List)

  2. dummy head를 갖는 연결 리스트

  3. 양방향 연결 리스트

  4. 스택(Stack)

  5. 후위표현 수식

  6. 후위표현 수식 계산


1. 연결 리스트(Linked List)

  • 연결 리스트를 이루는 하나의 항목을 노드라고 부르며, 각각의 노드는 데이터와 링크로 구성됨

  • 하나의 연결 리스트 내에서 각 노드의 데이터 타입은 다를 수 있음

  • 맨 앞의 노드는 Head, 맨 끝의 노드는 Tail이라고 부름

  • 배열 리스트에 비해 삽입/삭제는 자유롭지만, 탐색 시간 긺

  • 추상자료형

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

  • 인덱스 1부터 시작

    • 0은 dummy node에 사용

  • 연산 정의

    1. 특정 원소 참조(k 번째)

        def getAt(self, pos):
		if pos <= 0 or pos > self.nodeCount:
			return None

		i = 1
		curr = self.head

		while i < pos:
			curr = curr.next
			i += 1

		return curr

    2. 리스트 순회(traversal)

        def traverse(self):
		# 빈 연결 리스트의 경우
		if self.nodeCount == 0:
			return []
  
		datum = []
		curr = self.head

		# 현재 노드의 값 삽입한 뒤 다음 노드 있으면 이동하고 없으면 종료    
		while True:
	        datum.append(curr.data)
      
	    	if curr.next is None:
      			break
      
  			curr = curr.next
  	
		return datum

    3. 길이 계산

        def getLength(self):
		return self.nodeCount

    4. 원소 삽입

        def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:
			return False

		# 맨 처음에 삽입하는 경우
		if pos == 1:
			newNode.next = self.head
			self.head = newNode

		else:
			prev = self.getAt(pos - 1)
			newNode.next = prev.next
			prev.next = newNode

		# 맨 끝에 삽입하는 경우
		if pos == self.nodeCount + 1:
			self.tail = newNode

		self.nodeCount += 1
		return True

      • 삽입하려는 노드(newNode)의 next를 먼저 설정하고, 이전 노드(prev)의 next를 설정해야 함을 유의

      • 빈 연결 리스트에 삽입하는 경우, head와 tail을 모두 newNode로 설정

      • 시간복잡도
        - 맨 앞 삽입/삭제: O(1)
        - 중간 삽입/삭제: O(N)
        - 맨 뒤 삽입: O(1)
        - 맨 뒤 삭제: O(N) -> tail 이전의 노드가 무엇인지 모르기 때문


    5. 원소 삭제

        def popAt(self, pos):
		if pos < 1 or pos > self.nodeCount:
			raise IndexError
      
		curr = self.getAt(pos)
  
	    if pos == 1:
			# tail의 next -> None
			self.head = curr.next

  			if self.nodeCount == 1:
      			self.tail = None
      
		else:            
  			prev = self.getAt(pos - 1)

			# 맨 끝 노드일 경우에도 prev의 다음 next를 현재 노드의 next로 바꿔줘야 함
			# 이 경우, prev.next가 curr에서 None으로 변경됨
  			prev.next = curr.next
  
 		 	if pos == self.nodeCount:
      			self.tail = prev
      
	    self.nodeCount -= 1
		return curr.data

    6. 두 리스트 연결

        def concat(self, L):
		self.tail.next = L.head

		# 매개변수로 받은 연결 리스트가 비었을 경우 확인
		if L.tail:
			self.tail = L.tail

		self.nodeCount += L.nodeCount

2. dummy head를 갖는 연결 리스트

  • 삽입과 삭제가 유연하다는 것이 연결리스트의 가장 큰 장점
    -> 이러한 장점을 살리기 위해 아래의 두 메서드를 새롭게 정의

    insertAfter(self, prev, newNode)
 popAfter(self, prev)
    • 이 경우, prev가 맨 앞인 경우는 고려하기 어려워지기 때문에 dummy node를 만들어 head로 설정

  • 추상자료형

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

  • 연산 정의

    1. 길이 계산

    2. 리스트 순회

    3. 특정 원소 참조

    4. 원소 삽입

      • insertAfter()

        def insertAfter(self, prev, newNode):
		if prev.next is None:
			self.tail = nextNode

		newNode.next = prev.next
		prev.next = newNode

		self.nodeCount += 1
		return True

      • insertAt()

        def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:
				return False

		# 비어있지 않은 연결 리스트의 마지막에 삽입하는 경우
		if pos != 1 and pos == self.nodeCount + 1:
			prev = self.tail

		else:
			prev = self.getAt(pos - 1)

		return self.insertAfter(prev, newNode)

    5. 원소 삭제

      • popAfter()

        def popAfter(self, prev):
	# prev가 tail일 경우, 이후에 노드가 없으므로 None 반환
	if prev.next is None:
  	  return None

	curr = prev.next
	prev.next = curr.next

	if curr.next is None:
    	self.tail = prev

	self.nodeCount -= 1
	return curr.data

      • popAt()

        def popAt(self, pos):
	if pos < 1 or pos > self.nodeCount:
 		raise IndexError
         
    prev = self.getAt(pos - 1)
 
 	return self.popAfter(prev)

    6. 두 리스트 연결


3. 양방향 연결 리스트

  • 이전 노드로도, 이후 노드로도 이동할 수 있는 연결 리스트

  • 추상자료형

    class Node:
     def __init__(self):
          self.data = item
          self.prev = None
          self.next = None
    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

  • 리스트의 맨 앞과 맨 끝에 dummy node 배치

  • 역방향 순회 가능


4. 스택(Stack)

  • 후입선출(LIFO)의 특징을 갖는 선형 자료구조

  • 언더플로우: 비어있는 스택에서 원소를 꺼내려고 시도할 때 발생하는 에러

  • 오버플로우: 가득 찬 스택에 원소를 더 넣으려고 시도할 때 발생하는 에러

  • 추상자료형

    1. size(): 현재 스택의 데이터 원소 수 계산

    2. isEmpty(): 현재 스택이 비어있는지를 판단

    3. push(x): 데이터 원소 x를 스택에 추가

    4. pop(): 스택의 최상단 데이터 원소를 추출

    5. peek(): 스택의 최상단 데이터 원소를 반환

  • 구현

    class Stack:
        def __init__(self):
                self.data = []

        def size(self):
                return len(self.data)

        def isEmpty(self):
                return self.size() == 0

        def push(self, item):
                self.data.append(item)

        def pop(self):
                return self.data.pop()

        def peek(self):
                return self.data[-1]

5. 후위표현 수식

  • 중위 표기법(Infix Notation)

    • 우리가 일반적으로 사용하는 수식 표기법

    • 연산자가 피연산자들 사이에 위치
      (A + B) * (C + D)

  • 후위 표기법(Prefix Notation)

    • 연산자가 피연산자들 뒤에 위치
      A B + C D + *

  • 중위 표기법 -> 후위 표기법

    • 수식을 한 글자씩 검사해 피연산자는 그대로 표시

    • 연산자

      • 스택이 비었을 경우 push
      • 비어있지 않을 경우, 스택에서 우선순위가 높거나 같은 연산자 모두 pop한 뒤 현재 항목 추가

    • 여는 괄호는 스택에 push

    • 닫는 괄호 만나면 여는 괄호 나올 때까지 pop

    • 마지막에 스택에 남은 연산자 모두 pop

  • 연산자의 우선순위 결정

    prec = {
    '*':3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

  • 구현

    def infixToPostfix(S):
    answer = ''
    opStack = ArrayStack()

    for ch in S:
        if ch in '+-*/':
            while not opStack.isEmpty():
                peeked = opStack.peek()

                if prec[peeked] >= prec[ch]:
                    answer += opStack.pop()

                else:
                    break

            opStack.push(ch)

        elif ch == '(':
            opStack.push(ch)

        # 닫는 괄호 나올 경우, 여는 괄호 나올 때까지 pop 
        elif ch == ')':
            while not opStack.isEmpty():
                popped = opStack.pop()

                if popped == '(':
                    break

                answer += popped

        # 알파벳인 경우
        else:
            answer += ch

    # 스택에 남은 모든 연산자 pop
    while not opStack.isEmpty():
        answer += opStack.pop()

    return answer

6. 후위표현 수식 계산

  • 피연산자는 스택에 push

  • 연산자 만나면 스택에서 두 항목을 pop해 계산 후 다시 스택에 push

  • 마지막에 스택에 남은 항목이 결과값

  • 구현

    def postfixEval(tokenList):
    evalStack = ArrayStack()

    for token in tokenList:
        if type(token) is int:
            evalStack.push(token)

        else:
            curr = evalStack.pop()
            prev = evalStack.pop()
            value = 0

            if token == '+':
                value = prev + curr

            elif token == '-':
                value = prev - curr

            elif token == '*':
                value = prev * curr

            else:
                value = prev / curr

            evalStack.push(value)

    return evalStack.pop()

메모

  • 에러 발생시키는 방법

    • raise Error

  • 연결 리스트 삭제 연산 실습

    • 길이 1인 연결 리스트에서 한 항목을 pop할 경우, head와 tail을 모두 None으로 바꿔줘야 함

    • insert는 nodeCount + 1이면 맨 뒤에 삽입하지만, pop은 존재하지 않는 원소를 추출하려고 시도하는 것

    • tail의 next -> None

  • dummy head 연결 리스트 삭제 연산 실습

    • popAt() 메서드는 pos의 범위를 검사해 prev 노드를 구하는 역할만 수행

    • popAfter() 메서드에서 인자로 받은 prev 이후의 노드를 제거하고, tail 설정 및 nodeCount 감소

  • 중위 표기 -> 후위 표기 실습

    • while queue: 와 같은 방식은 안 될 수도 있으니 while not queue.isEmpty() 와 같이 메서드 사용 고려하기

  • 타입 검사

    type(element) is int
    isinstance(element, int)
profile
이원진
이전 포스트

[TIL] 자료구조/알고리즘 풀기 (1)

다음 포스트

[TIL] 자료구조/알고리즘 풀기 (3)

0개의 댓글