24.06.24 알고리즘

알고리즘

DFS

• 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
• 스택 or 재귀함수를 통해 구현한다.
• 모든경로를 방문해야 할 경우 사용에 적합하다.

시간복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)
• V(Vertex) : 정점, E(Edge) : 간선

BFS

• 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
• 큐를 통해 구현한다.
• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.

시간복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

동적 계획법(Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.
• 한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다.
• 똑같은 연산을 반복하지 않도록 만들어준다. 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이다.

접근 방식

• 커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다.
• 동적 계획법은 간단한 작은 문제들 속에서 ‘계속 반복되는 연산’을 활용하여 빠르게 풀 수 있는 것이 핵심이다.

조건

• 작은 문제에서 반복이 일어난다.
• 같은 문제는 항상 정답이 같다.
• 같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization)으로 큰 문제를 해결해나가는 것이다.
  • 메모이제이션(Memoization) : 한번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

구현 방식

• Bottom-up : 작은 문제부터 차근차근 구하는 방법
• Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법(재귀 방식)
• 동적 계획법으로 문제를 풀 때는, 우선 작은 문제부터 해결해나가보는 것이 좋다.
• 작은 문제들을 풀어나가다보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해내어 동적 계획법을 적용시키자.