S4) Unit 11. [자료구조/알고리즘] Algorithm 유형

📣  Greedy Algorithm

𝟭. Greedy Algorithm

✔️ 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

 

𝟮. Greedy Algorithm 문제 해결 단계

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

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

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

 

𝟯. Greedy Algorithm 적용 예시

Q. 김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다. 이때 김코딩은 어떻게 거슬러 주어야 할까요?

A. 

1️⃣ 선택 절자 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.

2️⃣ 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.

3️⃣ 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.

=> 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서로 거슬러준다.

 

𝟰. Greedy Algorithm의 특징

1️⃣ 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2️⃣ 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

=> 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다.

---

📣  Algorithm 구현의 기초

✔️ 알고리즘 문제를 푼다 = 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환해서 코드로 구현하는 것

➰ 정확하고 빠를수록 구현 능력이 좋다고 한다(정해진 시간 안에 빠르게 문제를 해결하는 능력)

 

𝟭. 완전 탐색

✔️ 단순히 모든 경우의 수를 탐색하는 경우로, 모든 문제는 완전 탐색으로 풀 수 있다.

➰ 단순하고 무식하지만 답이 무조건 있다는 장점이 있다.

➰ 하지만 탐색해야 할 데이터의 양이 많아질 경우 완전 탐색 알고리즘은 비효율적이다.

➰ 때문에 완전 탐색은 문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 완전 탐색밖에 없다고 판단될 때 적용하는 것이 좋다.

➰ Brute Force(조건/반복을 사용해 해결), 재귀, 순열, DFS/BFS 등이 있다.

 

𝟮. 시뮬레이션

✔️ 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 방법

➰ 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

 

✔️ 시뮬레이션 예시

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

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

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

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

예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"

 

➰ 문제에 대한 이해를 바탕으로 조건을 하나도 빠짐없이 처리해야 정답을 구할 수 있다.

➰ 조건을 하나라도 놓치면 통과할 수 없고, 길어진 코드 때문에 복잡해질 수 있다.

---

📣  Dynamic Algorithm

𝟭. Dynamic Algorithm(DP)

✔️ 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 방법

➰ 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 연산을 줄인다 => 하나의 문제는 한 번만 풀도록 하는 알고리즘

 

𝟮. Dynamic Algorithm의 사용 조건

1️⃣ Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.

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

➰ 대표적인 문제는 '피보나치 수열'

➰ 각 피보나치(n)의 값은 (n-2) + (n-1) 이므로 이를 이용해서 문제를 해결한다.

➰ 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.

🚨 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.

 

2️⃣ Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다.

=> 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

✔️ 정답은 최적의 해결 방법(Optimal solution)을 의미하며, 이를 구할 때 주어진 문제의 작은 문제들의 최적의 해를 찾아야한다. 작은 문제들의 최적의 해를 결합하면 결국 전체 문제의 최적의 해법을 구할 수 있다.

➰ 가장 대표적인 예시는 최단 경로를 찾는 문제이다.

Q. A에서 D로 가는 최단 경로를 찾아라.

A. 그의 작은 문제인 A에서 C로 가는 최단 경로, 또 그의 작은 문제인 A에서 B로 가는 최단 경로를 구하면 결국  A에서 D로 가는 최단 경로를 구할 수 있게 된다.

---

📣  Algorithm의 유형 예제

𝟭. Greedy Algorithm - 거스름돈

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

A. 입력이 380이면 거스름돈은 620엔이다 => 500엔 1개, 100엔 1개, 10엔 2개로 총 4개가 가장 적게 잔돈을 거슬러 받는 방법

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;
}

➰ 거스름돈 개수가 가장 적게 줘야하기 때문에 금액이 큰 잔돈부터 계산을 해야한다 => 금액이 큰 잔돈 순서대로 배열을 만들어준다.

➰ for문에서 배열의 요소 개수만큼 반복문을 돌고, if문에서 잔돈이 0원이 되면 for문을 멈춘다.

 

𝟮. Brute Force Algorithm

✔️ 하나하나 대입하는 무차별 대입 방법

➰ 공간, 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법

➰ 프로세스 속도를 높일 수 있는 다른 알고리즘이 없는 경우

➰ 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 하는 경우

➰ 데이터의 범위가 커질수록 비효율적이다.

 

✔️ Brute Force Algorithm의 한계

➰ 문제의 복잡도에 매우 민감해서, 문제가 복잡해질수록 많은 자원을 필요로 하는 알고리즘이 될 수 잇다.

 

✔️ Brute Force Algorithm을 사용하는 곳

1️⃣ 순차 검색 알고리즘

➰ 0부터 찾고자 하는 값이 있는 인덱스까지 순차적으로 검색한다.

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을 반환합니다.
	}
}

 

2️⃣ 문자열 매칭 알고리즘

➰ 길이가 n인 전체 문자열이 길이가 m인 문자열 패턴을 포함하는 지 검색한다.

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;
}

 

 

3️⃣ 선택 정렬 알고리즘

➰ 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 알고리즘

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 - 피보나치 수열

✔️ DP를 이용해 피보나치 수열을 해결하는 경우, Recursion + Memoization / Iteration + Tabulation 두 가지 방법이 있다.

 

1️⃣ Recursion + Memoization

function fibMemo(n, memo = []) {

		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) {
			return memo[n];
		}
        // n번째 피보나치 값이 있다면 또 구하지 않고 저장된 값을 사용한다.

    if(n <= 2) {
			return 1;
		}

		// 없다면 재귀로 결괏값을 도출하여 res에 할당(처음 계산하는 수라면)
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);

		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo에 저장
    memo[n] = res;

    return res;
}

➰ 시간복잡도는 O(n) => 메모제이션이 없는 그냥 재귀함수의 시간복잡도 O(2^n)과 비교해 아주 빠르다.

 

2️⃣ Iteration + Tabulation

➰ 반복문을 이용해서 구현하는 경우 => 작은 문제에서부터 시작해서 큰 문제를 해결해 나가는 Bottom-up 방식을 사용

function fibTab(n) {
    if(n <= 2) {
			return 1;
		}

		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    let fibNum = [0, 1, 1];

    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
    }

    return fibNum[n];
}

 

✚ 크롬 개발자 도구에서 함수 실행 시간 측정 방법

var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')

 

𝟰. Dynamic Programming - 타일링

Q. 2xn 크기의 타일이 주어진다면, 2x1과 1x2 크기의 타일로 채울 수 있는 경우의 수를 모두 구해야 합니다.

A. 맨 마지막 타일은 세로 타일 1개이거나 가로 타일 2개인 2가지 경우밖에 없기 때문에, 마지막 타일을 제외했을 때 남는 공간의 마지막 타일도 2가지 경우 밖에 없다 => 세로와 가로의 마지막 타일을 제외한 나머지 공간을 채우는 경우의 수와 답이 같다.

function tiling2x1(n) {
  let memo = [0, 1, 2];

  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }

  return memo[n];
};