코드스테이츠

4/5 일일정리 알고리즘 Greedy,구현,DP

강물둘기 2023. 4. 5. 20:13

Greedy Algorithm

그리디(탐욕) 알고리즘은 선택의 순간에 눈앞의 가장 최적인 상황을 고르면서 해답에 도달하는 방법이다.

그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 없다는 것을 명심해야 한다. 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.

 

Greedy Algorithm 문제 해결 단계

⓵ 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.

⓶ 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.

⓷ 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위 과정을 반복한다.

 

Greedy Algorithm의 특징

그리디 알고리즘은 앞의 선택이 이후의 선택에 영향을 주지 않는다. ( 탐욕적 선택 속성)

그리고 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. (최적 부분 구조)

그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다. 따라서 적당히 괜찮은 방법을 찾을 때 사용할 수 있다. 또한 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수 있다.

 

Greedy Algorithm 예시

대표적인 예시로 잔돈을 거슬러 줄 때 동전의 개수를 최소한으로 건네주는 알고리즘을 작성할 때 사용한다.

출처 : 코드스테이츠

  1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택
  2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사, 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전 선택
  3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사, 액수가 부족하면 1번 과정부터 다시 반복

 

구현(Implementation)

구현이란 머릿속에 있는 알고리즘을 코드로 작성하는것을 의미한다.

구현을 잘 하기 위해서는 프로그래밍 언어의 문법을 정확히 알고있어야 하고 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것이 중요하다. 

알고리즘 구현 문제의 경우 구현을 하기 까다롭게 문제를 만든다. 지문이 길거나, 까다로운 조건이나 상황을 붙이거나, 로직은 쉽지만 굉장히 길게 작성하도록 하는 문제들이 대부분이다. 

알고리즘 구현 문제의 대표적인 사례는 완전 탐색(Brute Force)과 시뮬레이션이 있다.

 

완전 탐색(Brute Force)

완전 탐색 알고리즘은 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 말한다. 이 방법은 비효율적인 방법이지만 '무조건 답을 찾을 수 있다.'라는 강력함을 가지고 있다.

Brute Force 알고리즘

메모리나 시간 제한이 있는 문제에서는 사용할 수 없지만, 제한이 없는 문제에서는 간단한 로직으로 문제를 풀 수 있다.

완전 탐색 알고리즘은 주로 프로세스의 속도를 높이는 다른 알고리즘이 없을 때나 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 사용한다.

 

완전탐색 알고리즘 예시

⓵ 순차 검색 알고리즘

⓶ 문자열 매칭 알고리즘

⓷ 선택 정렬 알고리즘

 

시뮬레이션(Simulation)

시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것처럼 코드를 구현하는 작업을 말한다.

보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결은 쉽지만 로직이 길고 자세하기 때문에 코드로 옮기는 작업이 까다로울 수 있다.

 

시뮬레이션 예시

출처 : 백준 온라인 저지
출처 : 코드스테이츠

 

DP(Dynamic Programming)

DP, 동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 앞에서 구했던 답을 기록해 놓았다가 다시 구하지 않고 재활용하며 사용한다.

 

다이나믹 프로그래밍은 다음과 같은 상황에서 사용할 수 있다.

⓵ 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.

⓶ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

 

DP 알고리즘 문제 예시

피보나치 수열

피보나치 수열의 n번째 수를 출력하는 문제의 경우 그냥 재귀방식이나 반복문으로 풀면 시간복잡도 O(2^n)를 가지게 된다. 

DP를 통하여 이전에 구한 피보나치 수열의 수를 배열 형태로 기억하도록 하는 DP 알고리즘으로 문제를 풀면 시간복잡도 O(n)으로 문제를 최적화하여 풀 수 있다.

function fibMemo(n, memo = []) {
	// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) {
			return memo[n];
		}
    if(n <= 2) {
			return 1;
		}
	// 없다면 재귀로 결괏값을 도출하여 res에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
	// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo에 저장
    memo[n] = res;
    return res;
}

 

Reference

- 코드스테이츠

- 나무위키