홈 Algorithm 20장 - 알고리즘 유형
포스트
취소

Algorithm 20장 - 알고리즘 유형

게시 2023/04/05
By 최기랑
33 분읽는 시간

Algorithm

Greedy algorithm

  • 탐욕 알고리즘은 말 그대로 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아 해답에 도달하는 방법이다.
  • 문제 해결을 위한 3가지 단계로 나뉜다.
    • 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
    • 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
    • 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

image

  • 탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일합니다. 거스름돈 960원을 채우기 위해서 먼저, 500원짜리 동전을 한 개 선택합니다. 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택할 겁니다. 김코딩의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 단계적으로 구분할 수 있습니다.

  • 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
  • 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
  • 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.
  • 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.

예시

🥖$3 40g🍞$1.5 25g🥯$2.5 5g🥐 $2 20g
 1달러당 무게(반올림)
🥖13.3g
🍞16.7g
🥯2g
🥐10g
  • 장발장이 빵 가게에서 빵을 훔치려고 합니다.
  • 장발장의 가방은 35g까지의 빵만 담을 수 있고, 빵은 가격이 전부 다르며, 4개의 종류가 각 1개씩 있습니다.
  • 빵은 쪼개어 담을 수 있습니다.
  • 장발장은 최대한 가격이 많이 나가는 빵으로만 채우고 싶습니다.

장발장이 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해집니다.

  1. 가방에 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣습니다.
  2. 그다음으로 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣습니다.
  3. 만약, 가방에 다 들어가지 않는다면 쪼개어 넣습니다.
  • $1당 2g인 🥯 3번 빵(5g) 먼저 가방에 담을 수 있습니다: [남은 가방의 무게: 30g]
  • $1당 10g인 🥐 4번 빵(20g)을 다음으로 담을 수 있습니다: [남은 가방의 무게: 10g]
  • $1당 13.3g인 🥖1번 빵(40g)을 다음으로 담을 수 있습니다.

  • 그러나, 40g을 온전히 못 채우기 때문에 쪼개어, 10g만 넣습니다: [남은 가방의 무게: 0g]

  • 탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.
  • 만약 “빵을 쪼갤 수 없는 상황”이라면 마시멜로 실험 결과처럼 Greedy는 최적의 결과를 보장할 수 없다.
  • 무게 대비 가장 비싼 물건을 넣는다는 조건을 두고 현재에 최선을 다하게 되면 빈 자리 5g이 남게 되고 결과를 도출하게 되지만, 빈 자리 5g을 채워 더 큰 최댓값을 만들 수 있는 최선의 상황이 있을 수도 있기 때문이다.

  • 따라서 탐욕 알고리즘을 적용하려면 2가지 조건을 성립하여야 한다.

  • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
  • 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
  • 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

알고리즘 구현의 기초

완전 탐색

  • 모든 문제는 완전 탐색으로 풀 수 있다.
  • 이 방법은 굉장히 단순하고 무식하지만 “답이 무조건 있다”는 강력함이 있다.
  • 문제 해결에는 두 가지 규칙이 붙는다.
    • 첫 번째, 문제를 해결할 수 있는가
    • 두 번째, 효율적으로 동작하는가
  • 완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만, 두 번째 규칙은 만족할 수 없는 경우가 있다.
1
2

양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾으시오.
단, 시간 복잡도가 O(N)보다 낮아야 합니다.
  • 이러한 문제가 나왔을 때, 최악의 경우 100번을 시도해야 하는 완전 탐색은 두 번째 규칙을 만족할 수 없다.
  • 배열을 작은 수에서 큰 수, 혹은 그 반대로 정렬한 후 이분 탐색을 사용하는 방법 등 다른 알고리즘을 사용해야 한다.
  • 그렇기 때문에, 완전 탐색은 문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 완전 탐색밖에 없다고 판단될 때 적용할 수 있다.
  • 완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다.
  • 완전히 탐색하는 방법에는 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.

Brute Force

1
2
3
4
5
6
7
8
9

우리 집에는 세 명의 아이들이 있습니다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다. 먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고, 좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다. 세 아이의 식성은 이렇습니다.

첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)

둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)

셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)

100개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.)
  • 이 문제의 경우 100개의 반찬을 첫째,둘째,셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다.
  • 문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 간결한 코드를 위한 문법을 사용한다고 하더라도 배열을 전부 탐색하여 세 명의 값을 도출한다는 것엔 변함이 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

for(let i = 0; i < 100; i++) {
  if(첫째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(둘째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(셋째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
}

return 많이 먹은 아이;

시물레이션

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

무엇을 위한 조직인지는 모르겠지만, 비밀스러운 비밀 조직 '시크릿 에이전시'는 소통의 흔적을 남기지 않기 위해 3일에 한 번씩 사라지는 메신저 앱을 사용했습니다. 그러나 내부 스파이의 대화 유출로 인해 대화할 때 조건을 여러 개 붙이기로 했습니다. 해당 조건은 이렇습니다.

1. 캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분합니다.
2. 소속은 'true', 'false', 'null' 중 하나입니다.
3. 소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿉니다.
4. 아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더합니다.
5. 캐릭터와 대화 내용을 구분할 땐 공백:공백으로 구분합니다: ['Blue', 'Green', 'null'] : hello.
6. 띄어쓰기 포함, 대화 내용이 10글자가 넘을 때, 내용에 .,-+ 이 있다면 삭제합니다.
7. 띄어쓰기 포함, 대화 내용이 10글자가 넘지 않을 때, 내용에 .,-+@#$%^&*?! 이 있다면 삭제합니다.
8. 띄어쓰기를 기준으로 문자열을 반전합니다: 'abc' -> 'cba'
9. 띄어쓰기를 기준으로 소문자와 대문자를 반전합니다: 'Abc' -> 'aBC'

시크릿 에이전시의 바뀌기 전 대화를 받아, 해당 조건들을 전부 수렴하여 수정한 대화를 객체에 키와 값으로 담아 반환하세요. 같은 캐릭터가 두 번 말했다면, 공백을 한 칸 둔 채로 대화 내용에 추가되어야 합니다. 대화는 문자열로 제공되며, 하이픈- 으로 구분됩니다.

문자열은 전부 싱글 쿼터로 제공되며, 전체를 감싸는 문자열은 더블 쿼터로 제공됩니다.

예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"
  • "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'" 입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분합니다.
    • 첫 번째 파싱은 - 을 기준으로 ['Blue', 'Green', 'null'] : 'hello. im G.', ['Black', 'red', 'true']: '? what? who are you?' 두 부분으로 나눕니다.
    • 두 번째 파싱은 : 을 기준으로 [‘Blue’, ‘Green’, ‘null’] 배열과 ‘hello. im G.’ 문자열로 나눕니다.
  • 배열과 문자열을 사용해, 조건에 맞게 변형합니다.
    • 소속이 셋 중 하나인지 판별합니다.
    • ['Blue', 'Green', 'null'] 아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더합니다: [1, 2, 'null']
    • 'hello. im G.' 10 글자가 넘기 때문에, .,-+@#$%^&* 를 삭제합니다: 'hello im G'
    • 'hello im G' 띄어쓰기를 기준으로 문자열을 반전합니다: 'olleh mi G'
    • 'olleh mi G' 소문자와 대문자를 반전합니다: 'OLLEH MI g'
  • 변형한 배열과 문자열을 키와 값으로 받아 객체에 넣습니다.
    • { "[1, 2, 'null']": 'OLLEH MI g' }

DP(Dynamic Programming)

  • 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해답을 찾는다.
  • 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다.
  • 하위 문제를 계산한 뒤 해결책을 저장하고, 나중에 동일한 하위 문제를 만났을 때 저장된 해결책을 적용해 계산 횟수를 줄인다.
  • 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.
  • 다이나믹 프로그래밍은 두 가지 가정이 만족해야 한다.
    • Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
    • Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

Overlapping Sub-problems

큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 합니다.

  • 대표적인 예시로 피보나치 수열을 들 수 있다.
  • 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.
1
2
3
4
5
6
7

function fib(n) {
  if (n <= 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

image

1
2
3
4

fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...

Optimal Substructure

image

  • 이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다.
  • 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다.
  • 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.
1
2
3
4
5

A → D로 가는 최단 경로 : A → B → C → D

A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)

A → B로 가는 최단 경로 : A → B

예제

Greedy Algorithm - 거스름돈
1
2
3
4
5
6
7

타로는 자주 JOI 잡화점에서 물건을 산다. JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

예제 1
입력 : 380 / 출력 : 4

예제 2
입력 : 1 / 출력 : 15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function keepTheChange(input) {
  //1000엔짜리 지폐를 냈다는 가정이 있고, 입력값으로는 지불해야 할 금액이 들어옵니다.
  let change = Number(1000 - input);
  //카운트하기 위해 변수 count에 0을 할당합니다.
  let count = 0;

  //입력값에 배열이 들어오지 않으므로 직접 배열을 만들어줍니다.
  const joiCoins = [500, 100, 50, 10, 5, 1];

  //만든 배열의 개수만큼만 돌려줘야 합니다.
  for (let i = 0; i < joiCoins.length; i++) {
    //거스름돈이 0원이 되면 for 문을 멈춥니다.
    if (change === 0) break;

    //거스름돈과 잔돈을 나눈 몫을 셉니다.(쓰인 잔돈의 개수 세기)
    count += Math.floor(Number(change / joiCoins[i]));
    //거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
    change %= joiCoins[i];
  }

  //count를 리턴합니다.
  return count;
}

Algoritm 구현 Brute Force Algorithm

  • 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다.
  • 예를 들어 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 가정한다.
  • 이 자물쇠의 번호 조합은 잊어버렸지만 튼튼해서 다른 자물쇠로는 바꾸고 싶지 않습니다. 자물쇠를 사용하려면 비밀번호를 0000부터 9999까지의 경우의 수를 모두 하나하나 대입하여 자물쇠를 열어야 한다.
  • 이때 최악의 경우 10000번의 시도가 필요하다. 이렇게 하나하나 대입하여 시도하는 방법이 Brute Force Attack이다.
Brute Force Algorithm

image

  • Brute Force Algorithm은 무차별 대입 방법을 나타내는 알고리즘이다.
  • 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법이다.
  • Brute Force는 최적의 솔루션이 아니라는 것을 의미하기도 한다.
  • 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법을 의미한다.
  • 크게 두 가지 경우에 사용된다.
    • 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때
    • 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
Brute Force Algorithm 한계
  • Brute Force Algorithm은 문제의 복잡도에 매우 민감한 단점을 가지고 있다.
  • 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 수 있다.
  • 여기서 자원은 시간이 될 수도 있고 컴퓨팅 자원이 될 수도 있다.
Brute Force Algorithm 사용
순차 검색 알고리즘

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function SequentialSearch2(arr, k) {
  // 검색 키 K를 사용하여 순차 검색을 구현
  // 입력: n개의 요소를 갖는 배열 A와 검색 키 K
  // 출력: K 값과 같은 요소 인덱스 또는 요소가 없을 때 -1
  let n = arr.length; // 현재의 배열 개수를 n에 할당합니다.
  arr[n] = k; // 검색 키를 arr n 인덱스에 할당합니다.
  let i = 0; // while 반복문의 초깃값을 지정하고
  while (arr[i] !== k) {
    // 배열의 값이 k와 같지 않을 때까지 반복합니다.
    i = i + 1; // k와 같지 않을 때 i를 +1 합니다.
  }
  if (i < n) {
    // i가 k를 할당하기 전의 배열개수보다 적다면(배열 안에 k 값이 있다면)
    return i; // i를 반환합니다.
  } else {
    return -1; // -1을 반환합니다.
  }
}
문자열 매칭 알고리즘

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function BruteForceStringMatch(arr, patternArr) {
  // Brute Force 문자열 매칭을 구현합니다.
  // 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P
  // 출력: 일치하는 문자열이 있으면 첫 번째 인덱스를 반환합니다. 검색에 실패한 경우 -1을 반환합니다.
  let n = arr.length;
  let m = patternArr.length;
  for (let i = 0; i <= n - m; i++) {
    // 전체 요소 개수에서 패턴 개수를 뺀 만큼만 반복합니다. 그 수가 마지막 비교 요소이기 때문입니다.
    // i 반복문은 패턴과 비교의 위치를 잡는 반복문입니다.
    let j = 0;
    // j는 전체와 패턴의 요소 하나하나를 비교하는 반복문입니다.
    while (j < m && patternArr[j] === arr[i + j]) {
      // j가 패턴의 개수보다 커지면 안 되기 때문에 개수만큼만 반복합니다.
      // 패턴에서는 j 인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
      // 같을 때 j에 +1 합니다.
      j = j + 1;
    }
    if (j === m) {
      // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미입니다.
      // 이때의 비교했던 위치를 반환합니다.
      return i;
    }
  }
  return -1;
}
선택 정렬 알고리즘

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function SelectionSort(arr) {
  // 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
  // 입력: 정렬 할 수 있는 요소의 배열 A
  // 출력: 오름차순으로 정렬된 배열
  for (let i = 0; i < arr.length - 1; i++) {
    // 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다.
    // 현재 값 위치에 가장 작은 값을 넣을 것입니다.
    let min = i;
    // 현재 인덱스를 최솟값의 인덱스를 나타내는 변수에 할당합니다.
    for (let j = i + 1; j < arr.length; j++) {
      // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소와 비교하는 반복문을 구성합니다.
      if (arr[j] < arr[min]) {
        // j 인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
        min = j;
        // j 인덱스를 최소를 나타내는 인덱스로 할당합니다.
      }
    }
    // 반복문이 끝났을 때(모든 비교가 끝났을 때)
    // min에는 최솟값의 인덱스가 들어있습니다.
    // i 값과 최솟값을 바꿔서 할당합니다.
    let temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
  }
  // 모든 반복문이 끝나면 정렬된 배열을 반환합니다.
  return arr;
}

Dynamic Programming 피보나치 수열과 타일링

Recursion + Memoization
  • 다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용한다.
  • 이때 결과를 저장하는 방법을 Memoization이라고 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
}
ALGORITHM
algorithm greedy dp
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
바로가기