자료구조&알고리즘/이코테

[알고리즘 / 자료구조] DFS / BFS

capaca 2023. 3. 14. 21:47

⭐️  DFS/BFS ⭐️ 

- 그래프 탐색 알고리즘으로 원하는 데이터를 찾는 과정 

 

📌 사전 지식

✅ 스택 (STACK)

:  LIFO(Last In First Out, 후입선출) 의 자료구조를 의미 , 입구와 추구가 동일한 형태로 시각화 할 수 있음 (ex; 박스 쌓고 내리기)

🐍 Python 🐍 

 

스택 사용법 1 (내장함수 이용방법) 📋 

: list를 통해  append(), pop() 등이 있음 -> 시간 복잡도가 상수시간이기 때문에 그대로 사용해도 괜찮음

stack_list = [2, 5, 3, 4]
stack_list.append(1) # 괄호 내의 요소를 리스트 맨 뒤에 넣음
# stack_list = [2, 5, 3, 4, 1]
stack_list.pop() # 리스트 맨 뒤의 요소를 꺼내고 리스트에서 삭제함
# stack_list = [2, 5, 3, 4]


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

 

더보기

❗❗ append(), extend(), insert() 함수의 차이점

1) append 함수

arry.append(x) 형태로 사용한다. x를 arry의 맨 끝에 객체로 추가다. x가 iterable 자료형이더라도 전체를 하나의 객체로 해서 요소로 추가한다.

2) extend 함수

array.extend(iterable) 형태로 사용한다. iterable의 각 요소를 하나씩 array의 끝에 요소로 추가한다. append 함수와 다른 점은 괄호 안에 iterable 자료형만 올 수 있다.

3) insert 함수

array.insert(i, x) 형태로 사용한다. 원하는 위치 i에 x를 삽입할 수 있다. 값 x는 객체로 추가된다. append 함수와 마찬가지로 iterable 자료형이더라도 하나의 요소로 삽입된다.

(https://ooyoung.tistory.com/117)

스택 사용법 2 (클래스 이용방법) 📋 

class stack:
    def __init__(self):  # 스택 객체 생성
        self.items = []

    def push(self, item):  # 스택 요소 추가
        self.items.append(item)

    def pop(self):  # 스택 맨 뒤 요소 삭제하고 리턴 pop()
        return self.items.pop()

    def peek(self):  # 스택 맨 뒤 요소 리턴
        return self.items[-1]

    def isEmpty(self):  # 스택이 비었는지 확인(비었으면 True 리턴)
        return not self.items

 

🍑 C++ 🍑

#include <bits/stdc++.h>

using namespace std;

stack<int> s; // #include <stack> 에 포함되어있음

int main(void){
	s.push(5);
    s.push(2);
    s.push(3);
    s.push(7);
    s.pop();
    s.push(1);
    s.push(4);
    s.pop();
    // 스택의 최상단 원소부터 출력
    while (!s.empty()) {
    	cout << s.top() << ' ';
        s.pop();
    }
}



/*
<bits/stdc++.h> 헤더파일은 자주쓰는 헤더파일의 계열을 모두 포함함
아래 stdc++.h 파일의 내용을 확인 할 수 있다.
*/
더보기 
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

✅ 큐(Queue)

:  FIFO(First in Fisrt out, 선입선출) 먼저 들어온 데이터가 먼저 나감

🐍 Python 🐍

* 리스트 자료형으로도 가능하지만 시간복잡도가 늘어남으로 deque 라이브러리를 사용하는 것이 좋음

from collections import deque

# Queue 구현을 위한 라이브러리 사용
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])

🍑 C++ 🍑

#include <queue>
#include <iostream>

using namespace std;

queue<int> q;

int main(void){
	q.push(5);
    q.push(2);
    q.push(3);
    q.push(7);
    q.pop();
    q.push(1);
    q.push(4);
    q.pop();
    // 먼저 들어온 원소부터 추출
    while (!q.empty()){
    	cout << q.front() << ' ';
        q.pop();
    }
	
}


// 3 7 1 4

 

 

✅ 재귀함수(Recursive Function)

- 자기 자신을 다시 호출하는 함수 ( python 에서 무한히 호출하다. 최대 깊이 제한이 있기 때문에 RecursionError 오류를 띄움)

def recursive_function():
	print('재귀 함수를 호출')
    recursive_function()
    
recursive_function()

- 다음과 같이 재귀함수의 종료 조건을 줘야함

def recursive_function(i):
	if i == 100:
    	return
	print(i,'번째 재귀 함수를 호출')
    recursive_function(i+1)
    print(i,'번째 재귀 함수를 호출 종료')
    
recursive_function(1)

 

 

✅ 팩토리얼 구현

# 반복적으로 구할 경우

def factorial_iterative(n):
	result = 1
    # 1~ n 까지 수 차례대로 곱하기
    for i in range(1, n+1):
    	result *=i
    return result

def factorial_recursive(n):
	if n <=1:
    	return 1
    return n * factorial_recursive(n-1)

print(factorial_iterative(5))
print(factorial_recursive(5))


# 둘다 500으로 시간을 측정해 본 결과 
# 반복적으로 구현: 0.000274658203125 재귀적으로 구현: 0.0005156993865966797
# 반복적으로 구현: 0.00013256072998046875 재귀적으로 구현: 0.00352430343627929
# 반복적으로 구현: 0.0002524852752685547 재귀적으로 구현: 0.0006015300750732422
# 반복적으로 구현: 0.000179290771484375 재귀적으로 구현: 0.0005211830139160156

# 반복적 구현 속도가 더 빠름을 알 수 있음

 

 

** (https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3) 해당 강의의 내용과 제 생각을 더했습니다. 문제시 비공개 전환하겠습니다.

저작자표시