동적 프로그래밍(Dynamic Programming)에 대해 알아보자!

2024. 4. 3. 16:11· C#/알고리즘 기초 익히기
목차
  1. 동적 프로그래밍이란?
  2. DFS와 동적프로그래밍의 차이점!!

동적 프로그래밍이란?

  • 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다.

    네 맞습니다. DFS와 같은 개념입니다.
    기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가??

    결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다.

DFS와 동적프로그래밍의 차이점!!

 

여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다.

 

문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다.

 DFS로 접근하게 되면,

 7+3+8+2+4 = 24,
 7+3+8+2+5 = 25,
 7+3+8+7+5 = 30,
 7+3+8+7+2 = 27,
 .
 .
 .
 7+8+0+4+5 = 24.

 

이 5줄짜리 정삼각형의 모든 DFS경우의 수를 재귀함수를 통해서 구하고, 그 과정에서 최대 숫자를 계속 갱신해주면서 문제를 풀어갈 것이라고 예상됩니다.

 

 하지만 여기 함정이 있습니다.

 

삼각형이 최대 500줄이라는 것입니다. 위 대표 예제와 같이 5줄이라면 문제를 DFS로 푸는 것에 있어서 딱히 상관이 없겠지만 500줄이라면 엄청난 수의 연산을 해야합니다.

 

이 때 동적 프로그래밍을 사용하게 되면 연산의 수가 현저히 감소하게 됩니다. 다음 유튜브 영상은 10분짜리 영상인데 참고하시면 정말 이해가 빠르게 되실 겁니다.

<참고 영상: https://youtu.be/0bqfTzpWySY> >> 제꺼 아닙니다.

 

 

  • 제가 이해한 동적 프로그래밍의 개념은 중복되는 연산을 저장하여 불필요한 연산을 줄이며 결과값을 도출해내는 방법입니다. 이 때 저장하고 필요할 때 꺼내쓰는 과정을 메모이제이션(Memoization)이라고 합니다.

  • 다음은 재귀함수로만 피보나치 수열을 구현한 코드입니다.
    void Start()
    {
        //결과값 출력.
        Debug.Log(solution(10));
    }
    public int solution(int n)
    {
        //딕셔너리 초기화.
        dicFib = new Dictionary<int, long>();

        long answer = 0;

        //함수 호출.
        answer = Normal_Fibonacci(n);

        return (int)answer;
    }
    
	//재귀함수로만 구현한 피보나치 수열 함수.
    public long Normal_Fibonacci(int n)
    {
        if (n <= 1)
        {
            return n;
        }

        long num1 = Normal_Fibonacci(n - 2);
        Debug.Log("n : " + n + "num1 = " + num1);
        long num2 = Normal_Fibonacci(n - 1);
        Debug.Log("n : " + n + "num2 = " + num2);

        long result = (num1 + num2) % 1234567;
        Debug.Log("n : " + n + "result = " + result);

        return result;

    }

  • 콘솔창에 265줄이 출력됐습니다.

 

  • 다음은 Dictionary클래스를 사용하여 동적 프로그래밍을 통해 구현한 코드입니다.
    void Start()
    {
        //결과값 출력.
        Debug.Log(solution(10));
    }
    public int solution(int n)
    {
        //딕셔너리 초기화.
        dicFib = new Dictionary<int, long>();

        long answer = 0;

        //함수 호출.
        answer = Dynamic_Fibonacci(n);

        return (int)answer;
    }
    
	Dictionary<int, long> dicFib;
    
    //동적 프로그래밍을 사용한 피보나치 수열 함수.
    public long Dynamic_Fibonacci(int n)
    {
        if (dicFib.ContainsKey(n))
            return dicFib[n];

        if (n <= 1)
        {
            dicFib.Add(n, n);
            return n;
        }

        long num1 = Dynamic_Fibonacci(n - 2);
        Debug.Log("n : " + n + "num1 = " + num1);

        long num2 = Dynamic_Fibonacci(n - 1);
        Debug.Log("n : " + n + "num2 = " + num2);

        long result = (num1 + num2)%1234567;
        Debug.Log("n : " + n + "result = " + result);

        dicFib.Add(n, result);

        return result;
    }

  • 콘솔창에 28줄이 출력됐습니다.

결론

: 이진트리 문제와 같이 DFS 등으로 해결하는 문제에서 경우의 수가 너무 많아진다면 동적 프로그래밍을 사용하여 중복 연산 줄이고 시간 효율을 올릴 수 있다.


'C# > 알고리즘 기초 익히기' 카테고리의 다른 글

DFS, BFS(깊이우선탐색, 너비우선탐색)에 대해 알아보자!  (0) 2024.04.11
그리디(탐욕법) 알고리즘에 대해 알아보자!  (1) 2024.04.10
재귀 알고리즘에 대해 알아보자!  (0) 2024.04.01
순차탐색과 이진탐색 알고리즘에 대해 알아보자!  (0) 2024.04.01
힙 정렬(Heap Sort)에 대해 알아보자!  (0) 2024.04.01
  1. 동적 프로그래밍이란?
  2. DFS와 동적프로그래밍의 차이점!!
'C#/알고리즘 기초 익히기' 카테고리의 다른 글
  • DFS, BFS(깊이우선탐색, 너비우선탐색)에 대해 알아보자!
  • 그리디(탐욕법) 알고리즘에 대해 알아보자!
  • 재귀 알고리즘에 대해 알아보자!
  • 순차탐색과 이진탐색 알고리즘에 대해 알아보자!
ForMan_
ForMan_
C# 언어로 프로그래머스 문제를 풀이하고, Unity 엔진으로 게임을 개발하며, 자료구조를 공부하는 과정을 반복문처럼 꾸준히 탐구하고 공유하는 '반복해서 노력하는 남자, ForMan'의 블로그입니다.
반복해서 노력하는 남자, ForManC# 언어로 프로그래머스 문제를 풀이하고, Unity 엔진으로 게임을 개발하며, 자료구조를 공부하는 과정을 반복문처럼 꾸준히 탐구하고 공유하는 '반복해서 노력하는 남자, ForMan'의 블로그입니다.
ForMan_
반복해서 노력하는 남자, ForMan
ForMan_
전체
오늘
어제
  • 분류 전체보기
    • C#
      • 프로그래머스 코딩 문제 풀이
      • 자료구조 이해하기
      • 알고리즘 기초 익히기
    • Unity
      • Unity 디자인 패턴
      • Unity 타워디펜스게임 프로젝트
      • Unity 물리기반 Merge게임 프로젝트(수박라..
      • Unity FPS게임 프로젝트(오버워치라이크)
    • UI
      • 젠레스존제로 UI작업 시작
      • 젠레스존제로 UI 이펙트 작업
      • 젠레스존제로 UI 사운드 작업
      • 젠레스존제로 UI 스크롤뷰 작업(메뉴창)

블로그 메뉴

  • 홈
  • 방명록
  • 태그

최근 글

최근 댓글

인기 글

태그

  • 유니티디자인패턴
  • 코딩테스트
  • 유니티
  • c#
  • 오버워치만들기
  • forman
  • 정렬알고리즘
  • 수박게임
  • 머쓱이
  • 게임프로젝트
  • 완전탐색
  • 동적프로그래밍
  • 오름차순
  • 유니티게임프로젝트
  • 오버워치
  • 과일합치기
  • 타워디펜스게임
  • Unity
  • 유니티게임
  • 프로그래머스
Thanks for Skin
hELLO · Designed By 정상우.v4.2.2
ForMan_
동적 프로그래밍(Dynamic Programming)에 대해 알아보자!
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.