Week 2 - 5

Dynamic Programming(동적 계획법)

특징

• 재귀적인 방식으로 보다 작은 부분 문제로 나누고 부분 문제를 푼 해를 조합하여 전체 문제의 해답에 이르는 방식.
• 실제로 문제를 푸는 법
  1. 테이블 정의하기(1차원(D[i] 또는 2차원(D[i][j]) 배열 설정)
  2. 점화식 찾기
  3. 초기값 설정

 

DFS, BFS

특징

• 그래프
  • 정점(vertex, node)과 간선(edge, link)으로 이루어진 자료구조
  • 유향(directed) 그래프와 무향(undirected) 그래프가 있다.
• 실제로 문제를 푸는 법
  1. 시작하는 칸을 queue(BFS), stack(DFS)에 넣고 방문표시를 남김.(boolean 배열 이용)
  2. 선택한 자료구조에서 원소를 꺼내며 그 칸의 상하좌우로 인접한 칸에 대해 3번 진행
  3. 해당 칸을 방문했는가?
     • yes : 아무것도 안함
     • no : 자료구조에 넣고 방문표시를 남김
  4. 자료구조가 빌 때 까지 2번 반복