Algorithm) 자료구조 기초 (Feat. DFS와 BFS에 들어가기 전..)

DFS와 BFS를 다루기 전 .. 저 멀리 잊고 있었던 자료구조 기초 파트가 있길래 정리해봅니다 !

 

✨ 탐색(Search)이란 ? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루는데 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있습니다 ! 그런데,, DFS와 BFS 를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제 되어야 하무로 살짝 정리하고 갑니다 ~ 

 

🌿 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 ! 

- 기초 개념인 스택과 큐에서 Push, Pop 과 같은 핵심적인 함수 이 외에도 오버플로, 언더플로를 고민해야한다.

- 오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 

- 언더플로는 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생 

 

1. 스택 Stack

- 박스 쌓기에 비유할 수 있다. 선입후출 

- 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다.

- 기본 리스트에서 append() 와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작 

- append()는 리스트의 가장 뒤쪽에서 데이터를 삽입하고, pop()은 리스트에 가장 뒤쪽에서 데이터를 꺼내기 때문 ! 

 

2. 큐 

- 대기줄에 비유할 수 있다. 선입선출 

- from collections import deque : 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 

deque 자료구조를 활용하자 ( queue = deque() )

- deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 뺴는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 간단하다 ! 

- 대부분 코테에서 collections 모듈과 같은 기본 라이브러리 사용을 허용한다 !

- deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용하자 : list(queue)

 

3. 재귀함수

DFS와 BFD 를 구현하려면 재귀함수도 이해해야된다 !

- 자기 자신을 다시 호출하는 함수 

- 파이썬 인터프리터는 호출 횟수 제한이 있어서 재귀함수가 계속 호출되다가 재귀의 최대 깊이를 초과했을 때 오류메시지가 뜬다 ! ( 무한대로 재귀호출을 진행할 수 없다. 그런 문제 또한 출제되지 않을 것 ! )

 

📌 재귀함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.

종료조건을 명시하지 않을 경우, 함수가 무한 호출될 수 있다. 

def recursive_function(i):
	#100번째 출력했을때 종료되도록 종료조건 명시
    if i == 100:
    	return
    print(i,'번째 재귀함수에서' , i+1,'번째 재귀함수 호출')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료')

recursive_function(1)

- 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용

- 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문 !

- 내부적으로 스택 자료구조와 동일하다 !

- 따라서 , 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀함수를 이용해서 간편하게 구현될 수 있다 !

- 대표적인 예가 DFS 

- 팩토리얼 문제 : n! = 1 x 2 x 3 x ... x (n-1) x n -> 수학적으로 0! 과 1!의 값은 1로 같다는 성질을 이용하여 팩토리얼 함수는 n 이 1 이하가 되었을 때 함수를 종료하는 재귀함수의 형태로 구현할 수 있다 ! 

 

# 반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    for i in range(1, n+1):
    	result *= i
    return result
    
# 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <= 1:
    	return 1
    return n + factorial_recursive(n-1)

-  실행 결과는 동일 ! 재귀함수를 사용했을때 코드가 더 간결함 . 

-  왜 ? 수학의 점화식을 그대로 소스코드로 옮겼기 때문 ! 

- 점화식 ? 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미 

- 일반적으로 우리는 점화식에서 종료조건을 찾을 수 있다  n이 0 또는 1일때 

- 양의 정수일때만 유효 : n 이 1 이하인 경우 1을 반환 

- 음수값일 땐 ? 입력 범위오류 !

 

 

 

여기까지 DFS 와 BFS 하기전의 필요한 자료구조 기초 개념을 살펴봤다 >> 이제 찐 DFS BFS 하러 가보쟈고 ~