알고리즘 설계기법

알고리즘 설계기법 (Algorithm Design Technique)

 

알고리즘 설계 기법은 문제를 해결하기 위한 알고리즘, 해당 문제의 답을 효과적으로 찾아가기 위한 전략과 접근 방식이다. 문제를 풀 때 어떤 알고리즘 설계 기법을 쓰는지에 따라 효율성에서 막대한 차이를 보이기 때문에 특정 문제 유형에 가장 효과적인 해결책을 찾기 위한 접근 방식을 구할 필요가 있다.

 

[이전까지는 C#에서 구현되어 있는 자료구조나 기본 문법들의 사용 방식을 배우고 그것들을 응용하는 것을 배웠다면 이번에 배운 설계 기법은 접근 방식이기 때문에 즉각적으로 적용과 응용이 힘들었고 적용 과정이 매우 난해하게 느껴졌었다.

그렇지만 이것은 알고리즘 설계 기법이 수학적인 원리를 기반으로 하고 있고 수학적 사고와 추론을 필요로 하여 문제 해결에 대한 효율적인 방법을 찾는 과정으로써 결국 나의 수학적인 사고 방식이 약하기 때문에 반복된 연습을 필요로 한다.]

 

[그리디 알고리즘 (탐욕 접근법)]

 

 탐욕 알고리즘은 문제를 해결하는 데 사용되는 근시안적 방법이다. 각 단계에서 가장 최적인 선택을 하며 답을 찾아가는 알고리즘으로 문제를 직면한 당시에 당장 최적인 답을 선택하는 과정을 반복해서 시행한다.

그런데 각 상황에 직면할 때의 최적의 답만을 찾기 때문에 전체 단계를 모두 포함해서 볼 경우 최적의 해를 구해준다는 보장은 없게 된다.

 

대표적인 예시는 거스름돈 줄이기 문제를 들 수 있다.

 

거스름돈을 줄이고자 할 때 최대 크기의 코인부터 밀어넣어 잔액을 줄이는 방법을 사용한다.

매개변수로 주어진 money에 맞춰서 가장 적은 수의 동전을 사용하여 거스름돈을 주고자 할 때의 상황이다.

가장 큰 동전부터 사용하며 최대한 많은 동전을 사용하면 전체적으로 동전의 개수를 최소화 할 수 있다.

 

 

 

[동적 프로그래밍 (동적 계획법)]

 

동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하고  작은 부분 문제들을 한번씩만 풀고 결과를 저장해 재활용함으로써 중복 계산을 피하여 효율적으로 해결하는, 즉 작은 문제의 해답을 큰 문제의 해답의 부분으로 이용하는 상향식 접근 방식이다.

 

코드적으로는 동적 계획법 없이 작성할 경우 재귀적인 방식으로 연속된 계산을 표현할 수 있다.

하지만 재귀적인 방식은 중복 계산이 발생하여 성능적인 문제가 발생할 수 있다. 예시로 든 피보나치 수열의 경우, 특정 값에 대한 계산은 이전 값들의 합으로 이루어지기 때문에 같은 값을 반복적으로 계산하게 된다. 이러한 중복 계산으로 인해 계산 시간은 기하급수적으로 증가하고 연산에 필요한 메모리 또한 기하급수적으로 증가하게 된다.

 

피보나치 수열을 동적계획법으로 작성하였을 때

 

피보나치 수열을 재귀적으로 작성하였을 때

 

 

[분할 정복]

 

분할 정복은 큰 문제를 작은 문제로 나누어 분할하고 각 부분 문제를 해결한 후에 이를 결합하여 전체 문제를 해결하는 하향식 접근 방식이다.

 

동적 계획법과 분할 정복은 둘 다 큰 문제를 작은 문제로 분할하여 해결한다는 점에서 공통점을 갖지만 중요한 차이점이 존재한다.

 

동적 계획법은 이미 해결한 작은 문제들을 한번씩만 풀고 문제들의 해답을 저장하여 필요할 때마다 다시 사용하여 효율성을 높이는 메모이제이션을 사용한다. 또한 큰 문제의 최적해를 작은 부분 문제의 최적해 이용하여 찾을 수 있는 성질을 갖는다. 이러한 특징을 갖기 때문에 동적 계획법은 작은 부분 문제들이 서로 의존성을 가지며 작은 부분 문제를 반복적으로 해결하고 저장하는 것으로 중복 계산을 피한다.

 

반면 분할 정복은 각 부분 문제는 독립적이며 중복되지 않기 때문에 일반적으로 중복되는 부분 문제를 해결하지 않고 문제를 각각 작은 부분으로 나누어 독립적으로 부분 문제들을 해결한다.

이러한 문제들을 해결하기 위해 보통 분할 정복은 재귀적으로 부분 문제들을 해결하고 그 결과들을 결합하여 최종 해결책을 구하는 방식을 갖는다.

 

요약하자면, 동적 계획법은 작은 문제들의 해답을 저장하고 재사용하여 중복 계산을 피하며 답을 찾는 방식이라면, 분할 정복은 문제를 독립적으로 나누고 각각을 해결하여 최종 답을 찾는 방식이다.

 

이러한 분할 정복 방식을 갖는 건 퀵 정렬과 병합 정렬을 예로 들 수 있다.

 

데이터를 2분할하여 정렬 후 합병하는 병합정렬과 하나의 피벗(중심)을 기준으로 작은값과 큰값을 2분할하여 정렬하는 퀵 정렬은 다음에 정렬을 모아 정리해보고자 한다.

 

 

 

[백 트래킹]

백 트래킹이란 모든 경우의 수를 탐색하면서 해답을 찾는 알고리즘이다. 가능한 선택지를 모두 탐색하다가 조건을 만족하지 않으면 이전 단계로 돌아가 다른 선택지를 탐색하는 기법으로 백 트래킹으로 해결할 수 있는 예시로 N개의 퀸 놓기 문제가 있다.

 

고마워요 GPT