Home [데브코스] 1주차 - 알고리즘 문제 풀기 (2)
Post
Cancel

[데브코스] 1주차 - 알고리즘 문제 풀기 (2)

Posted Feb 17, 2022 Updated Mar 5, 2022 24 min read

스택 (stack)

스택: 자료를 보관할 수 있는 선형 구조

  • x.isempty() : 스택이 비어있는지 판단한다.
  • x.peek() : 스택에 가장 나중에 저장된 데이터 원소를 참조한다.
  • x.size()
  • x.push()
  • x.pop()

단, 넣을 때는 한 쪽 끝에서 밀어 넣어야 하는 push 연산, 꺼낼 때는 같은 쪽에서 뽑아 꺼내야 하는 pop 연산에 대한 제약이 있다.

이를 후입선출(LIFO - Last-In-First-Out) 특징을 가지는 선형 자료구조라 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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]



수식의 후위 표기법

중위 표기법: 연산자가 피연산자들의 사이에 위치

1
2

(A + B) * (C + D)
   1    3    2

후위 표기법: 연산자가 피연산자들의 뒤에 위치

1
2

A B + C D + *
    1     2 3

각 연산자의 우선순위를 비교하는데, 스택에 있는 연산자가 읽어온 연산자보다 우선순위가 높거나 같으면 pop, 아니면 push한다.



스택의 응용 - 후위 표기 수식 계산

후위 표기법으로 된 식을 계산하는 방법은 다음과 같다.

중위 표기법 → 후위 표기법 → 후위 계산

이를 변환할 때는 이제 문자열이 아닌 리스트에 추가하여 리스트를 리턴할 것이다. 피연산자를 받으면 스택에 추가하고, 연산자를 만날 경우 맨 위의 2개를 빼내서 연산자에 맞게 계산한 후 다시 스택에 집어넣는다. 그렇게 마지막까지 간 후 스택에 담긴 값은 1개일 것이고, 이 값이 최종값이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

이는 중위 표현식을 받아 리스트로 변환하는 함수이다. 가장 중요한 것은 10진법을 표기해야 하기 때문에, 10진법을 구현하는 것을 주의하며 구현한다.


이제 리스트로 넣은 중위 표현식을 후위 표현식으로 변환해야 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

  opStack = ArrayStack()
  postfixList = []

  for s in tokenList:
      if type(s) is int:
          postfixList.append(s)
      else:
          if opStack.isEmpty():
              opStack.push(s)
          else:
              if s == ')':
                  while prec[opStack.peek()] > prec['(']:
                      postfixList.append(opStack.pop())
                  opStack.pop()
              else:
                  if prec[opStack.peek()] >= prec[s] and s != '(':
                      postfixList.append(opStack.pop())
                  opStack.push(s)

  while not opStack.isEmpty():
      postfixList.append(opStack.pop())

  return postfixList


이제 변환된 후위 표현식을 계산한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def postfixEval(tokenList):
  valStack = ArrayStack()
  lists = []
  for t in tokenList:
      if type(t) is int:
          valStack.push(t)
      else:
          a = valStack.pop()
          b = valStack.pop()
          if t == '*':
            valStack.push(b*a)
      elif t == '/':
            valStack.push(b/a)
      elif t == '+':
            valStack.push(b+a)
      elif t == '-':
            valStack.push(b-a)

  return valStack.pop()

def solution(expr):
  tokens = splitTokens(expr)
  print("tokens: {}".format(tokens))
  postfix = infixToPostfix(tokens)
  print("postfix: {}".format(postfix))
  val = postfixEval(postfix)
  return val

최종적으로 후위 표현식을 계산하는 함수로, 2개를 pop한 후 계산하여 다시 스택에 넣는 식이다. solution에서 모든 함수를 실행시키면 결과를 얻을 수 있다.



큐 (queue)

큐: 자료를 보관할 수 있는 선형 구조

단 넣을 때는 한 쪽 끝에서 밀어 넣어야 하는 enqueue연산, 꺼낼 때는 반대 쪽에서 뽑아 꺼내야 하는 dequeue연산의 제약이 있다. 이를 선입선출(FIFO - First-In Fisrt-Out) 특징을 가진다고 한다.

알고리즘 테스트 중 대기열 문제가 큐에 해당된다.

큐 연산의 종류

  • size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
  • isEmpty(): 현재 큐가 비어 있는지를 판단
  • enqueue(): 데이터 원소 x를 큐에 추가
  • dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거)
  • peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거 x)

이때, dequeue()만 O(n)이고, 나머지는 O(1)의 복잡도를 가진다. 이는 맨 앞의 원소를 꺼내게 되면 나머지 원소들이 앞으로 당겨져야 하기 때문에, 순차적인 방식이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def __init__(self):
    self.data = DoublyLinkedList()

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

def isEmpty(self):
    return self.data.getLength() == 0

def enqueue(self, item):
    node = Node(item)
    self.data.insertAt(self.data.getLength()+1,node)

def dequeue(self):
    return self.data.popAt(1)


def peek(self):
    return self.data.getAt(1).data



환형 큐(Circular queue)

큐의 활용:

  • 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(asynchronously)으로 일어나는 경우
  • 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
  • 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
  • 자료를 생성/이용 둘 다 여러 곳에서 일어나는 경우
  • 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐(circular queue) : 정해진 개수의 저장 공간을 빙 돌려가며 사용

정해진 개수의 공간이므로 큐가 가득 차면 더이상 원소를 넣을 수 없다.

큐보다 추가된 점

  • isfull()이라는 큐의 데이터가 꽉 차있는지 확인하는 함수를 더 추가한다.
  • 마지막 원소 저장된 공간을 rear, 처음을 front라 한다.
  • 전체 공간을 정의하는 self.maxcount = n을 정의한다.
  • data를 None으로 초기화하기 위한 self.data를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class CircularQueue:

def __init__(self, n):
    self.maxCount = n
    self.data = [None] * n
    self.count = 0
    self.front = -1 # 데이터가 존재하는 첫 위치보다 1개 전
    self.rear = -1 # 데이터가 들어있는 마지막 위치

def size(self):
    return self.count

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

def isFull(self):
    return self.count == self.maxCount

def enqueue(self, x):
    if self.isFull():
        raise IndexError('Queue full')
    
    self.rear = (self.rear+1) % self.maxCount

    self.data[self.rear] = x
    self.count += 1

def dequeue(self):
    if self.isEmpty():
        raise IndexError('Queue empty')
    self.front = (self.front+1) % self.maxCount

    x = self.data[self.front]

    self.count -= 1
    return x

def peek(self):
    if self.isEmpty():
        raise IndexError('Queue empty')
    return self.data[(self.front+1)%self.maxCount]



우선순위 큐(Priority Queues)

우선순위 큐: 큐가 FIFO 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

우선순위 큐 활용:

  • 운영체제의 CPU 스케줄러

우선순위 큐 구현:

  • 서로 다른 방식이 가능함
    • Enqueue할 때 우선순위 순서를 유지하도록
    • Dequeue할 때 우선순위 높은 것을 선택

이때는 1번이 조금 더 유리하다. 2번은 O(n)의 복잡도를 가지지만, 1번은 이미 줄지어 집어넣었기 때문에 맨 뒤나 맨 앞만 보면 되기 때문이다.

큐를 만드는 두 가지 재료 중 골라서 사용 가능하다.

  • 선형 배열
  • 연결 리스트

시간 적으로 볼 때는 연결 리스트가 유리하다. 하지만 메모리 적으로는 연결 리스트가 많이 들기 때문에 적합한 방법을 사용하는 것이 좋다.



17강: 트리(trees)

트리: 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

이 때, 뿌리를 root node, 이파리를 leaf node라 한다. 이는 각각 노드에 대해 부모(parent), 자식(child)로도 표현할 수 있다.

같은 부모 아래 자식들을 sibling이라 한다. 그리고, 부모의 부모를 조상(ancestor), 자식의 자식을 후손(deancestor)이라 한다. child는 많을 수 있지만, 부모는 오직 1개이다.

  • 노드의 수준(level)

뿌리를 level0이라 하고, 내려갈수록 level이 1씩 증가한다. 이 때 뿌리를 0과 1 중 하나로 둘 수 이는데 0이 더 편하다.

  • 트리의 높이(height)

높이 = 최대 수준(level) + 1

깊이(depth)라고도 한다.

  • 부분트리(= 서브트리(subtree))

각각의 부분에 대해 서브트리라고도 부를 수 있다.

  • 노드의 차수(degree)

차수 = 자식(서브트리)의 수

degree는 각 노드의 자식의 수와도 같다. 맨 마지막의 node 즉 degree=0인 노드를 leaf nodes라고 부른다.

  • 이진 트리(binary tree)

모든 노드의 차수가 2이하인 트리

  • 포화 이진트리 (full binary tree)

모든 레벨에서 노드들이 채워져 있는 이진 트리 = 모든 차수가 2이다. 높이가 k이고, 노드의 개수는 2^k - 1 이다.

  • 완전 이진트리 (complete binary tree)

높이가 k인 완전 이진트리의 경우

  1. 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
  2. 레벨 k-1 까지는 2개씩이 아니더라도 왼쪽부터 노드가 순차적으로 채워져 있는 트리



이진 트리(binary tree)

이진 트리의 연산 종류

  • size(): 현재 트리에 포함되어 있는 노드의 수를 구함
  • depth(): 현재 트리의 깊이 (또는 높이) 를 구함
  • traverse()

이진 트리 노드의 기본 구조는 다음과 같다.

1
2
3
4
5
6

# 이진 트리 노드의 기본 구조
class Node:
	def __init__ (self,item):
		self.data = item
		self.left = None
		self.right = None


size 

1
2
3
4

# 이진 트리 초기화
class BinaryTree:
	def __init__ (self,r):
		self.root = r

1
2
3
4
5
6
7

# 재귀적 방법 가능
# 오른쪽 tree size + 왼쪽 tree size + 1(자신)
class Node:
	def size(self):
		l = self.left.size() if self.left else 0
		r = self.right.size() if self.right else 0
		return l + r + 1

1
2
3
4
5
6

class BinaryTree:
	def size(self):
		if self.root: 
      return self.root.size()
		else: 
      return 0


depth 

1
2
3
4

def depth(self):
    if self.root:
        return self.root.depth()
    else: return 0


Traversal(순회) 종류

  • 깊이 우선 순회
    • 중위 순회(in-order traversal): 왼 → 자신 → 오
    • 전위 순회(pre-order traversal): 자신 → 왼 → 오
    • 후위 순회(post-order traversal): 왼 → 오 → 자신
  • 넓이 우선 순회



이진 트리 넓이 우선 순회(breadth first traversal)

수준(level)이 낮은 노드를 우선으로 방문한다. 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고, 왼쪽 자식 노드를 먼저 방문한다.

설계(큐 사용)

  1. 빈 리스트 traversal, 빈 큐 q 선언
  2. 빈 트리가 아니면, root node를 q에 추가 (enqueue)

  3. q가 비어있지 않는 동안

    3-1. q에서 node를 추출

    3-2. node 방문

    3-3. node의 왼, 오 자식 q에 추가

  4. q가 빈 큐가 되면 종료



이진 탐색 트리(binary search trees)

모든 노드에 대해

  • 왼쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 작음
  • 오른쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 큼

의 성질을 만족하는 이진 트리가 이진 탐색 트리이다.

이진 탐색과 비슷하지만, 트리의 장점은 데이터 원소의 추가, 삭제가 용이하다. 그러나, 단점은 공간 소요가 크다.


추상적 자료구조

  • 각 노드는 (key, value)의 쌍으로 되어 있다.

연산의 종류

  • insert(key, data): 트리에 주어진 데이터 원소를 추가
  • remove(key): 특정 원소를 트리로부터 삭제
  • lookup(key): 특정 원소를 검색
  • inorder(): 키의 순서대로 데이터 원소를 나열
  • min(),max(): 최소 키, 최대 키 원소를 탐색
1
2
3
4
5
6
7
8
9
10
11

# 기본 노드 구성
class Node:
	def __init__(self,key,data):
		self.key = key
		self.data = data
		self.left = None
		self.right = None

class BinSearchTree:
	def __init__(self):
		self.root = None

inorder 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# inorder traversal
class Node:
  def inorder(self):
    traversal = []
    if self.left:
      traversal += self.left.inorder()
    traversal.append(self.data)
    if self.right:
      traversal += self.right.inorder()
    return traversal

class BinaryTree:
  def inorder(self):
    if self.root:
      return self.root.inorder()
    else:
      return []

preorder 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# preorder traversal
class Node:
  def preorder(self):
    traversal = []
    traversal.append(self.data)
    if self.left:
      traversal += self.left.preorder()
    if self.right:
      traversal += self.right.preorder()
    return traversal

class BinaryTree:
  def preorder(self):
    if self.root:
      return self.root.preorder()
    else:
      return []

postorder 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# postorder traversal
class Node:
  def postorder(self):
    traversal = []
    if self.left:
      traversal += self.left.postorder()
    if self.right:
      traversal += self.right.postorder()
    traversal.append(self.data)
    return traversal

class BinaryTree:
  def postorder(self):
    if self.root:
      return self.root.postorder()
    else:
      return []

min 

1
2
3
4
5
6
7
8

# minimum value
class Node:
	def min(Self):
		if self.left:
			return self.left.min()
		else:
			return self # 계속 내려가다가 더 내려갈 곳이 없으면 자신이 최솟값이므로

lookup

  • 입력은 찾으려는 대상의 키
  • 리턴은 찾은 노드와 부모 노드(없으면 둘다 None)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class BinSearchTree:
	def lookup(self,key):
		if self.root:
			return self.root.lookup(key)
		else:
			return None,None

class Node:
	def lookup(self,key,parent=None):
		if key < self.key:
			if self.left:
				return self.left.lookup(key,self) # self.left 의부모는 self이므로
			else:
				return None,None
		elif key > self.key:
				...
		else: return self, parent


remove

원소 삭제의 메커니즘

  1. 키를 이용해서 노드를 찾는다.

    1-1. 해당 키가 없으면, 삭제할 것도 없음

    1-2. 찾은 노드의 부모 노드도 알고 있어야 함

  2. 찾은 노드를 제거하고도 이진 탐색 트리의 성질을 만족하도록 트리의 구조를 정리

  • 입력: 키
  • 출력: 삭제한 경우 True, 해당 키가 없는 경우 False
1
2
3
4
5
6
7

class BinSearchTree:
	def remove(self,key):
		node,parent = self.lookup(key)
		if node:
			...
			return True
		else: return False

트리 구조를 계속 유지해야 하기 때문에

  • 삭제하는 노드가
    • 말단 노드인 경우
    • 하나의 자식을 가진 경우
    • 둘의 자식을 가진 경우

를 다 고려해야 한다.



힙(heap)

힙: 이진 트리의 한 종류

힙의 특징

  1. 루트 노드가 언제나 최댓값 또는 최솟값을 가짐
    • 최대 힙, 최소 힙
  2. 완전 이진 트리여야 함


이진 탐색 트리와의 비교

  1. 둘 다 원소들은 안전히 크기 순으로 정렬되어 있음
  2. 특정 키 값을 가지고 빠르게 원소를 찾을 수 있는가?
    • 이진 탐색트리 - O
    • 힙 - X
  3. 부가 제약 조건
    • 힙의 경우 완전 이진 트리여야 함


최대 힙의 연산의 종류

  • __init__(): 비어있는 최대 힙을 생성
  • insert(item): 새로운 원소를 삽입
  • remove(): 최대 원소(root node)를 반환 및 제거

노드 번호m을 기준으로

  • 왼쪽 자식의 번호: 2*m
  • 오른쪽 자식의 번호: 2*m + 1
  • 부모 노드의 번호: m // 2

완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 이루어진다.

__init__ 

1
2
3

class Maxheap:
	def __init__(Self):
		self.data = [None]

0번 인덱스는 버리기 위해 none


삽입(insert)

  1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
  2. 부모 노드와 키 값을 비교하여 위로 이동시킴

복잡도: 원소의 개수가 n인 최대 힙에 새로운 원소 삽입 후 부모 노드와 계속 비교 → log2(n)

두 변수 값을 바꾸는 방법

1

a,b = b,a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def bft(self):
        traversal = []
        q = ArrayQueue()
        
        if self.root: 
            q.enqueue(self.root)
            
        while not q.isEmpty():
            k = q.dequeue()
            traversal.append(k.data)

            if k.left: q.enqueue(k.left)
            if k.right: q.enqueue(k.right)
        
        return traversal


제거(remove)

최대 힙에서 원소를 삭제

  1. 루트 노드의 제거 → 이것이 원소들 중 최댓값

  2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치 → 완전 이진 트리를 만들기 위함

  3. 자식 노드들과의 값 비교 → 아래로 이동 → 자식이 둘이라면, 자식 중 더 큰 값 선택

복잡도: 원소의 개수가 n인 최대 힙에서 최대 원소 삭제 → 자식 노드들과의 대소 비교 최대 회수: 2 x log2(n) → 최악 복잡도가 O(logn)의 삭제 연산


최대/최소 힙의 응용

  • 우선 순위 큐
    • enqueue할 때 느슨한 정렬을 이루고 있도록 함
    • dequeue할 때 최댓값을 순서대로 추출
  • 힙 정렬
    • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 O(logn)
    • 삽입이 끝나면 힙이 비게 될 때까지 하나씩 삭제 O(logn)
    • 원소들이 삭제된 순서가 원소들의 정렬 순서
    • 정렬 알고리즘의 복잡도: O(nlogn)
1
2
3
4
5
6
7
8
9
10
11

# 힙 정렬의 코드 구현
def heapsort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)
    sorted = []
    d = H.remove()
    while d:
        sorted.append(d)
        d = H.remove()
    return sorted
  • 알고리즘을 풀면서 느낀 점

c++ 아직 너무 약하다

long long, string에 대해서만 알아도 lv2까지는 풀 것 같다.

  • LLONG_MIN, LLONG_MAX, 계산을 long long으로 한정하기 위한 1*LL
  • string(메모리 용량 정의), vector(메모리 용량 정의)

next_permutation

1
2

    do {
    } while (next_permutation(dungeons.begin(), dungeons.end()));

행렬 테두리 회전, 피로도, 모음 사전

Classlog, devcourse
algorithm devcourse
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents