문제
프로그래머스의 문제를 해결하던 중 DFS와 BFS라는 개념이 등장했다. 깊이우선탐색, 너비우선탐색이라는 말로도 불리는 두개의 개념에 대해서 정확히 알지 못해서 유튜브 강의를 보고서 이와 관련된 내용을 알아가던 중 DFS,BFS를 알기 위해서는 먼저 스택, 큐, 재귀함수에 대하 이해가 필요하다고 해서 지금까지 이해한 내용들을 작성해보려고 한다.
스택
스택은 쌓는 것을 상상하면된다. 책은 위에서 부터 하나씩 쌓을 수 있고, 쌓인 책은 위에서 부터 하나씩 꺼내야 한다. 그렇기 때문에, 스택의 경우 위에서 top이라는 부분에서만 입력과 출력이 가능하고, 후입선출이라고해서 늦게 들어온 것이 먼저나가는 형태이다.
python에서 스택을 사용하는 방법은 리스트 객체를 이용하면 된다. 리스트의 경우 append()와 pop()메서드가 있어서 이를 활용하면, 간단히 stack을 사용할 수 있다.
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)
[10, 20, 30]
stack.pop()
print(stack)
[10, 20] 위의 print문의 결과를 보면 나중에 들어온 30이라는 값이 먼저 나간다. python에서는 단순히 리스트를 이용해서 stack을 구현할 수 있다. 리스트의 append()와 pop()의 경우 시간복잡도는 상수시간에 가능하기 때문에 빠르다.
큐
큐는 스택과는 달리 먼저들어온 값이 먼저 나가는 형태로, 일반적으로 줄을 서는 모습을 상상하면된다. 앞에 있는 사람이 먼저 밥을 먹든, 서비스를 받든 한다. 큐를 구현하기 위한 방법으로는 리스트와, python에서 제공하는 deque 모듈이 있다. 기본적으로 사용하는 것은 deque이다. 리스트를 이용해서 구현할 수도 있지만, 그 경우 pop()을 할 시 시간복잡도가 늘어나게 된다. pop()으로 맨 앞의 값을 꺼내야 하는데, 꺼내고 난 뒤에 모든 요소를 한 칸씩 앞으로 이동시켜 주어야 한다. 그렇기 때문에, deque를 이용하는 것이 편리하다. deque에는 append()와 popleft()이 있어서 상수시간에 값을 집어 넣거나, 빼는 것이 가능하다.
from collections import deque
queue =deque()
queue.append(10)
queue.append(20)
queue.popleft()재귀함수
재귀함수는 자기 자신을 부르는 함수를 의미한다. 이는 DFS에서 많이 사용되는 방법이기에 이해하고 넘어갈 필요가 있다.
재귀함수는 함수안에 자기를 부르는 함수를 다시 넣는 로직이다. 그렇기 때문에, 종료시점을 지정하지 않으면 무한 반복에 빠질 수 있다. 파이썬의 경우 재귀함수를 부를 깊이가 정해져 있어서 몇 회 이상의 재귀함수를 부를 시 오류를 내게 된다.
오류가 발생하는 이유는 보통 함수가 불리게 되면 cpu의 스택에 함수가 쌓이게 되고 해당 함수가 불리게 된다. 재귀함수를 이용하게 되면, 스택에 계속해서 함수가 쌓이게 되는 것이고, 스택의 허용치를 넘기기 때문에 오류가 나는 것이다. 그렇기 때문에 위에서 말한 것과 같이 종료시점을 알려주어야 한다.
def recursive():
print("재귀함수 호출")
recursive()위의 함수를 호출하게 되면, 계속해서 print문을 출력하다가 오류가 발생하게 된다.
maximum recursion depth exceeded while calling a Python objectdef recursive(i):
if i == 100:
return
print(f"{i}재귀함수에서 {i+1} 재귀함수 호출")
recursive(i+1)
print(f"{i}재귀함수 완료")
recursive(1)위와 같이 i==100이라는 조건과 함께 재귀함수에 인자를 넣어줌으로써 무한으로 재귀함수를 호출하는 것을 막을 수 있다.
팩토리얼
재귀함수를 이용한 문제풀이 중 기본이 되는 것이 팩토리얼 문제이다. 팩토리얼이란 number가 주어졌을때 number부터 1까지의 곱을 구하는 것이다.
5! = 5*4*3*2*1
4! = 4*3*2*1
이를 수학적으로 정리해보면 n! = n * (n-1)! 이다 그렇기 때문에 재귀함수로 계속해서 팩토리얼을 부르면 간단하게 팩토리얼 문제를 해결할 수 있다.
def factorial(i):
if i == 1:
return 1
return i * factorial(i-1)
result = factorial(10)유클리드 호제법
최대 공약수를 구하는 방법으로 수학적으로 증명된 방법이라고 한다. 증명이 어떻게 되는 지는 알지 못하나, 개념은 A>B에 해당하는 두개의 수 A,B가 있을 때 A를 B로 나눈 나머지 R이다. 이 경우 A와 B의 최대 공약수는 B와 R의 공약수와 같다. 라는 식이 증명되었다고 한다. 이를 재귀함수를 이용해서 로직을 구현하면 다음과 같다.
def gcd(A,B):
if A%B == 0:
return B
else:
return gcd(B, A%B)이번에 정리한 내용들은 DFS와 BFS를 알기 위한 사전지식이기 때문에 간단히 개념만 알고 넘어가는 것에 지나지 않는다. 이외에도 더 많은 내용이 있기에 따로 알아봐야겠다.
