211126 탐색, 자료구조 개념

탐색, 자료구조

탐색 (Search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS, BFS 를 꼽을 수 있는데, 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 그런데 DFS 와 BFS 를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다.

자료구조(Data Structure)

데이터를 표현, 관리, 처리 하기 위한 구조

스택과 큐를 사용할 때는 삽입/삭제/오버플로우/언더플로우 모두를 고민해야한다.

• 삽입 (Push) : 데이터 삽입
• 삭제 (Pop) : 데이터 삭제
• 오버플로 (Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생.
  저장공간을 벗어나 데이터가 넘쳐 흐를 때 발생
• 언더플로 (Underflow) : 자료구조에 데이터가 전혀 들어있찌 않은 상태에서 삭제 연산을 수행할 때 발생

자료구조 종류

스택 (Stack)

선입 후출 (First In Last Out) 또는 후입 선출 (Last In First Out) 구조

재귀 함수(Recursive Function) 의 연속해서 호출되는 함수는, 메인 메모리의 스택 공간에 적재되므로 스택 자료구조와 같다고 볼 수 있다.
따라서 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용하여 간편하게 구현할 수 있다.

큐 (Queue)

선입선출 (First In First Out) 구조

재귀함수 (Recursive Function)

자기 자신을 호출하는 함수

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다.
함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 호출이 종료되기 때문이다.

연속해서 호출되는 함수는, 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 비슷하다. 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀함수를 이용하여 구현할 수 있다.

반복문보다 재귀함수를 사용했을 때, 코드가 조금 더 간결해진다는 장점이 있다. 더 간결한 이유는 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다. 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다. 이 개념은 '다이나믹 프로그래밍' 으로 이어지기 때문에 중요하다.

계승 (Factorial)

재귀함수를 이용하는 대표적인 예제로는 팩토리얼 문제가 있다.

팩토리얼은 기호로 간단하게 n! 로 나타내며, 1부터 n 까지의 자연수를 모두 곱하는것을 의미한다.

n! = 1 * 2 * 3 * ... * (n - 1) * n

수학적으로 0! 과 1! 의 값은 1 로 같다는 성질을 이용하여, 팩토리얼 함수는 n 이 1 이하가 되었을 때 함수를 종료하는 재귀함수의 형태로 구현할 수 있다.

---

팩토리얼을 수학적 점화식으로 표현해보면 다음과 같다.

1. n 이 0 혹은 1 일때 종료 :: $factorial(n) = 1$
2. n 이 1 보다 클 때 종료 :: $factorial(n) = n × factorial(n - 1)$

일반적으로 점화식에서 _종료조건_을 찾을 수 있는데, 두 예시에서 종료 조건은 'n 이 0 혹은 1 일때' 이다. 재귀 함수 내에서 특정 조건일 때 더이상 재귀적으로 함수를 호출하지 않고 종료하도록 if 문을 이용하여 꼭 종료 조건을 구현해주어야한다.

다시 한번 앞의 점화식과 조금 전에 작성했던 팩토리얼 재귀함수 버전을 비교해보면, 재귀함수의 소스코드와 점화식이 매우 닮아있다는 것을 확인할 수 있다.

---

Stack & Queue & 재귀함수 코드

Stack

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)        # [5, 2, 3, 1]
print(stack[::-1])  # [1, 3, 2, 5]  최상단 원소부터 출력

class Stack {
  constructor () {
    this.arr = []
    this.index = 0
  }

  peek () {
    return `arr : [ ${this.arr} ], index: ${this.index}, length: ${this.arr.length}`
  }

  push (item) {
    this.arr[this.index++] = item
  }

  pop () {
    if (this.index <= 0) return null
    return this.arr.splice(--this.index, 1)
  }
}

const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
console.log(stack.peek()) // arr : [ 1,2,3 ], index: 3, length: 3 
stack.push(4)
console.log(stack.peek()) // arr : [ 1,2,4 ], index: 3, length: 3
stack.pop()
stack.pop()
stack.pop()
console.log(stack.peek()) // arr : [  ], index: 0, length: 0

Queue

Python 으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자!
deque 는 스택/큐 장점을 모두 채택한것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효과적이며, queue 라이브러리보다 더 간단하다. 또한 코딩테스트에서 기본 라이브러리 사용을 허용한다.

# 큐 구현을 위해 deque 라이브러리 사용
from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

# 먼저 들어온 순서대로 출력
print(queue)  # deque([3, 7, 1, 4])

queue.reverse()
print(queue)  # deque([4, 1, 7, 3])

list(queue) # list 로 사용하는 방법

class Queue {
  constructor() {
    this.arr = []
  }
  enqueue(item) {
    this.arr.push(item)
  }
  dequeue() {
    return this.arr.shift()
  }
}

const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.arr) // [1, 2, 3]
queue.dequeue()
console.log(queue.arr) // [2, 3]
queue.enqueue(5)
console.log(queue.arr) // [2, 3, 5]
queue.dequeue()
console.log(queue.arr) // 3, 5

재귀함수 (Recursive Function)

Factorial

# for 반복으로 구현한 n!
def factorial_iterative(n):
  result = 1

  # 1 부터 n 까지의 수를 차례대로 곱하기
  for i in range(1, n + 1): result *= i
  return result

#######

# 재귀적으로 구현한 n!
def factorial_recursive(n):
  if (n <= 1): return 1    # n 이 1 이하인 경우 1 반환

  # n! = n * (n - 1) 를 그대로 구현하기
  return n * factorial_iterative(n - 1)

print('for 반복으로 구현 : ', factorial_iterative(5))  # 120
print('재귀적으로 구현 : ', factorial_iterative(5))    # 120

function factorial_iterative (n) {
  result = 1
  for (let i = 1; i < n + 1; i++) result *= i
  return result
}

function factorial_recursive (n) {
  if (n <= 1) return 1
  return n * factorial_recursive(n - 1)
}

const withFor = factorial_iterative(5)
console.log(withFor)
const withRecursive = factorial_recursive(5)
console.log(withRecursive)