알고리즘 설계 기법

알고리즘 설계 기법은 문제를 어떤 차례와 기준으로 쪼개고 고를지 정한 풀이의 틀입니다. 탐욕 알고리즘(greedy algorithm)은 그 순간 가장 좋아 보이는 것을 고르고, 동적 계획법(dynamic programming)은 작은 문제의 답을 표에 적어 두고 다시 쓰며, 분할 정복(divide and conquer)은 나눠 풀고 합치고, 백트래킹(backtracking)은 가 보다 막히면 되돌아옵니다. 같은 문제도 어떤 틀로 푸느냐에 따라 답이 맞는지와 걸리는 단계가 달라집니다. 아래 그림은 거스름돈을 큰 동전부터 고르는 모습과, 그 방법이 틀리는 동전에서 표를 앞부터 채워 맞는 답을 내는 모습을 보여 줍니다.

1탐욕 알고리즘 — 지금 가장 좋아 보이는 것을 고른다

탐욕 알고리즘은 단계마다 그 자리에서 가장 좋아 보이는 것을 고르고, 고른 것을 다시 무르지 않습니다. 760원을 500·100·50·10원 동전으로 거슬러 줄 때 가장 큰 동전부터 고르면 500원 1개, 100원 2개, 50원 1개, 10원 1개로 모두 5개입니다. 동전마다 개수는 남은 돈을 동전 값으로 나눈 몫이고, 남는 돈은 나머지입니다.

이 동전들에서는 탐욕이 가장 적은 개수를 내지만, 동전이 달라지면 틀릴 수 있습니다. 1·3·4원 동전으로 6원을 만들면 탐욕은 4원을 먼저 골라 4 + 1 + 1로 3개를 내는데, 3 + 3이면 2개입니다. 자료에 따라 그리디 알고리즘이라고도 부릅니다.

2동적 계획법 — 작은 답을 표에 적어 다시 쓴다

동적 계획법은 큰 문제를 겹치는 작은 문제로 나누고, 작은 문제의 답을 표에 적어 두었다가 꺼내 씁니다. 같은 계산을 되풀이하지 않는 것이 핵심입니다. 1·3·4원 동전으로 0원부터 6원까지 가장 적은 동전 수를 앞에서부터 채우면, n원 칸은 n − 1원·n − 3원·n − 4원 칸 가운데 가장 작은 값에 1을 더한 값입니다.

6원은 3원 칸의 1개에 3원 동전 하나를 더해 2개입니다. 피보나치 수 F(n) = F(n − 1) + F(n − 2)도 표를 앞에서부터 채우면 덧셈을 n번 남짓 하고 끝나지만, 재귀로 그대로 부르면 F(7) 하나에 함수를 41번 부릅니다. 자료에 따라 동적 프로그래밍이라고도 부릅니다.

3분할 정복과 백트래킹

분할 정복은 문제를 같은 꼴의 작은 문제로 나눠 각각 풀고 그 답을 합칩니다. 퀵·병합·힙 정렬의 퀵 정렬과 병합 정렬, 이진 탐색과 해싱의 이진 탐색이 이 방식입니다. 나눈 작은 문제끼리 겹치지 않아 표에 적어 둘 일이 없다는 점이 동적 계획법과 다릅니다.

백트래킹은 답이 될 수 있는 길을 하나씩 따라가다, 조건에 어긋나는 순간 바로 앞 갈림길로 되돌아가 다른 길을 고릅니다. 미로에서 막다른 길을 만나 돌아 나오는 것과 같고, 체스 판에 퀸 여럿을 서로 공격하지 않게 놓는 N-Queen 문제가 대표적인 예입니다.

예제

실기에는 동전 개수를 세는 코드가 나옵니다. 다음 Java 코드는 2760원을 몇 개의 동전으로 거슬러 줄까요? Java 문법은 33단원에서 배웁니다. 여기서는 C와 같은 꼴의 반복과 /·%만 따라가면 됩니다. main 머리는 폰 화면에 맞추려고 두 줄로 썼고, 한 줄로 쓴 것과 같습니다.

public class Main {
  public static void main(
      String[] args) {
    int[] coin =
        {500, 100, 50, 10};
    int m = 2760, cnt = 0, i;
    for (i = 0; i < 4; i++) {
      cnt += m / coin[i];
      m %= coin[i];
    }
    System.out.println(cnt);
  }
}

9

• 반복이 큰 동전부터 돕니다. m / coin[i]가 그 동전의 개수(몫)이고, m %= coin[i]가 남은 돈(나머지)입니다.
• 500원 5개로 260원, 100원 2개로 60원, 50원 1개로 10원이 남고, 10원 1개로 끝나 5 + 2 + 1 + 1 = 9입니다.

시험 포인트

• 필기(시험에서는 1과목): 설명이나 예를 주고 기법 이름을 고르게 합니다 — 나눠 풀고 합치면 분할 정복, 작은 답을 표에 적어 다시 쓰면 동적 계획법, 지금 가장 좋아 보이는 것을 고르면 탐욕 알고리즘, 막히면 되돌아가면 백트래킹입니다. 설계 기법이 아닌 이름을 섞어 놓고 고르게도 합니다. 탐욕 알고리즘이 언제나 가장 좋은 답을 낸다는 보기는 틀립니다.
• 실기: 동전 개수를 세는 코드의 결과를 씁니다 — 몫(/)으로 개수를, 나머지(%)로 남은 돈을 셉니다. 이름은 한글 이름과 영문으로 씁니다 — 분할 정복(Divide and Conquer), 동적 계획법(Dynamic Programming), 탐욕 알고리즘(Greedy Algorithm), 백트래킹(Backtracking).

확인 문제

1. 동적 계획법으로 푸는 모습을 고르세요.

• ① 정렬된 명단을 반으로 나눠, 찾는 이름이 있는 쪽만 다시 반으로 나누기를 되풀이합니다.
• ② 계단을 한 번에 1칸이나 2칸씩 오를 때 n칸을 오르는 방법의 수를, 1칸·2칸의 답부터 표에 적고 앞 두 칸의 답을 더해 구합니다.
• ③ 여러 곳을 돌 때 매번 지금 자리에서 가장 가까운 곳으로 갑니다.
• ④ 스도쿠 빈칸에 숫자를 넣어 가다 규칙이 깨지면 바로 앞 칸으로 돌아가 다른 숫자를 넣습니다.

2. (가)~(라)에 맞는 기법 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 큰 그림 퍼즐을 네 판으로 나눠 따로 맞춘 뒤, 맞춘 판 넷을 이어 붙입니다.
• (나) 1원부터 n원까지 만들 수 있는 가장 적은 동전 수를 칸마다 적어 두고, 다음 금액을 셀 때 적어 둔 칸을 꺼내 씁니다.
• (다) 배낭에 물건을 넣을 때마다 무게에 견줘 값이 가장 큰 것부터 넣고, 한 번 넣은 물건은 빼지 않습니다.
• (라) 미로의 갈림길마다 한 길을 골라 가다가, 막다른 곳에 닿으면 바로 앞 갈림길로 돌아가 다른 길을 고릅니다.

3. 예제 코드의 동전 배열을 {10, 50, 100, 500}으로 바꾸면 무엇이 찍힐까요? 답을 끝까지 쓴 뒤 정답을 펼치세요.