Algorithms and Problem Solving with and without division
알고리즘과 문제해결
Contents
1️⃣ 알고리즘을 통한 문제해결 (Problem solving through algorithms)
2️⃣ 분할없이 해결하는 방법 (Solving without division)
3️⃣ 분할을 통해 해결하는 방법 (Solving through division)
1️⃣ 알고리즘을 통한 문제해결
(Problem solving through algorithms)
알고리즘을 통한 문제해결의 절차는 일반적으로 4가지의 과정으로 이루어진다. 위의 스텝을 활용해서 차근차근 문제를 풀게되면 최종적인 결과가 목표치에 어긋나지 않게된다.
숫자의 합 구하기: 문제풀이 _(1) 문제 분석하기
위의 예제는 N개의 숫자의 합을 구하는 알고리즘 문제이다.
문제의 핵심과제: 공백 없이 주어진 N개의 숫자를 모두 더한 값을 출력하는 것.
- 예를 들어,
54321이라는 숫자들이 주어지면, 각각의 자리수를 더해서5 + 4 + 3 + 2 + 1 = 15라는 결과를 구해야 한다.
- 예를 들어,
입력 조건:
- 첫 번째 줄: 숫자의 개수 N이 주어진다. 이는 뒤에서 입력받을 숫자가 몇 자릿수인지 알기 위한 정보이다.
- 두 번째 줄: N개의 숫자가 공백 없이 연속적으로 주어진다. 이 줄에 주어지는 숫자들은 실제로 더해야 하는 대상이다.
출력 조건:
- 주어진 숫자들을 모두 더한 값을 출력해야 한다.
숫자의 합 구하기: 문제풀이 _(2) 손으로 전략 세우기
이 전략은 문제를 푸는 구체적인 과정을 손으로 짜보는 예시로, 알고리즘 문제 해결에서 자주 쓰이는 방법이다. 먼저 문제를 단계별로 나누고, 그 단계를 코드로 구체화하는 과정을 통해 효율적인 해결 방안을 찾는 것이 중요하다.
숫자의 개수만큼 입력 받은 값을 리스트 형태로 저장
예를 들어, 입력으로
"10987654321"이라는 문자열이 주어지면, 이를 리스트로 변환numbers = '10987654321'라고 저장한다. 이때, 리스트에는 각 자리의 숫자가 개별 요소로 들어간다.
numbers 리스트를 탐색하며 각 값을 정수형으로 변환하며 결과값에 더하여 누적다.
리스트에 있는 각 문자형 숫자를 반복문을 사용하여 하나씩 탐색한 후, 이를 정수형으로 변환한다.
변환된 정수형 숫자들을 모두 더해서 최종 합계를 구하게 된다.
설명 및 예제
리스트 저장 및 변환 과정:
문제를 해결하기 위해 입력된 문자열을 하나씩 나눠서 리스트에 저장하는 것은 매우 중요한 단계이다. 이 리스트의 각 요소는 문자열 형태로 저장되며, 이를 숫자형으로 변환하는 과정이 필요하다.
numbers 리스트:
['1', '0', '9', '8', '7', '6', '5', '4', '3', '2', '1']
탐색 및 합산:
리스트의 각 요소를 반복문을 사용해 하나씩 꺼내고, 그 요소를 숫자(정수형)로 변환한 후, 그 값을 누적합에 더해주는 방식이다.
이때 사용되는 기본적인 전략은 문자열로 받아온 숫자를 정수로 변환하는 함수 (
int())와 반복문을 이용한 탐색이다.각 숫자를 차례로 꺼내서 정수로 변환한 후 더해가면, 최종적으로 45라는 값을 얻게 된다.
숫자의 합 구하기: 문제풀이 _(3) 의사코드 작성하기
의사코드는 실제 코드로 변환하기 전에 문제 해결 과정을 쉽게 설명할 수 있도록 작성된 가상의 코드이다. 실제 프로그래밍 언어로 변환하기에 앞서 문제 해결 과정을 시각적으로 정리한 것이며, 간단하고 직관적으로 문제의 흐름을 잡는 데 도움이 된다. 이 과정을 바탕으로 실제 코드로 전환할 수 있게 된다.
의사코드 설명
n값 받기: 첫 번째 입력으로 숫자의 개수 n을 받는다.
numbers 변수를 사용하여 숫자를 리스트로 변환: 입력된 숫자들을 list() 함수를 이용하여 한 자리씩 나누어 리스트로 변환환다.
- 주어진 입력을 공백 없이 연속된 숫자로 받았으므로, 이를 각각의 숫자로 나누어 리스트에 저장해야 합니다.
list()함수를 사용해 이를 쉽게 처리할 수 있다.
sum 변수 선언: 숫자들의 합을 저장할 sum 변수를 0으로 초기화한다.
for 문을 이용하여 numbers 리스트 탐색: numbers 리스트에 있는 각 자리 숫자를 탐색하면서, 각 숫자를 정수형으로 변환하여 sum 변수에 더한다.
- 탐색 및 합산: 리스트에 들어 있는 문자형 숫자들을 하나씩 반복문을 통해 꺼내와서, 이를 정수로 변환한 후
sum에 더해준다.
sum 출력: 최종적으로 계산된 합을 출력합니다.
- 출력: 반복문이 끝난 후, 최종적으로
sum값을 출력하여 숫자들의 합을 구한 결과를 확인한다.
설명
n = input()
- 사용자로부터 숫자의 개수를 입력받는다. 하지만 이 예제에서는 숫자의 개수를 따로 사용하지 않기 때문에
n은 사실상 중요하지 않다.
- 사용자로부터 숫자의 개수를 입력받는다. 하지만 이 예제에서는 숫자의 개수를 따로 사용하지 않기 때문에
numbers = list(input())
공백 없이 입력받은 숫자를
input()함수를 통해 문자열로 받고, 이를list()함수를 사용하여 각 자리 숫자를 하나씩 나누어 리스트로 변환한다.예를 들어,
54321을 입력하면['5', '4', '3', '2', '1']로 변환되게 된다.
sum = 0
- 합계를 저장할 변수를 0으로 초기화한다. 여기서
sum변수는 모든 자리 숫자의 합계를 계산하는 데 사용된다.
- 합계를 저장할 변수를 0으로 초기화한다. 여기서
for i in numbers:
numbers리스트에 있는 각 문자형 숫자를 반복문을 통해 하나씩 꺼내온다.
sum = sum + int(i)
- 꺼내온 문자형 숫자
i를int()함수를 사용하여 정수형으로 변환한 후,sum에 더해줍니다. 이 과정을 리스트에 있는 모든 숫자에 대해 반복한다.
- 꺼내온 문자형 숫자
print(sum)
- 최종적으로 계산된 합계를 출력합니다.
예시 실행:
입력:
5,54321출력:
15- 5 + 4 + 3 + 2 + 1 = 15
2️⃣ 분할없이 해결하는 방법
(Solving without division)
문제 해결에는 여러 가지 방식이 있으며, 이 이미지에서는 크게 두 가지로 나누어 설명하고 있다: 분할 없이 해결하는 방법과 분할을 통해 해결하는 방법이다. 아래에 각 방법에 대한 설명을 살펴보자
1) 문제 해결 방법의 개략적 분류(General Classification of Problem-Solving Methods)
1. 분할 없이 해결하는 방법: 문제를 분할하지 않고, 문제 자체를 바로 해결하는 방법이다. 이 방식은 보통 문제의 전체를 한 번에 다루거나 탐욕적인 방법으로 해결하는데 사용된다. 간단하고 직관적인 접근 방식을 제공하여 단순한 문제 해결 방법이 가능하지만, 효율성 측면에서는 문제의 특성에 따라 더 나은 방법을 선택해야 한다.
원시적 접근법 (Brute Force):
- 가능한 모든 경우의 수를 모두 탐색하여 답을 찾는 방법이다. 가장 단순하고 직관적인 방법이지만, 비효율적일 수 있다. 문제의 크기가 작을 때 적합하다.
탐욕법 (Greedy Algorithm):
- 현재 상황에서 가장 좋은 선택을 반복적으로 수행하여 전체 문제를 해결하는 방법이다. 탐욕법은 그 순간의 최선의 선택이 최종 결과에도 최선이라고 가정한다. 하지만 항상 최적의 해답을 보장하지는 않으며, 그리디 알고리즘이 효과적인 문제에 한해 잘 작동한다.
2. 분할을 통해 해결하는 방법: 문제를 작게 쪼개서 해결하는 방식이다. 중복 계산을 방지하면서 효율적으로 해결하는 방법이다. 복잡하고 대규모 문제를 다룰 때 유리하며, 효율성을 높일 수 있다.
분할정복 (Divide & Conquer):
- 문제를 작은 부분 문제로 나눈 뒤, 각각을 해결하여 합치는 방식이다. 대표적인 예로는 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 큰 문제를 작게 나누어 해결하는 구조라서 문제의 복잡도를 줄이는 데 효과적이다.
동적 계획법 (Dynamic Programming):
중복되는 부분 문제를 해결한 결과를 저장해 두고, 이를 재사용하여 효율성을 극대화하는 방식이다.
문제를 하위 문제로 나누는 것은 분할정복과 유사하지만, 이전에 해결한 결과를 저장해서 같은 문제를 다시 계산하지 않는 것이 차이점이다. 대표적인 예로 피보나치 수열 계산이 있다.
💡분할 없이 해결하는 방법 설명: 원시적 접근법(Brute Force)
개념: 가능한 모든 선택지를 하나씩 시도하여 성공할 때까지 계속하는 방법이다.
전수조사, 무차별 시도, 시행착오(trial & error)와 동일하거나 유사한 개념이다.
영어의 "brute"는 "짐승 같은, 난폭한"이라는 의미로, 시간과 자원을 많이 투자하여 무식하고 비효율적으로 문제를 푸는 방식이라는 뜻이다.
하지만 모든 경우의 수를 다 시도하기 때문에 정답에 접근하는 가장 확실한 방법이 되기도 한다.
명확한 해법이 보이지 않고 n이 큰값이 아닌 알고리즘 계획시엔 원시적 접근법으로 요긴하게 해결할 수 있는 방법중 하나이다.
특징:
- 병렬 작업 가능(Parallel processing possible): 여러 대의 컴퓨터를 연결해 동시에 작업을 수행하여 시간을 줄일 수 있다.
매우 높은 복잡도(Very high complexity)
전수조사를 하므로 입력에 따라 복잡도가 기하급수적으로 증가하는 단점이 있다.
문제의 크기가 커지면 컴퓨팅 자원을 매우 많이 소비하게 된다. 심한 경우엔 몇일 몇달이 걸려도 해결이 안될 수 있다.
효율적인 알고리즘을 개발하기 전에 작은 문제에 대해 정답을 구할 때 유용할 수 있다.
사례:
4자리 숫자로 된 핸드폰의 암호를 알아내는 방법:
4자리 암호는 0000부터 9999까지 총 10^4(10,000)개의 조합 중 하나이다.
가능한 모든 조합을 하나씩 대입해 보면 언젠가는 핸드폰의 암호를 알아낼 수 있게된다.
시간이 충분이 있다면 만번의 시도는 해볼만 하다고 할 수있다.
알고리즘 설명: 반복문을 사용해 0000부터 9999까지의 모든 조합을 대입해보는 과정을 통해 핸드폰 암호를 알아내는 방식이다.
복잡도: 자리수가 n일 경우, 복잡도는 O(10^n), 문자의 개수가 m일 경우 O(m^n)의 복잡도를 가집니다. (비밀번호가 6자리일경우 복잡도는 10^6이다. 비밀번호 자리수가 커질수록 무차별 대입을 하기엔 엄청난 시간이 필요하므로 요즘 비밀번호 설정은 특수문자, 대문자, 자리수 증가 등 섞어서 하는 이유도 여기에 있다.)
💡분할 없이 해결하는 방법 설명: 탐욕법(Greedy algorithm)
개념: 현재 상태에서 가능한 선택지 중 최상의 선택을 선택해 나가는 알고리즘이다.
즉, 각 단계에서 가장 좋은 선택을 하면서 문제를 해결해 나가는 방식이다.
주의점: 현재 부분의 최적해가 전체의 최적해가 아닐 수 있다는 점이다. 이는 탐욕법의 한계라고 할 수 있다. (아래 사진 참조)
위 그림은 탐욕법의 한계를 보여주는 예시이다.
탐욕법은 각 단계에서 최선의 선택을 하지만, 그 선택들이 전체 최적의 결과를 보장하지 않는 경우가 있을 수 있다. 위 예시에서는 탐욕법이 찾은 경로(오렌지색)가 전체 최적 경로(녹색 경로)가 아님을 보여주고 있다.
그림 설명:
출발 지점에서 도착 지점까지 가는 경로를 찾는 문제:
탐욕법은 현재 상황에서 가장 좋은 선택을 반복적으로 하여 최적의 경로를 찾는다
예시에서 탐욕법의 선택은
출발 -> b -> d -> 도착의 경로(오렌지색)입니다. 이 경로의 총 거리는 1 + 5 + 20 = 26이다.그러나 전체 최적 경로는
출발 -> a -> 도착(녹색 경로)로, 이 경로의 총 거리는 5 + 2 = 7이다.현재 상황에서 제일 좋은 선택은 1 vs 5에서 1이므로 이 경로를 선택하였지만 결과적으로는 5가 더 나은 선택이었다는 걸 알수있다.
탐욕법의 특징
장점:
단순한 구현: 탐욕법은 비교적 간단하게 구현할 수 있다.
매우 빠른 시간복잡도: 각 단계에서 최적의 선택을 하므로 계산이 빠르다.
단점:
- 부분 최적해가 전체 최적해가 아닐 수 있다. 탐욕법이 항상 최적의 해를 보장하지 않는다는 단점이 있다.
단점을 보완하기위해 탐욕법이 최적해를 보장하는 조건을 체크해보아야 한다.
탐욕 선택 조건(Greedy choice property): 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다.
최적 부분 구조(Optimal substructure): 부분 문제의 최적 결과가 곧 전체 문제의 최적 결과로 일치 되는 구조이어야 한다.
탐욕법 - 최적 부분 구조의 예시
최종 해결:
부분 문제 1과 부분 문제 2의 최단 경로를 합치면 전체 문제의 최단 경로가 된다.
따라서, 서울에서 대구까지 200km + 대구에서 부산까지 80km = 280km로 최종 경로를 구할 수 있다.
이 예시는 탐욕법이 잘 작동하는 상황을 보여준다. 부분 문제의 최적해를 합쳤을 때 전체 문제의 최적해가 되는 구조를 갖고 있기 때문에, 탐욕법이 문제 해결에 적합하다. 이는 탐욕법이 최적 부분 구조를 가질 때 전체 문제의 최적해를 구할 수 있음을 설명하는 좋은 예시이다.
탐욕법이 항상 최적해를 보장하지는 않지만, 이러한 최적 부분 구조가 있는 경우에는 전체 최적해를 빠르게 구할 수 있다.
💡분할을 통해 해결하는 방법 - 분할정복 (Divide & conquer)
개념
- 전체 문제를 더 작은 하위 문제들로 나누어 각각을 해결하고, 그 결과들을 결합하여 전체 문제를 해결하는 방법이다. 즉, 큰 문제를 작게 쪼개서 해결하는 방식으로, 효율적이고 문제의 복잡도를 줄일 수 있다.
그림설명
- 위의 그림은 분할정복(Divide & Conquer) 알고리즘의 전형적인 문제 해결 과정을 시각적으로 표현한 트리 구조이다. 먼저 작은 하위 문제들로 분할하고, 그 문제들을 독립적으로 해결한 후, 마지막에 그 결과들을 조합하여 전체 문제를 해결하는 방식이다. 트리 구조는 문제 분할, 해결, 그리고 결과 조합의 흐름을 시각적으로 명확히 보여주며, 각 단계가 어떻게 전체 문제 해결에 기여하는지 알 수 있다. 대표적인 예로는 병합 정렬(Merge Sort)와 퀵 정렬(Quick Sort) 같은 알고리즘이 이러한 방식으로 동작한다.
분할정복의 과정
문제 Problem (루트 노드): 시작점은 "문제"로, 전체 문제가 하나의 단위로 시작된다. 분할정복의 첫 단계는 이 문제를 더 작은 하위 문제(Lower-level problem)들로 나누는 과정이다.
분할 Divide : 문제는 첫 번째로 여러 "부분 문제 (Subproblem) "로 분할다. 이 부분 문제들도 다시 작은 단위로 나눌 수 있다면, 또다시 분할 과정을 거친다.
- 이 과정이 반복되며, 각 하위 문제가 더 작은 단위로 나누어진다. 트리 구조에서 위에서 아래로 확장되는 모습이 이 과정을 나타낸다.
정복 Conquer (하위 문제 해결): 가장 작은 단위까지 분할된 후에는, 각 하위 문제를 해결하는 과정이다. 그림에서는 "부분 문제 해결법 (Solution to the subproblem)"으로 표시된 노드들이 이러한 해결 단계들을 나타낸다. 각 하위 문제를 독립적으로 해결하고, 그 결과를 저장한다.
조합 Combine : 해결된 각 부분 문제들의 결과를 다시 조합하여 상위 문제의 해결법을 도출한다. 트리 구조의 아래쪽에서 위쪽으로 올라가는 과정에서 각 하위 문제의 해결 결과가 모여 최종 해결로 이어지게 된다. 이 단계에서 여러 해결된 하위 문제들이 모여서 최종적으로 원래의 문제를 해결할 수 있게 된다.
분할정복의 특징
💡분할정복 장단점 요약: 분할정복 알고리즘은 복잡한 문제를 작은 단위로 나누어 해결하는 강력한 방법론이지만, 그 과정에서 재귀 호출 오버헤드와 스택 메모리 사용에 대한 문제가 발생할 수 있다. 이를 보완하기 위해 반복적 접근(Iterative approach)이나 메모이제이션 기법을 사용하는 것도 좋은 방법이다.
분할정복의 장점
복잡한 문제를 소문제로 분할하여 해결 가능
분할정복의 가장 큰 장점은 큰 문제를 다루기 쉽다는 점이다. 복잡한 문제를 작은 문제들로 나누면, 각 작은 문제를 독립적으로 해결할 수 있게된다. 각 하위 문제의 해결법이 비교적 간단해질 수 있기 때문에, 대규모 문제도 점진적으로 해결할 수 있게된다.
예를 들어, 정렬 문제에서 병합 정렬(Merge Sort)을 사용하면 배열을 반으로 나누고, 각 부분을 정렬한 뒤 다시 병합하여 전체 배열을 정렬하는 방식으로 접근한다. 이 방식은 큰 문제를 작은 문제로 나누어 처리함으로써 문제의 작업시간을 효율적으로 줄일 수 있게된다.
병렬적으로 알고리즘을 수행하여 작업 시간을 줄일 수 있음
분할된 하위 문제들은 서로 독립적이기 때문에 병렬적으로 처리할 수 있다. 각 하위 문제를 서로 다른 프로세서나 쓰레드에서 동시에 실행하면 작업 시간을 크게 단축할 수 있다. 이 점은 현대의 멀티코어 프로세서 환경에서 매우 큰 장점으로 작용한다.
예를 들어, 이미지 처리와 같은 분야에서는 분할정복을 통해 이미지를 여러 부분으로 나누고, 각각의 부분을 독립적으로 처리한 후 병합하는 방식을 사용한다. 이렇게 하면 작업을 동시에 여러 프로세서에서 처리할 수 있어 전체 작업 시간이 짧아지게된다.
분할정복의 단점
재귀적으로 함수를 호출하여 함수 호출 오버헤드 발생:
분할정복 알고리즘은 재귀적으로 문제를 해결한다. 즉, 문제를 나누고 나눌 때마다 재귀적으로 함수를 호출하여 처리한다. 하지만 재귀 호출에는 호출 스택을 관리하는 오버헤드가 발생하게 된다. 이로 인해 재귀 호출이 매우 깊어지면 성능에 영향을 미칠 수 있다.
예를 들어, 피보나치 수를 재귀적으로 계산하는 경우, 재귀 호출이 많아질수록 중복된 계산이 많아지고, 호출 스택이 쌓이면서 성능 저하가 발생할 수 있다다. 이를 해결하기 위해 동적 계획법(Dynamic Programming)이나 메모이제이션(Memoization)을 사용하는 경우가 많다.
함수 스택이 깊게 쌓여 과도한 메모리 사용 가능:
분할정복은 재귀적으로 문제를 해결하므로 재귀 호출이 반복될 때마다 함수 스택이 깊게 쌓이게 된다. 이로 인해 메모리를 과도하게 사용할 가능성이 있다. 특히, 매우 큰 입력이 주어질 때는 스택 오버플로우(stack overflow)가 발생할 수 있다.
예를 들어, 퀵 정렬(Quick Sort)에서 매우 편향된 분할이 이루어지면 (즉, 피벗이 항상 한쪽 끝에만 위치할 때), 재귀 호출이 불균형하게 이루어져 함수 호출 스택이 깊어질 수 있다. 이를 방지하기 위해서는 균형 잡힌 분할을 유도하거나 재귀 깊이를 제한하는 방법을 사용할 수 있다.
분할정복의 사례: 병합 정렬(Merge Sort)
병합 정렬은 배열을 두 부분으로 나누어 각각을 정렬한 뒤, 다시 병합하는 방식으로 전체 배열을 정렬하는 알고리즘이다.
병합 정렬(Merge Sort)의 핵심 과정:
배열 분할(Array division)
p < r인 경우 배열을 두 부분으로 나누어야 한다. 이때 중간 지점q를 계산하여 배열을A[p..q]와A[q+1..r]로 분할한다.q = (p + r) / 2로 계산하여 배열을 절반으로 나눈다.
전반부 정렬(Sorting the first half)
mergeSort(A, p, q)를 호출하여 배열의 전반부A[p..q]를 정렬한다.이 과정은 다시
p < q일 경우, 분할 및 병합을 재귀적으로 반복한다.
후반부 정렬(Sorting the second half)
mergeSort(A, q+1, r)를 호출하여 배열의 후반부A[q+1..r]를 정렬한다.이 과정 역시 전반부와 동일하게 재귀적으로 정렬한다.
병합(Merge)
두 부분으로 나누어진 배열이 각각 정렬된 후,
merge(A, p, q, r)를 통해 두 배열을 병합한다.이 단계에서 각각 정렬된 두 배열을 하나의 배열로 합쳐서 최종적으로 정렬된 하나의 배열을 만들게 된다.
추가 설명:
병합 과정: 병합 단계에서는 두 개의 정렬된 배열을 병합하는데, 각각의 배열에서 가장 작은 값을 비교하여 작은 값을 먼저 새로운 배열에 넣는 방식으로 진행된다.
재귀적 호출: 병합 정렬은 재귀적으로 배열을 나누고 병합하는 과정이다. 각 하위 배열이 더 이상 나눌 수 없을 정도로 작아지면(원소가 1개일 때), 병합을 시작한다.
병합 정렬의 시간 복잡도는 항상 O(n log n)으로, 안정적인 정렬 알고리즘 중 하나이다. 배열을 절반으로 나누는 데 O(log n), 병합하는 데 O(n)이 소요되기 때문이다..
이 알고리즘은 큰 데이터를 다룰 때 효율적이며, 분할정복의 전형적인 구조를 잘 보여주고 있다.
텍스트 설명과 의사코드(pseudocode)는 서로 다른 방식으로 정보를 전달하기 때문에, 처음에는 의사코드가 복잡하게 느껴질 수 있다. 텍스트 설명과 의사코드를 연결해 보면서 반복적으로 연습하다 보면 자연스럽게 익숙해질 것이다.
💡분할을 통해 해결하는 방법 - 동적계획법(Dynamic programming)
개념: 전체 문제를 작은 하위 문제로 분할한 후, 그 하위 문제들의 해답을 저장하여 나중에 상위 문제의 해답에 재활용하는 알고리즘이다. 즉, 한 번 계산한 문제의 결과를 다시 계산하지 않고 재활용하는 방식이다.
동적 계획법의 원리와 구현 방식:
큰 문제를 작은 문제로 분할이 가능해야 함
(The large problem must be divisible into smaller problems.)- 동적 계획법은 문제를 작은 하위 문제로 나누는 방식이므로, 문제를 적절히 쪼개서 해결할 수 있어야 한다.
작은 문제들이 반복되고 작은 문제의 해법은 항상 같아야 함
(The smaller problems must recur, and the solution to the smaller problem must always be the same.)- 하위 문제가 여러 번 등장하고, 각 하위 문제에 대한 해답이 동일해야 동적 계획법이 효과적이다.
메모이제이션 (Memoization):
- 계산된 하위 문제들의 결과는 저장되어 재사용된다. 이를 메모이제이션이라고 한다. 이를 통해 중복 계산을 피하고, 효율성을 극대화한다. 계산된 값들은 메모리나 DP 테이블에 저장된다.
Top-down 방식과 Bottom-up 방식으로 구현 가능
(It can be implemented using both top-down and bottom-up approaches.)Top-down 방식은 재귀적 호출을 통해 큰 문제를 해결하며, 하위 문제의 결과를 저장해가며 해결한다.
Bottom-up 방식은 작은 문제부터 차근차근 해결하며, 큰 문제를 해결하는 방식이다. 테이블을 채워나가면서 최종 해답을 얻는 방식이다.
동적 계획법의 적용 절차:
동적 계획법은 중복 계산을 피하고 효율성을 높이는 데 매우 유용한 알고리즘으로, 이 절차를 거쳐야 제대로 적용할 수 있게되는데 간략히 설명하면 DP 조건을 확인하고, 그 문제에 맞는 점화식을 세운 후, 그 점화식을 기반으로 문제를 해결하면서 메모이제이션을 통해 효율성을 극대화하는 것이 핵심이다.
DP 조건 확인:
동적 계획법을 적용할 수 있는 조건이 맞는지 확인하는 단계이다.
DP가 적용되기 위해서는 문제가 반복되는 하위 문제로 나눌 수 있어야 하며, 각 하위 문제의 해법이 항상 동일해야 한다.
점화식 세우기(Establishing a recurrence relation)
상위 문제와 하위 문제를 연결하는 점화식을 표현하는 단계이다.
점화식은 문제의 구조를 파악하고, 큰 문제를 작은 문제로 나누는 방법을 수학적으로 표현한 것이다. 예를 들어, 피보나치 수열의 점화식은
F(n) = F(n-1) + F(n-2)와 같이 정의할 수 있다.
메모이제이션 적용:
하위 문제의 해답을 DP 테이블에 저장하고 재활용하는 단계이다.
중복되는 계산을 피하기 위해 한 번 계산한 하위 문제의 결과를 메모리에 저장하여, 이후에는 다시 계산하지 않고 그 값을 가져다 쓴다.
동적계획법의 사례
피보나치 수열은 동적 계획법을 적용할 수 있는 대표적인 문제이다. 이 예시는 Top-down 방식과 메모이제이션을 활용한 효율적인 피보나치 수열 계산을 비교하고 있다. 이를 통해 동적 계획법의 메모이제이션이 어떻게 문제 해결의 효율성을 크게 향상시키는지 잘 보여주고 있다.
간단히 요약하면 Top-down 방식(좌측)에서는 피보나치 수를 계산할 때 중복 계산이 발생하여 성능이 저하된다. 메모이제이션 방식(우측)을 사용하면, 한 번 계산된 값은 저장하고 이를 재활용하여 중복 계산을 피할 수 있게된다.
피보나치 수열의 점화식:
- D[N] = D[N-1] + D[N-2]: 피보나치 수열은 이전 두 항의 합으로 다음 항을 계산하는 구조이다. 이 점화식을 바탕으로 동적 계획법을 적용할 수 있다.
좌측 (Top-down 방식 / DFS 방식):
트리 구조: 재귀 호출을 통해 피보나치 수를 계산할 때, 각 함수 호출이 다시 또 다른 함수를 호출하는 방식이다.
중복 계산: 이 방식은 중복 계산이 발생하여 비효율적이다. 예를 들어,
F(3)를 두 번 이상 계산하는 등 같은 계산을 여러 번 반복하는 문제가 생다.
우측 (메모이제이션 방식):
저장 및 재사용: 동적 계획법을 적용하여, 한 번 계산한 값은 DP 테이블에 저장된다. 저장된 값이 있다면 그 값을 바로 가져와서 사용한다.
효율성 증가: 중복 계산을 피하고, 이전에 계산한 값을 바로 반환함으로써 연산량을 크게 줄일 수 있다. 이는 메모이제이션의 핵심 원리로, 피보나치 수열을 훨씬 빠르게 계산할 수 있게 된다.
동적계획법(Dynamic Programming)과 분할정복(Divide & conquer)의 차이점
두 알고리즘 모두 문제를 작은 하위 문제로 나누어 해결하는 방식이지만, 문제 해결 과정에서 차이점이 존재한다. 이 차이를 이해하면, 문제의 특성에 따라 어떤 알고리즘을 선택해야 할지 더 명확해지게 된다.
요약해서 설명하면 분할정복은 하위 문제 간 중복이 거의 없는 경우 적합하다. 동적 계획법은 하위 문제들이 중복되어 여러 번 계산될 가능성이 있을 때 유리하다.
차이점 요약:
분할정복: 하위 문제로 분할하지만, 하위 문제의 결과를 저장하지 않아 중복 계산이 발생할 수 있다.
동적 계획법: 하위 문제의 결과를 저장하고 이를 재활용하여 중복 계산을 피한다.
분할정복 (Divide & Conquer):
특징: 문제를 하위 문제로 분할하여 각 하위 문제를 독립적으로 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방식이다.
중복 계산: 하위 문제들이 중복되더라도, 그 결과가 저장되지 않기 때문에 중복된 계산이 반복될 수 있습니다. 즉, 재활용이 되지 않는다.
예시: 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)과 같은 알고리즘이 대표적이다. 동일한 하위 문제들이 여러 번 호출되더라도 그 결과는 저장되지 않는다.
동적 계획법 (Dynamic Programming)
특징: 문제를 작은 하위 문제로 나누고, 한 번 계산한 하위 문제의 해답을 저장하여 필요할 때 재활용한다. 이 과정을 통해 중복 계산을 피하고 효율성을 극대화할 수 있다.
메모이제이션: 계산된 하위 문제의 결과를 메모리에 저장하여, 나중에 동일한 하위 문제가 다시 필요할 경우 저장된 값을 바로 사용한다.
예시: 피보나치 수열에서 동적 계획법을 적용하면, 중복된 계산 없이 빠르게 해결할 수 있다.
학습퀴즈
학습정리
