ABOUT ME

궁금하니깐

Today
Yesterday
Total
  • [DFS / BFS] 스택자료구조, 큐자료구조, 재귀함수
    코딩/🤦 ALGORITHM 2022. 2. 8. 01:11

    그래프 탐색 알고리즘에 있어 대표적인 알고리즘 DFS와 BFS를 알아보기 전에 선행되어야 할 개념이 있다.

    바로 스택(stack)자료구조와 큐(Queue)자료구조가 그것이다. 

     

    Stack 자료구조

    마치 책을 쌓아 놓고 위에서부터 꺼내는 방식의 알고리즘이라고 생각하면 쉽다.

    FILO 즉, 선입후출의 방식인 것이다. 

    예를 들어 삽입을 5 - 2 - 7 - 삭제 - 1 - 4  삭제의 과정이 있다면 

    stack을 출력하면, 5 2 1 만 밑에서부터 남게 될 것이다. 

     

    이를 파이썬 코드로 표현하자면 append와 pop으로 구현할 수 있다. 

    stack = [] 
    
    stack.append(5)
    stack.append(2)
    stack.append(3)
    stack.append(7)
    
    stack.pop()
    
    stack.append(1)
    
    stack.pop()
    
    stack.append(4)
    
    
    print(stack)
    >>> [5, 2, 3, 4]

     

    큐 자료구조 

    큐는 마치 파이프에서 물이 빠지듯이 나가는 구조라고 생각하면 된다. 

    선입후출 (FIFO) 방식으로 먼저 들어온 정보가 먼저 빠져나가는 알고리즘이다. 

     

    이를 파이썬 코드로 작성하게 된다면, deque라는 내부라이브러리를 사용할 수 있다. 

    파이썬 코드로 구현이 가능하지만 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.reverse()
    print(queue)
    >>> deque([4, 1, 7, 3, 2])
    
    #나중에 들어온 순서부터
    print(queue)
    >>> deque([2, 3, 7, 1, 4])

     

    재귀함수

    재귀함수란 자기함수를 다시 호출하는 함수로 반복해서 자기를 호출하는 경우 사용한다,

    영어로는 Recursive Function이라고 하는데, 반드시 종료조건을 넣어야 멈추게 되는 함수라는 걸 잊지 말아야 한다. 

    예를 들어보자.

    #재귀함수
    def recursive_function(i):
        if i == 10:
            return 
        print(i,'번째', i+1, '번째 호출')
        recursive_function(i+1)
        print(i, '종료')
    recursive_function(1)
    
    1 번째 2 번째 호출
    2 번째 3 번째 호출
    3 번째 4 번째 호출
    4 번째 5 번째 호출
    5 번째 6 번째 호출
    6 번째 7 번째 호출
    7 번째 8 번째 호출
    8 번째 9 번째 호출
    9 번째 10 번째 호출
    9 종료
    8 종료
    7 종료
    6 종료
    5 종료
    4 종료
    3 종료
    2 종료
    1 종료

    함수를 호출하는 로직을 살펴보면

    - 1번 호출하고 2번째 자기함수를 호출하다가 

    - 10번째 호출이 되고나서 차례대로 9번째 호출한 것이 종료되고, 8번째 호출한 것이 종료되고

    - 마지막으로 1번째가 종료되는 것을 알 수 있다. 

     

    마치 스택에서 데이터를 꺼내는 것과 같이 작동하는 것을 알 수 있다. 

    이를 토대로 팩토리얼과 최대공약수를 구현할 수 있다! 

    팩토리얼 구현

    이를 토대로 팩토리얼을 구현하자면

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

    0 ! = 1 ! = 1 이라는 사실은 알아두고 구현하자. 

    # 팩토리얼 구현예제
    def factorial_recursive(n):
        if n <= 1:
            return 1
        return n * factorial_recursive(n-1)

    이를 반복문으로도 구현할 수 있지만, 재귀함수를 통해서 구현할 수 있으며, 시간복잡도 또한 반복문보다 낮은 평가를 받을 수 있어 효율적이다. 

    최대공약수 구현 (유클리드 호제법)

    두개의 자연수에 대한 최대공약수를 찾으려면 두가지 전제조건을 만족시켜야한다.

     

    -  두 자연수 A, B (A>B)에 대해서 A를 B로 나눈 나머지가 R

    -  이때, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다 

     

    예를 들어 GCD(192,162)를 구한다고 해보자.

    여기서 GCD는 최대공약수를 뜻한다. 

    A B  
    192 162  
    162 30 -> R
    30 12 -> R
    12 6 -> R

    정리하면, 192와 162 최대공약수와 12와 6의 최대공약수가 같다는 것이므로 

    6 이 최대 공약수인 것이다. 

    # 재귀함수 
    def gcd(a,b):
        # a와 b가 나눴을 때 0이란 말은 a가 b의 배수라는 뜻이다. 전제조건이 (a>b)이기 때문에! 
        if a % b == 0:
            return b
        else:
            # b와 a를 b로 나눈 나머지 R의 최대공약수
            return gcd(b, a % b)
    gcd(192, 162)
    
    >>> 6

     

    참고문헌

    더보기

    이것이 취업을 위한 코딩테스트다 동영상을 공부하고 TIL입니다

     

Designed by Tistory.