1주차 - 2 [자료구조/알고리즘] 연결리스트와 스택

두괄식 요약

1. 연결 리스트 → 양방향 연결 리스트 → 스택을 이용한 알고리즘 문제풀이 빌드업이 오늘의 강의 내용

2. 연결 리스트의 가장 큰 장점은 데이터의 삽입과 삭제가 간단하다.

3. 단점은 일정 수준의 알고리즘 구현력과 이해를 요구한다는 점, 인덱싱을 제공하지 않아 데이터 접근에 시간이 많이 걸리는 점

4. 스택은 후입선출(LIFO, Last In First Out)이 특징으로 첫날 배운 재귀 역시 스택과 원리는 같다. (Stack overflow 에러)

 

어려웠던 점

1. 첫날에 비해 난이도가 비약적으로 상승

2. 개발을 잠시 놓고 있어 클래스 작성과 구현에 시간이 조금 소요된 점이 나 자신에게 아쉽다.

 

3. 어렵다기 보다는 우려되는 점인데 앞으로 점점 강의 내용이 어려워진다면 시간관리를 잘 할 수 있을지 걱정이다. 알고리즘의 구현과 이해가 어려워지면 그에 비례해 많은 시간을 디버깅에 투자해야 하는데 학습내용 정리나 본격적인 복습은 코어타임 전후와 주말 시간을 더 많이 투자해야 할 것 같다. 소중한 기회이니만큼 힘내자..

 

 

 

 

 

 

문제 정답 코드)

 

 

(07) 연결 리스트 순회

def traverse(self):
    res=list()
    now=self.head

    while now:
        res.append(now.data)
        now=now.next

    return res

 

 

 

 

 

 

 

8강 실습: 연결 리스트 노드 삭제하기

def popAt(self, pos):
    if pos<1 or pos>self.nodeCount:
        raise IndexError

    if pos==1:
        to_del=self.head
        self.head=to_del.next
        if self.nodeCount==1:
            self.tail=self.head
    else:
        prev=self.getAt(pos-1)
        to_del=prev.next
        prev.next=to_del.next
        if pos==self.nodeCount:
            self.tail=prev

    self.nodeCount-=1
    return to_del.data

 

 

 

 

 

 

 

9강 실습: dummy head 를 가지는 연결 리스트 노드 삭제

def popAfter(self, prev):
    if not prev.next:
        return None

    to_del=prev.next

    if not to_del.next:
        self.tail=prev
        prev.next=None
    else:
        prev.next=to_del.next

    self.nodeCount-=1
    return to_del.data


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

 

 

 

 

 

 

 

10강 실습: (1) 양방향 연결 리스트 역방향 순회

def reverse(self):
    ans=list()
    now=self.tail

    while now.prev.prev:
        now=now.prev
        ans.append(now.data)

    return ans

 

 

 

 

 

 

 

10강 실습: (2) 양방향 연결 리스트 노드 삽입

def insertBefore(self, next, newNode):
    prev=next.prev
    newNode.prev=prev
    newNode.next=next

    prev.next=newNode
    next.prev=newNode

    self.nodeCount+=1
    return True

 

 

 

 

 

 

 

10강 실습: (3) 양방향 연결 리스트 노드 삭제

def popAfter(self, prev):
    to_del=prev.next
    prev.next=to_del.next
    to_del.next.prev=prev

    self.nodeCount-=1
    return to_del.data


def popBefore(self, next):
    to_del=next.prev
    next.prev=to_del.prev
    to_del.prev.next=next

    self.nodeCount-=1
    return to_del.data


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

 

 

 

 

 

 

 

10강 실습: (4) 양방향 연결 리스트의 병합

def concat(self, L):
    if not self.nodeCount and not L.nodeCount:
        self.head.next=L.tail
        L.tail.prev=self.head

        return True

    front_last=self.tail.prev
    back_first=L.head.next

    front_last.next=back_first
    back_first.prev=front_last

    self.tail=L.tail
    self.nodeCount+=L.nodeCount

    return True

 

 

 

 

 

 

 

12강 실습: 중위표현 수식 -> 후위표현 수식

class ArrayStack:

    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]

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

def solution(S):
    opStack = ArrayStack()
    
    ans=''
    
    for s in S:
        if s.isalpha():
            ans+=s
        elif s in {'*', '/', '+', '-'}:
            if opStack.isEmpty():
                opStack.push(s)
            else:
                while not opStack.isEmpty() and prec[opStack.peek()]>=prec[s]: # opStack[-1]은 TypeError: 'ArrayStack' object is not subscriptable
                    ans+=opStack.pop()
                opStack.push(s)
        elif s=='(':
            opStack.push(s)
        else:
            while opStack.peek()!='(':
                ans+=opStack.pop()
            opStack.pop()
    
    while not opStack.isEmpty():
        ans+=opStack.pop()
    
    return ans

 

 

 

 

 

 

 

 

13강 실습: 후위표현 수식 계산

def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    ans=list()
    
    for t in tokenList:
        if type(t)==int:
            ans.append(t)
        elif t in {'*', '/', '+', '-'}:
            if opStack.isEmpty():
                opStack.push(t)
            else:
                while not opStack.isEmpty() and prec[opStack.peek()]>=prec[t]:
                    ans.append(opStack.pop())
                opStack.push(t)
        elif t=='(':
            opStack.push(t)
        else:
            while opStack.peek()!='(':
                ans.append(opStack.pop())
            opStack.pop()
    
    while not opStack.isEmpty():
        ans.append(opStack.pop())
    
    return ans


def postfixEval(tokenList):
    stack=list()
    
    for t in tokenList:
        if type(t)==int:
            stack.append(t)
        elif t=='+':
            lt=stack.pop()
            rt=stack.pop()
            stack.append(lt+rt)
        elif t=='*':
            lt=stack.pop()
            rt=stack.pop()
            stack.append(lt*rt)
        elif t=='-':
            lt=stack.pop()
            rt=stack.pop()
            stack.append(rt-lt)
        else:
            lt=stack.pop()
            rt=stack.pop()
            stack.append(rt//lt)
    
    return stack.pop()​