[DE 데브코스] 04.12 TIL - 자료구조 中 정렬, 탐색, 재귀 기초, Linked List, Stack, 후위 표기식

자료구조와 알고리즘

• 주어진 문제를 어떤 자료구조와 연산 방법을 선택해서 해결할 것인가?
• "효율적으로 푼다"라는 것은 결국 개발에서는 무엇이 비용(cost)를 적게하는 방법일까에 대한 고민일듯.
• 경영으로 보면 자본적 비용(money)이 비용의 주요 의미겠지만, 개발에서는 시간(time)이 비용의 주 의미가 아닐까?
• 보조적으로 보면 메모리와 CPU 연산 사용을 얼마나 적게, 필요한 만큼만 사용하느냐.. 이런 것도 비용에 포함될듯.

 

선형 배열(Linear Array)

• 파이썬에서는 list로 구현
• 파이썬의 list에서는 원소의 자료형이 동일할 필요가 없다.
• 아래는 파이썬의 list class의 method들 정리.

li = [1,2,3,4] # list 변수 할당

# 리스트 연산
li.append(1) # 원소 덧붙이기
li.pop() # 원소 pop
li.insert(10,2) # li = [1,2,10,3,4]
del(li[-1]) # li = [1,2,10,3]
li.pop(2) # index 위치에 있는 원소를 제거. li = [1,2,3]
li.index(3) # 원소의 index를 찾는 연산

# append와 pop()은 상수 시간 O(1)이 소모되는 연산
# insert, del, pop(index), index()는 O(n)이 소모되는 연산

 

정렬

• sorted() -> 파이썬의 내장 함수, 새로운 리스트를 얻어낼 수 있다.
• sort() -> 리스트의 method. parameter의 list 자체를 정렬한다.
• parameter에 reverse=True를 추가하면 내림차순으로 정렬한다.

li = [1,5,2,3,4]
li2 = sorted(li)

# li = [1,5,2,3,4]
# li2 = [1,2,3,4,5]


# 문자열 정렬시 문자열 길이로 정렬하는 예시

li = ['ab','cde','fg']
li2 = sorted(li, key=lambda x: len(x))

# li2 = ['ab','fg','cde']

 

탐색

• 선형 탐색(Linear Search) : 앞에서 부터 쭉 원하는 원소를 찾는 것, 리스트의 길이에 비례하는 시간 소요 : O(n)
• 이진 탐색(Binary Search) : 정렬되어 있는 리스트에서 원소를 찾는 방법이다.
• 이진 탐색은 divide & conquer를 이용한 방식으로, O(log n)에 비례하는 복잡도를 가진다.
• 이진 탐색은 while문을 이용한 반복으로 찾는 방법과 재귀를 이용하는 방법이 있다.
• 아래는 while문을 이용한 방법이다. bs를 이용한 백준 문제를 풀어온 나한테는 재귀를 이용한 방법이 더 익숙하다.

def bs(L, x, start, end):
    idx = -1
    
    # 재귀를 이용하지 않은 bs
    while start <= end:
        mid = (start + end) // 2
        if L[mid] == x:
            return mid
        
        # 만약 찾는 원소가 mid보다 크면 
        elif L[mid] < x:
            start = mid + 1
        else:
            end = mid - 1
    # 찾는 원소가 없으면
    return -1

 

재귀 기초

• 자연수의 합 구하기 같은 간단한 예시에서 사용할 수 있다.
• 재귀 구조를 이용할 때는 종결 조건을 고려하는 것이 굉장히 중요하다.
• iterlative한 방식과 비교할 때 시간적 측면에서는 비슷할지 몰라도, 재귀는 함수를 호출하는 추가 overhead도 발생하기 때문에 재귀는 조심스럽게 이용해야 한다. ( 내 생각에는 메모리에 함수를 추가 할당하는 overhead가 발생할듯 )

 

링크드 리스트

• 기본 연결 리스트는 Node가 Data와 Link로 구성되어 있다.
• Link는 다음 Node를 가리키는 포인터가 담기고, Data는 말 그대로 데이터가 담긴다.
• 맨 앞 Node를 Head, 맨 뒤 Node를 Tail이라고 한다.
• 배열과 비교하면, 연결리스트는 저장 공간이 임의의 위치로 할당된다. 운영체제에서 하드 디스크를 생각해보자.
• 배열은 메모리에 연속한 위치에서 할당된다.
• 특정 원소를 지칭하는 것은 array는 O(1), 연결 리스트는 O(n)이 소요된다.
• 연결 리스트의 삽입 : 맨 앞 삽입은 O(1), 중간 삽입은 O(n), 맨 끝 삽입은 O(1) <- tail pointer를 이용
• 연결 리스트의 삭제 : 맨 앞 삽입은 O(1), 중간 삽입은 O(n), 맨 끝 삽입은 O(n) <- tail pointer를 이용
• 단순한 배열에 대비하여 연결 리스트가 힘을 발휘할 때는 삽입과 삭제가 유연하다는 점에 있다.

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
    
    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
        
# 노드와 연결 리스트 자료 구조 정의 예시

 

양방향 링크드 리스트

• 각 노드가 prev, next라는 포인터를 가지고 있다는 특징이 있다.
• 그리고 클래스 생성시 head, tail에는 dummy node를 만들고 서로를 prev, next로 지칭하게 만든다.

 

스택

• 자료를 보관할 수 있는 선형 구조다. LIFO(Last in, First out)의 구조를 가진 자료구조다.
• 파이썬에서는 list로 간단하게 스택 구조를 구현할 수 있다. push, pop, peek, isEmpty 등도 쉽게 구현 가능하다.
• doublylinkedlist 모듈을 이용해서 양방향 링크드 리스트로도 Stack 구조를 구현할 수 있다.

 

중위 표기식 -> 후위 표기식 전환

• 스택을 이용하여 구현할 수 있다.
• 구현 코드는 아래와 같다.
• 단, push, peek 등을 method로 가지고 있는 스택 클래스가 별도로 구현 되어있다고 가정한 코드다.
• 그리고 수식의 유효성을 검증할 필요가 없는, 올바르게 구성된 수식만 parameter로 전달된 코드다.

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

def solution(S):
    opStack = ArrayStack()
    answer = ''
    for s in S:
        if s == '(':
            opStack.push(s)
            
        elif s == ')':
            while opStack.peek() != '(':
                op = opStack.pop()
                answer += op
            opStack.pop() # '('도 pop해줌
            
        elif s == '+' or s == '-' or s == '*' or s == '/':
            while not opStack.isEmpty():
                if prec[s] <= prec[opStack.peek()]:
                    op = opStack.pop()
                    answer += op
                else:
                    break
            opStack.push(s)
        else:
            answer += s
    
    while not opStack.isEmpty():
        answer += opStack.pop()
        
    return answer

 

 

오늘 공부하며 어려웠던 내용

• 오늘은 딱히 없었다.
• 오늘 배운 중위 표기식 to 후위 표기식을 자료구조였나, 프로그래밍 언어론이었나. 아무튼 2~3년 전 전공 수업에서 배우고 오랜만에 마주쳤는데 많은 생각이 들었다.