문제 : Minimum Substring Partition of Equal Character Frequency(20240717)
난이도 : 중급
URL : https://leetcode.com/problems/minimum-substring-partition-of-equal-character-frequency/description/
본격 강의에 앞서, 동적 프로그래밍과 함수형 프로그래밍에 대한 이해를 돕기 위해 간략히 다음과 같이 정리하였습니다.
동적 프로그래밍(Dynamic Programming, DP)
동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 간단한 하위 문제들로 나누어 해결하는 알고리즘 기법입니다. 이 방법은 주로 최적화 문제를 해결하는 데 사용되며, 하위 문제들의 결과를 저장하여 동일한 계산을 반복하지 않도록 함으로써 효율성을 높입니다.
동적 프로그래밍의 핵심 개념은 다음과 같습니다:
- 중복되는 하위 문제: 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 반복되는 경우가 많습니다. 동적 프로그래밍은 이러한 중복 계산을 피하기 위해 하위 문제의 결과를 저장합니다.
- 최적 부분 구조: 원래 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있어야 합니다. 즉, 문제를 작은 하위 문제들로 나누어 해결하고, 이 하위 문제들의 해를 결합하여 원래 문제의 해를 구할 수 있어야 합니다.
동적 프로그래밍은 주로 두 가지 방식으로 구현됩니다:
- 메모이제이션(Memoization): 재귀적 접근법을 사용하여 하위 문제의 결과를 저장하는 방식입니다. 처음 계산된 하위 문제의 결과를 메모리에 저장해 두고, 이후 동일한 하위 문제가 발생하면 저장된 결과를 재사용합니다.
- 타뷸레이션(Tabulation): 반복적 접근법을 사용하여 하위 문제를 해결하는 방식입니다. 작은 하위 문제부터 차례대로 해결해 나가면서, 그 결과를 테이블에 저장합니다. 최종적으로 원래 문제의 해는 이 테이블을 참조하여 구할 수 있습니다.
동적 프로그래밍의 대표적인 예로는 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack Problem), 최단 경로 문제 등이 있습니다. 이 기법을 사용하면 많은 최적화 문제를 효율적으로 해결할 수 있습니다.
함수형 프로그래밍(Functional Programming)
함수형 프로그래밍(Functional Programming)은 프로그래밍 패러다임 중 하나로, 프로그램을 함수의 연속으로 구성하는 방식입니다. 이 패러다임은 수학적 함수의 개념을 기반으로 하며, 상태와 가변 데이터를 피하고 순수 함수를 사용하는 것을 강조합니다. 함수형 프로그래밍의 주요 특징은 다음과 같습니다:
- 순수 함수(Pure Functions): 순수 함수는 동일한 입력에 대해 항상 동일한 출력을 반환하며, 함수 외부의 상태를 변경하지 않습니다. 즉, 부작용(side effects)이 없습니다. 이는 함수의 예측 가능성을 높이고, 테스트와 디버깅을 용이하게 합니다.
- 불변성(Immutability): 함수형 프로그래밍에서는 데이터가 불변(immutable)입니다. 즉, 한 번 생성된 데이터는 변경되지 않으며, 데이터의 변경이 필요할 경우 새로운 데이터를 생성합니다. 이는 프로그램의 상태를 추적하고 관리하는 데 도움을 줍니다.
- 고차 함수(Higher-Order Functions): 함수형 프로그래밍에서는 함수를 일급 객체(first-class citizen)로 취급합니다. 즉, 함수를 변수에 할당하거나, 함수의 인자로 전달하거나, 함수의 반환값으로 사용할 수 있습니다. 고차 함수는 다른 함수를 인자로 받거나, 함수를 반환하는 함수입니다.
- 함수 합성(Function Composition): 작은 함수들을 조합하여 더 복잡한 함수를 만드는 기법입니다. 이는 코드의 재사용성을 높이고, 모듈화된 코드를 작성하는 데 도움을 줍니다.
- 지연 평가(Lazy Evaluation): 필요할 때까지 계산을 미루는 기법입니다. 이는 성능을 최적화하고, 무한 데이터 구조를 다루는 데 유용합니다.
함수형 프로그래밍의 장점은 다음과 같습니다:
- 가독성: 순수 함수와 불변성을 사용하면 코드가 더 예측 가능하고 이해하기 쉬워집니다.
- 테스트 용이성: 부작용이 없기 때문에 함수 단위 테스트가 용이합니다.
- 병렬 처리: 상태 변경이 없으므로 병렬 처리가 더 안전하고 간단합니다.
함수형 프로그래밍을 지원하는 언어로는 Haskell, Lisp, Erlang, Scala, F#, Clojure 등이 있으며, JavaScript, Python, Java 등 많은 언어에서도 함수형 프로그래밍 스타일을 지원하는 기능을 제공합니다.
함수형 프로그래밍과 동적 프로그래밍의 유사점과 차이점
함수형 프로그래밍(Functional Programming)과 동적 프로그래밍(Dynamic Programming)은 각각 프로그래밍 패러다임과 알고리즘 기법으로, 서로 다른 목적과 특성을 가지고 있습니다. 그러나 둘 사이에는 몇 가지 유사점과 차이점이 존재합니다.
유사점
(1) 재사용성:
함수형 프로그래밍: 순수 함수와 고차 함수를 사용하여 코드의 재사용성을 높입니다.
동적 프로그래밍: 하위 문제의 결과를 저장하여 재사용함으로써 중복 계산을 피합니다.
(2) 불변성:
함수형 프로그래밍: 데이터의 불변성을 강조하여 상태 변화를 피합니다.
동적 프로그래밍: 메모이제이션이나 타뷸레이션을 통해 이미 계산된 값을 변경하지 않고 재사용합니다.
(3)함수의 사용:
함수형 프로그래밍: 함수가 일급 객체로 취급되며, 고차 함수와 함수 합성을 통해 복잡한 연산을 수행합니다.
동적 프로그래밍: 문제를 해결하기 위해 재귀적 접근법(메모이제이션)이나 반복적 접근법(타뷸레이션)을 사용합니다.
차이점
(1) 목적:
함수형 프로그래밍: 프로그래밍 스타일이나 패러다임으로, 코드의 가독성, 재사용성, 테스트 용이성을 높이는 것을 목표로 합니다.
동적 프로그래밍: 특정 유형의 문제(주로 최적화 문제)를 효율적으로 해결하기 위한 알고리즘 기법입니다.
(2) 적용 범위:
함수형 프로그래밍: 전체 프로그램의 구조와 설계에 영향을 미칩니다. 함수형 프로그래밍 언어를 사용하거나, 함수형 스타일로 코드를 작성합니다.
동적 프로그래밍: 특정 문제를 해결하는 데 사용되는 알고리즘 기법으로, 프로그램의 일부에만 적용될 수 있습니다.
(3) 상태 관리:
함수형 프로그래밍: 상태 변화를 피하고, 순수 함수와 불변성을 강조합니다.
동적 프로그래밍: 하위 문제의 결과를 저장하는 메모이제이션이나 타뷸레이션 테이블을 사용하여 상태를 관리합니다.
(4) 언어 지원:
함수형 프로그래밍: Haskell, Lisp, Erlang, Scala, F#, Clojure 등 함수형 프로그래밍을 지원하는 언어가 있으며, JavaScript, Python, Java 등에서도 함수형 스타일을 지원합니다.
동적 프로그래밍: 특정 언어에 종속되지 않으며, 다양한 프로그래밍 언어에서 구현할 수 있습니다.
결론
함수형 프로그래밍과 동적 프로그래밍은 서로 다른 목적과 특성을 가진 개념이지만, 재사용성과 불변성 같은 공통된 원칙을 공유할 수 있습니다. 함수형 프로그래밍은 전체 프로그램의 설계와 구조에 영향을 미치는 패러다임인 반면, 동적 프로그래밍은 특정 문제를 효율적으로 해결하기 위한 알고리즘 기법입니다.