알고리즘 문제

다이나믹 프로그래밍 문제를 풀면서 느낀 것

als982001 2024. 2. 4. 19:32

Pixabay로부터 입수된 Daniel Mena님의 이미지 입니다.

 

 

 다이나믹 프로그래밍 문제를 풀면서 느낀 것이 있다. 문제 풀이의 유형이 크게 재귀 함수를 이용하는 방법과 반복문을 이용하는 방법으로 나뉜다는 것이었다. 물론 모든 문제가 이런 것은 아니며, 또 문제를 푸는 사람에 따라 다른 방식을 이용할 수도 있을 것이다. 어쨌든 내가 문제를 풀 때에는 크게 두 가지 유형으로 나뉘는 느낌이었다. 그래서 이 두 유형의 차이점을 간단하게 기록하려고 한다.

 

1. 재귀함수

  • 큰 문제를 작은 문제로 나누어 해결하는 방식
  • 복잡한 문제에서 시작해 딱 필요한 하위 문제만을 해결하기 위함
  • 스택 오버플로우같은 문제가 발생할 위험이 있음
  • 피보나치 수열, 최소 편집 거리 등, 재귀적 구조가 명확한 문제에 적합

2. 반복문 

  • 작은 문제부터 시작해 점차 큰 문제를 해결하는 방식
  • 초기 상태 설정이나 반복 로직 구성하기 어려울 수 있음
  • 동전 교환, 배낭 문제 등, 초기 조건에서 출발해서 점진적으로 해를 구축해나가는 문제에 적합

 

재귀함수 방식 예시 문제

반복문 방식 예시 문제