꼭 필요한 자료구조 기초

그래프 탐색 알고리즘: DFS/BFS

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

반드시 알아야 할 자료구조

스택

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. (박스 쌓기, 빼기)
  
  
  

큐

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
  

재귀 함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.
• 재귀 함수의 종료조건을 반드시 명시해야 한다.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.

유클리드 호제법

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
• 유클리드 호제법
  - 두 자연수 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)
    
print(gcd(192, 162))

6

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
• 재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
  - 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다