happyso
study with happyso
happyso
전체 방문자
오늘
어제
  • 분류 전체보기 (300)
    • GIT (3)
    • 컴퓨터 기본 개념 (29)
    • 알고리즘 (125)
      • 알고리즘 문제 (115)
      • 알고리즘 개념 (10)
    • Go (2)
    • 클라우드 (53)
      • DevOps (3)
      • Kubernetes(쿠버네티스) (33)
      • AWS (6)
      • CKA (8)
    • 리눅스(Linux) (18)
      • 컨테이너(Container) (8)
    • Front (22)
      • JavaScript (2)
      • React (20)
    • Python (21)
      • Python 웹 크롤링 (11)
      • Django (7)
      • MachineLearning (3)
    • 데이터베이스 (6)
      • MariaDB (2)
      • MongoDB (4)
    • C언어 (5)
    • Trouble Shooting (2)
    • 네트워크 (8)
      • CCNA (5)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • replace
  • Patch
  • kubernetes
  • apply
  • 15
  • edit
  • 18

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
happyso

study with happyso

알고리즘/알고리즘 개념

다이나믹 프로그래밍

2020. 8. 11. 00:34

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

- 문제에는 크기가 있어야함

- 각각의 작은 문제를 풀고 원래대로 합친다.

- Dynamic에 대한 어떠한 의미도 없음 -> 헷갈리지마셈 ㅎㅅㅎ

 

<분할정복 알고리즘과의 차이점>

  - 다이나믹 알고리즘 : 작은 문제가 중복가능

  - 분할정복 알고리즘 : 작은 문제가 중복되지 않음

 

<두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.>

1. Overlapping Subproblem : 부분문제 겹친다. 2. Optimal Substructure : 최적 부분 구조
* 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. * 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
* 문제를 작은 문제로 쪼갤 수 있다.  
* 예시(피보나치 수)

- 문제 : N번째 피보나치 수를 구하는 문제
- 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

- 문제 : N-1번째 피보나치 수를 구하는 문제
- 작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

*예시

- 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면

- 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야한다.

 

<Optimal Substructure를 만족한다면 , 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. >

10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 
9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 
...
4 번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 

=> 4번째 피보나치 수는 항상 같다.

 

- 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.

- Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.

- 따라서, 정답을 한 번 구했으면, 어딘가 메모해놓는다.

- 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.

- 메모를 한다고 해서 영어로 Memoization이라고 한다.(캐시와 비슷)

int memo[100];
int fibonacci(int n){
    if(n<=1){
        return n;
    }else{
        if(memo[n] > 0){
            return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return momo[n];
    }
}

 

 

<다이나믹을 푸는 두 가지 방법이 있다.>

1. Top-down : 재귀함수

- 위에서 진행한 예제

 

2. Bottom-up : for문 사용

- 문제를 크기가 작은 문제부터 차례대로 푼다.

- 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

- 작은 문제를 풀면서 왓기 때문에, 큰 문제는 항상 풀 수 있다.

- 그러다 보면, 언젠간 풀어야 하는 문제는 풀 수 있다.

int d[100];
int fibonacci(int n){
    d[0] = 0;
    d[1] = 1;
    for(int i=2; i<=n; i++){
        d[i] = d[i-1] + d[i-2];
    }
    return d[n];
}

 

 

 

 

 

 

 

 

 

'알고리즘 > 알고리즘 개념' 카테고리의 다른 글

정렬 알고리즘  (0) 2020.10.21
자료구조와 알고리즘  (0) 2020.10.14
탐욕알고리즘(Greedy)  (0) 2020.08.22
그래프의 탐색(DFS, BFS)  (0) 2020.08.04
그래프와 BFS  (0) 2020.08.03
    '알고리즘/알고리즘 개념' 카테고리의 다른 글
    • 자료구조와 알고리즘
    • 탐욕알고리즘(Greedy)
    • 그래프의 탐색(DFS, BFS)
    • 그래프와 BFS
    happyso
    happyso

    티스토리툴바