개념- 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 목적- 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선  메모리 사용 : 배열 또는 자료구조 만들중복 연산 줄이기 : 연산 결과를 배열에 담기  판단 기준  - DFS / BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제 - 경우의 수에 중복 연산이 많은 경우 구현 방법- Bottom-Up : 아래에서부터 계산하고 누적시켜서 전체 큰 문제 해결- Top-Down : 위에서 시작해서 내려간 뒤에 결과 값을 재귀를 통해 재활용Bottom-UpTop-Down작은 문제부터 풀기-> 작은 문제 답을 이용해서 큰 문제 풀기-> 반복해서 최종 문제 풀기큰 문제를 작은 문제로 나누..

DFS (Depth First Search) : 깊이 우선 탐색그래프 탐색의 종류루트 노드 또는 임의의 노드에서 시작해서 최대 깊이까지 탐색 후 돌아와서 다른 노드 탐색Stack 사용 현재 경로에 있는 노드만 기억하면 된다목표 노드가 깊은 단계에 있으면 해를 빨리 구할 수 있다해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸림얻어진 해가 최단 경로라는 보장이 없음 구현 방법인접 행렬 (Adjacency Matrix) : 행렬로 정점 사이의 관계 표현 인접 리스트 : 리스트 방식으로 정점이 연결된 노드의 정보 저장 BFS (Breadth First Search) : 너비 우선 탐색그래프 탐색의 종류루트 노드 또는 임의의 노드에서 시작해서 인접한 노드 먼저 모두 확인 후 다른 노드 탐색Queue 사용 거리가..