[데브코스 9일차] 백트래킹과 동적 계획법

💡 키워드

- 백트래킹

- 동적 계획법(Dynamic Programming)

 

[1] 백트래킹

특정 알고리즘이라기 보다는 모든 경우의 수를 탐색한다는 개념. 보통 DFS, BFS를 이용하는 경우가 많다.

백트래킹에서 중요한 점은 효율을 높이기 위해 가지치기를 하여 탐색할 경우의 수를 점점 줄여나가는 것.

재귀를 이용하는 경우가 많으므로 순환(무한루프)에 빠지지 않도록 한다.

방법

1. 우선 모든 경우의 수를 찾을 수 있도록 한다.

2. 특정 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건을 건다. (가지치기)

대표적인 문제

- N-Queen 문제, 체스 문제 등

 

[2] 동적 계획법(Dynamic Programming)

"큰 문제를 작은 문제로 나누어서 해결한다"

즉 작은 문제의 규칙을 찾아서 큰 문제를 해결하는 방식을 말한다. 또 해결한 문제는 다시 해결하지 않는다. 규칙성이 있고, 작은 문제의 해결 방식이 큰 문제에도 동일하다면 DP문제일 가능성이 높다.

대표적인 문제) 피보나치 수열

피보나치 수열은 DP를 설명할 때 가장 처음에 나오는 문제이다.

피보나치 수열) 1 1 2 3 5 8 13 21 34 ...

n번째 피보나치 수열의 값은 아래와 같이 점화식으로 표현할 수 있다.

 

$$f(n)=f(n-1)+f(n-2)$$ (단, n > 1)

 

하지만 f(15) 를 구하려면 같은 연산을 몇 번 해야할까?

하지만 위 그림처럼 f(15)를 구하는 동안 반복된 연산을 하게 된다. 점화식을 그대로 재귀함수로 구현한다면.... 한번 해보는 것을 추천한다.

 

타뷸레이션과 메모이제이션

이러한 문제를 해결하기 위해, 공간(메모리)을 더 사용하여 시간을 획기적으로 줄인다는 타뷸레이션, 메모이제이션의 방식을 사용할 수 있다.. 일반적으로 타뷸레이션은 상향식 접근, 메모이제이션은 하향식 접근이라고 한다.

 

프로그래머스 Lv2 연습문제 <피보나치 수>

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

연습문제를 한번 풀어보고, 시간초과가 나왔다면 타뷸레이션과 메모이제이션 방식을 사용해보자.

나의 풀이

https://ryong9rrr.github.io/pgm-lv2-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98/

프로그래머스 Lv2) 피보나치 수

 

💡 오늘의 회고

허허... 어제 입국심사에 이어 N-Queen과 단어 퍼즐을 풀지 못했다. 이번에도 거의 1~2시간 고민을 했지만... 해결 방법 자체가 떠오르지 않아 풀이를 참고했음... 풀이 방법 자체가 떠오르지 않은 문제들은 아예 정말 '벽'을 느껴버린다. 이런 문제들은 풀이 방법을 봐도 잘 모르겠다... 역시 알고리즘은 꾸준한 연습이 필요한 것 같다...

그리고 오늘 팀원들의 1주차 과제 코드리뷰를 했다. 다들 정말 좋은 코드를 짜셨고, 코드를 짜는데 많은 고민을 하셨겠구나 라는 느낌을 받았다. 내 코드도 다른 분들에게 그런 평가를 받았으면 좋겠다.