S4 Unit 11. 코딩 테스트 준비

나현·2022년 12월 8일
section4코드스테이츠프론트엔드학습일지
0

학습일지

목록 보기
50/53
post-thumbnail

💡 이번에 배운 내용

  • Section4. 사람과 기계가 모두 쉽고 빠르게 접근 가능한 Web App을 만들 수 있다.
  • Unit11. [자료구조/알고리즘] 코딩테스트 준비: 코딩테스트를 대비해 알고리즘과 알고리즘을 이용하여 해결할 수 있는 문제를 다루며 문제 해결 능력을 기른다.

느낀점

알고리즘의 각 개념을 공부하고 예제를 풀어보면서 머리가 살짝 빠개질 뻔한 경험을 해보았다. 재귀함수를 이미 배우긴 했는데, 막상 활용하려면 쉽지 않다. 특히 제일 기억에 남는 것은 반복문을 여러번 중첩해서 사용해야 할 때, 이를 재귀함수로 만드는 것이었다. 처음부터 하려니 좀 막막했지만 몇 번 해보니까 조금은 익숙해지긴 했다. 부디 취업전까지 응애 코린이 좀 조금이나마 탈출하길 바라며...

키워드

Big-O 빅오 표기법, 시간 복잡도 Time complexity, 공간 복잡도 Space Complexity, Brute Force, Greedy Algorithm 탐욕 알고리즘 탐욕법, DP Dynamic Programming 동적 계획법,피보나치 수열 fibonacci, Recursion, Memoizatio, Iteration, Tabulation, 순열, 조합, nPr, nCr, GCD, LCM, 유클리드 호제법, 부분집합, 멱집합

학습내용

Ch1. 알고리즘

► 알고리즘의 특성

  • 입력(Input) :
    알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 한다.
    꼭 입력을 받지 않아도 되는 알고리즘도 있다. (ex. 원주율(pi) 구하기 등)
  • 출력(Output) :
    알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 한다. 출력되었다는 것은 연산이 끝났다는 것이며 이는 유한성과도 연관이 있다.
  • 유한성(Finiteness) :
    알고리즘은 유한한 명령어를 수행하고 유한한 시간 내에 종료해야 한다.
    알고리즘은 실행 후 반드시 종료되어야 한다는 것과 같다.
  • 명확성(Definiteness) :
    알고리즘의 각 단계는 단순하고 명확해야 한다.
  • 효율성(Efficiency) :
    알고리즘은 가능한 한 효율적이어야 한다.
    시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘이다.

► 알고리즘 푸는 방법, 공부 방법

  1. 문제를 이해한다.
    문제의 설명, 입출력 예시, 제한사항, 주의사항 등으로 문제를 파악한다.
    조건을 토대로 문제가 무엇인지를 이해하는 것부터 시작한다.
  2. 문제를 어떻게 해결할 수 있을지, 전략을 세운다.
    이해가 어렵다면, 연습장에 전체적인 그림을 그려가며 전체적인 흐름을 파악한다.
    먼저 인간의 사고로 문제를 해결할 수 있어야 한다.
    그 후 의사코드를 작성한다.
    막혔던 생각이 설명을 하면서 해결되는 경우도 있다.
  3. 문제를 코드로 옮긴다.
    전략을 코드로 옮긴다.
    구현한 코드의 최적화를 시도한다.
  4. 전체과정이 30~40분을 넘어가면 레퍼런스를 참고하며 이해한다.

Ch2. 시간복잡도

► 시간 복잡도(Time complexity)란?

시간복잡도란 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 나타낸 것이다. 주로 빅-오 표기법을 사용해 나타낸다.

  • Big-O 표기법: 알고리즘이 실행되었을 제일 오래 걸리는, 최악의 경우를 나타내는 방법이다. O(예상 연산 횟수)로 표기한다.

► O(1)

O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이 바로 출력값을 얻어낼 수 있다.
예시는 아래와 같다.

function findIndex(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4];
let index = 3;
let result = findIndex(arr, index);
console.log(result); // 4

► O(n)

O(n)은 linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다.
예시는 아래와 같다.

//예1
function findSum(n) {
  let sum=0;
  for (let i = 1; i < n; i++) {
    sum+=i;
  }
  return sum;
}

//예2
function findDoubleSum(n) {
  let sum=0;
  for (let i = 0; i < 2n; i++) {
	sum+=i;
  }
  return sum;
}

보통 1에서 n까지 반복문을 한 번 사용할 경우 O(n)이 된다.
예시1은 O(n), 예시2는 O(2n)이다. 그러나 이 n이 무한대로 커질경우 앞의 상수는 의미가 없게 된다.
따라서 n앞에 상수가 있어도 그냥 n과 같다고 보면 된다.
ex) O(2n)=O(4n)=O(n)

► O(log n)

O(log n)은 logarithmic complexity라고 하며, 입력값이 증가함에 따라 시간이 log n의 비율로 증가하는 것을 의미한다.
Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
쉽게 말해, 보통 단계를 진행할 때마다 탐색량이 전체의 절반씩 줄어드는 경우 O(log n)의 복잡도를 가졌다고 한다. 대표적인 알고리즘으로 이진탐색(BST, Binary Search Tree)이 있다.

► O(n^2)

O(n2)은 quadratic complexity라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
예시는 아래와 같다.

function O_expo2_algorithm(n) {
  for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++) {
	  //식
	}
  }
}

function O_expo3_algorithm(n) {
  for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++) {
	  for (let k = 0; k < n; k++) {
	    // do something for 1 second
	  }
	}
  }
}

보통 1에서 n까지 반복하는 반복문을 중첩해 사용했을 때, 중첩한 만큼 n을 제곱하여 표기한다.

► O(2^n)

O(2^n)은 exponential complexity라고 하며, 입력값이 증가함에 따라 시간의 2배씩 증가하는 것을 의미한다. Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
만약 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고려해 보는 것이 좋다.
예시는 아래와 같으며, 피보나치 수열을 O(2^n) 시간복잡도로 풀이한 알고리즘이다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

이렇게 구현할 경우 n이 40이상만 되어도 알고리즘 출력값을 반환하는데 수 초 이상이 걸리므로 다른 방식으로 구현하는 것이 좋다.

► 데이터 크기에 따른 시간 복잡도

입력으로 주어지는 데이터의 범위를 확인하면 어느 정도의 시간 복잡도를 가져도 괜찮을지 유추할 수 있다.
입력값이 어느정도 제한되어 있다면 시간을 줄이려고 애쓰는 것보다 일단 시간복잡도가 커도(느려도) 문제를 풀어보는 것이 나을 수 있다.
일단 문제를 풀고 최적화는 나중에 생각하도록 한다.

데이터 크기에 따른 수용 가능한 시간 복잡도는 다음과 같다.

데이터 크기 제한예상되는 시간 복잡도
n ≤ 1,000,000O(n) or O (logn)
n ≤ 10,000O(n2)
n ≤ 500O(n3)

Ch3. 공간복잡도

► 공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다.
프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구하는데, 여기서 가변적인 공간이 중요하다. 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 준다.
이런 공간 복잡도 계산도 마찬가지로 빅 오 (Big-O) 표기법을 사용한다.
아래는 공간복잡도의 예시다.

function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}

함수 factorial은 재귀함수로 구현되었다. 그리고 변수 n이 n개가 만들어지고 재귀함수를 호출할 경우 n부터 1까지 스택에 쌓이게 된다. 따라서 이 함수의 공간 복잡도는 O(n)이다.

► 공간 복잡도의 중요성

보통 때의 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다. 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 거의 없기 때문이다.
그리고 시간 복잡도에 맞다면 공간 복잡도도 대부분 통과한다. 만약 공간 복잡도에 실패했다면, 보통 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정했을 경우가 많으니 확인해야 한다.

그러나 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우 공간복잡도도 고려해야 한다. 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문이다.


Ch4. 알고리즘 유형

► 구현 Algorithm

구현 알고리즘은 문제의 설명과 조건을 그대로 코드로 구현하는 알고리즘을 의미한다.
이 경우 문제의 출제의도는 다음과 같은 사항에 초점이 맞춰져 있다.

  • 정해진 시간에는 문제를 빠르게 해결하는지
  • 문제를 정확하게 해결하는지
  • 해당 프로그래밍 언어의 문법을 잘 알고 있는지
  • 문제의 조건에 전부 부합하는 코드를 작성하는지

구현 Algorithm 해결 방법

  • 완전 탐색(brute force):
    완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식.
    단순히 모든 경우의 수를 탐색하는 방법으로 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등이 있다.
  • 시뮬레이션(simulation):
    문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮기는 것

구현 Algorithm 적용 예시: Brute Force 문자열 매칭
길이가 n인 전체 문자열이 길이가 m인 문자열 패턴을 포함하는지 검색하고 그 시작위치를 반환한다.
시작은 0부터 이다.
ex) 'abcdgkgkgk' 에서 'cd'를 포함하며, 시작위치는 2이다.

//arr은 전체문자열, patternArr은 찾을 문자열 패턴
function BruteForceStringMatch(arr, patternArr) {
  let n = arr.length;
  let m = patternArr.length;
  // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복한다. 
  //시작 위치만 찾으면 되기 때문이다.
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    //전체와 패턴의 각 요소를 비교하는 반복문이다.
    //패턴의 개수만큼 반복해야 하므로 j가 패턴의 개수 m보다 커지면 안된다.
    while (j < m && patternArr[j] === arr[i + j]) {
      //patternArr[j] === arr[i + j] :
      // 패턴의 글자와 현재 전체 인덱스의 글자가 같은지 판단한다.
      // 같다면 다음 글자도 비교해야 하므로 인덱스 j에 +1 한다.
      j = j + 1;
    }
    //만약 j와 패턴의 개수 m이 같다면 문자열 패턴을 찾은 것이 된다.
    if (j === m) {
      // 이 때 i는 전체 인덱스 중에서 문자열 패턴이 시작했던 지점이므로 
      //i를 바로 반환한다.
      return i;
    }
  }
  //위의 과정에서 반환되지않고 여기까지 왔다면 찾을 문자열이 없는 것이다.
  return -1;
}

► Greedy Algorithm(탐욕 알고리즘)

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 문제를 해결하는 방법은 다음과 같다.

Greedy Algorithm 문제 해결 단계

  • 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
  • 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
  • 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사 후, 해결되지 않았다면 선택 절차로 돌아가 반복

탐욕 알고리즘은 항상 최적의 해를 보장하지 못한다. (당장 좋은 방법을 택하는 것이 최선이 아닐수도 있기 때문이다.)
만약 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야 한다.

Greedy Algorithm의 조건

  • 탐욕적 선택 속성(Greedy Choice Property) :
    앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

Greedy Algorithm 적용 예시: 거스름돈의 동전 최소 개수 구하기

  • 선택 절차 : 가장 가치가 높은 동전을 우선 선택한다.
  • 적절성 검사 : 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
  • 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.
function findChange(change){
  //동전 개수
  let count=0;
  //동전 종류
  let coins=[500, 100, 50, 10];
  //동전들을 검사하기 위해 동전 종류만큼 반복한다.
  for(let i=0; i<coins.length; i++){
    //거스름돈이 0이 되면 반복문을 멈춘다.
    if(change===0) break;
    //선택된 동전이 거슬러준 금액을 초과하는지 검사하고, 동전의 개수를 센다.
    count+=Math.floor(Number(change/coins[i]));
 	//현재 거스름돈을 남은 거스름돈으로 대체한다.
    change=change%coins[i];
  }
  //동전 개수를 반환한다.
  return count;
}

탐욕 알고리즘으로 위 예시를 해결하려면 동전 간의 관계가 배수로 연결되어야 한다.
만약 coins=[6,7,8] 이런식으로 되어있다면 탐욕 알고리즘은 최적의 방법이 아니게 된다.

► Dynamic Programming(DP, 동적 계획법)

DP, 즉 동적 계획법은 모든 경우의 수를 조합해 최적의 해법을 찾는다.
탐욕 알고리즘과 같이 작은 문제에서 출발하지만, 매 순간 최적의 선택을 찾는 탐욕 알고리즘과는 달리 모든 경우의 수를 조합한 후 최적의 해법을 찾는다.

DP 문제 해결 단계

  • 주어진 문제를 여러 개의 (작은) 하위 문제로 나눈다.
  • 하위 문제를 계산한 뒤 그 해결책을 저장한다.
  • 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.
    즉 하나의 문제는 단 한 번만 풀도록 한다.

DP는 다음 두 가지 조건이 만족되어야 사용할 수 있다.

DP의 조건

  • Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
  • Optimal Substructure : 작은 문제에서 구한 정답을 큰 문제에서 활용할 수 있다.
  • Overlapping Sub-problems: 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.

DP 적용 예시: 피보나치 수열 구하기
피보나치 수열은 첫째와 둘째 항이 1이고, 그 다음의 항은 바로 앞 두 항의 합으로 구성된다.

원래 O(2^n)의 시간복잡도를 가진 피보나치 수열은 다음과 같다.

function fibo(n) {
	if(n <= 2) {
		return 1;
	};
	return fib(n - 1) + fib(n - 2);
}

그러나 이 경우 시간복잡도가 너무 크기 때문에 다음과 같은 방법을 사용해 좀 더 효율적으로 해결할 수 있다.

  • Recursion + Memoization
    Memoization은 동일한 하위 문제가 나왔을 경우 결과를 저장하여 동일한 계산의 반복 수행을 줄이도록 하는 기술이다.
    이 방법을 사용한 피보나치 예시는 다음과 같다.
function fiboMemo(n, memo = []) {
  //결과가 저장된 하위 문제인지 확인한다.
  if(memo[n] !== undefined) {
    return memo[n];
  }
  //피보나치의 첫 항, 두번째 항은 1이다.
  if(n <= 2) {
	return 1;
  }
  //결과가 저장되지 않았다면 결과를 구한다.
  let result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  //동일한 하위 문제가 나왔을 경우를 대비해 결과를 저장한다.
  memo[n] = result;
  //결과를 반환한다.
  return res;
}
  • Iteration + Tabulation
    Tabulation이란 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 배열(리스트 혹은 도표)에 저장해 반복 수행을 제거하는 기술이다.
    하위 문제의 결과를 배열에 저장해서 사용하는 것은 재귀함수와 비슷해 보일 수 있으나, 큰 문제에서 작은 문제가 아닌 작은 문제서부터 큰 문제로 옮겨가며(bottom-up) 해결한다는 차이가 있다.
    이 방법을 사용한 피보나치 예시는 다음과 같다. 
function fiboTab(n) {
  //피보나치의 첫 항, 두번째 항은 1이다.
  if(n <= 2) {
	return 1;
  }
  //피보나치의 첫 항, 두번째 항을 미리 배열에 저장한다.
  let fibNum = [0, 1, 1];
  //다음 항부터 배열에 저장해가며 해결한다.
  for(let i = 3; i <= n; i++) {
    //앞서 배열에 저장해 놓은 값들을 이용해 다음항을 구하고, 저장한다.
    fibNum[i] = fibNum[i-1] + fibNum[i-2];
  }
  //배열에 저장된 값을 반환한다.
  return fibNum[n];
}

Ch5. 알고리즘과 수학

몇몇 알고리즘 문제를 풀기 위해서는 수학개념을 몇가지 알아야 한다.
다음은 자주 나오는 기본적인 수학개념들에 대한 설명과 그 예제들이다.

► 순열

순열(Permutation)은 서로 다른 n개의 원소로 이뤄진 집합에서 중복 없이, 순서를 지켜 r개의 원소를 선택.나열하는 것을 의미한다. 여기서 r은 n보다 작아야 하며, 기호로 나타내면 nPr로 나타낼 수 있다.

순열 구하는 공식
순열은 팩토리얼을 사용해 다음과 같은 공식으로 나타낼 수 있다.
nPr=n!/(n-r)!

순열 적용 예시: r만큼 반복문 사용하기
nPr, 즉 n개의 원소중 n개를 순서를 지켜 뽑아야 할 때 모든 경우의 수를 구하는 함수를 아래와 같이 만들 수 있다. r의 개수만큼 반복문을 중첩시켜 찾는다.

function permutation() {
  let target = ['A', 'B', 'C', 'D', 'E']; //선택할 대상. nPr에서 n개
  let result = []; //각 부분집합이 배열로 들어있는 2차원 배열

  //nPr의 r개수만큼 중첩하여 반복문을 돌린다. 
  //각 반복문은 target의 처음부터 끝까지 반복한다. 
  for (let i = 0; i < target.length; i++) {
    for (let j = 0; j < target.length; j++) {
      for (let k = 0; k < target.length; k++) {
        if(i === j || j === k || k === i) continue; //중복 체크
        //순열의 각 부분집합을 나타내는 배열
        result.push([target[i], target[j], target[k]])
      }
    }
  }

  return result;
}

만약 nPr에서 r이 매번 다르다면 반복문 부분을 재귀함수로 만들어 사용한다.

function permutation(r) {
  let target = ['A', 'B', 'C', 'D', 'E']; //선택할 대상. nPr에서 n개
  let result = []; //각 부분집합이 배열로 들어있는 2차원 배열

  //nPr의 r개수만큼 중첩하여 반복문을 돌린다. 
  //각 반복문은 target의 처음부터 끝까지 반복한다. 
  const recursive=(r, arr)=>{
    //base case
    if(r===0){
      result.push(arr);
      return;
    }
    
    //recursive case
    for (let i = 0; i < target.length; i++) {
      let currentValue=target[i];
      if(!arr.includes(currentValue)){
        recursive(r-1, [...arr,currentValue]);
      }
    }
  }
  
  recursive(r, []);

  return result;
}

► 조합

조합(combination)은 서로 다른 n개의 원소로 이뤄진 집합에서 중복 없이, 순서없이 r개의 원소를 선택.나열하는 것을 의미한다. 여기서 r은 n보다 작아야 하며, 기호로 나타내면 nCr로 나타낼 수 있다.

조합 구하는 공식
조합은 팩토리얼을 사용해 다음과 같은 공식으로 나타낼 수 있다.
nCr=n!/r!(n-r)!
조합은 순열을 이용해서도 나타낼 수 있다.
nCr=nPr/r!

조합 적용 예시: r만큼 반복문 사용하기
nCr, 즉 n개의 원소중 n개를 순서없이 뽑아야 할 때 모든 경우의 수를 구하는 함수를 아래와 같이 만들 수 있다. 순열을 구할 때처럼 r의 개수만큼 반복문을 중첩시켜 찾되, 각 반복문은 이전 상위 반복문의 다음 인덱스부터 시작해야 한다.

function combination() {
  let target = ['A', 'B', 'C', 'D', 'E']; //선택할 대상. nCr에서 n개
  let result = []; //각 부분집합이 배열로 들어있는 2차원 배열

  //nCr의 r개수만큼 중첩하여 반복문을 돌린다. 
  //처음 반복문은 target의 처음부터 끝까지 반복한다. 
  //그 다음 반복문은 상위 반복문의 다음부터 반복해야 한다.
  for (let i = 0; i < target.length; i++) {
    for (let j = i+1; j < target.length; j++) {
      for (let k = j+1; k < target.length; k++) {
        //순열의 각 부분집합을 나타내는 배열
        result.push([target[i], target[j], target[k]])
      }
    }
  }

  return result;
}

만약 nCr에서 r이 매번 다르다면 반복문 부분을 재귀함수로 만들어 사용한다.

function combination(r) {
  let target = ['A', 'B', 'C', 'D', 'E']; //선택할 대상. nCr에서 n개
  let result = []; //각 부분집합이 배열로 들어있는 2차원 배열

  //nCr의 r개수만큼 중첩하여 반복문을 돌린다. 
  //처음 반복문은 target의 처음부터 끝까지 반복한다. 
  //그 다음 반복문은 상위 반복문의 다음부터 반복해야 한다.
  const recursive=(r, arr, start)=>{
    //base case
    if (r === 0) {
      result.push(arr);
      return;
    }

    //recursive case
    for (let i = start; i < cards.length; i++) {
      const item = cards[i];
      recursive(r - 1, [...arr, item], i + 1);
    }
  }
  
  recursive(r, [], 0);

  return result;
}

► GCD, LCM

GCD, LCM은 각각 최대공약수, 최소공배수로 이를 활용한 알고리즘 문제를 풀기 위해서는 아래의 개념들을 필수로 알아야 한다.

  • 최대공약수(Greatest Common Divisor, GCD): 두 수 이상의 여러 공약수 중 최대인 수
  • 공약수(Common Divisor): 두 수의 여러 약수(1과 자기자신만으로 나눠진다) 중 공통된 약수
  • 최소공배수(Lowest Common Multiple, LCM): 두 수 이상의 여러 공배수 중 최소인 수
  • 공배수(Common Multiple): 두 수의 배수 중 공통된 배수

GCD를 구하는 방법 중 유클리드 호제법이 있으며, GCD를 알아내면 LCM을 알아낼 수 있다.

공식: GCD를 구하는 유클리드 호제법
기본적인 방식은 시간이 많이 걸릴수도 있으므로, 비교적 간단하게 구할 수 있는 방법을 소개한다.

  • 유클리드 호제법: 자연수 a, b가 있을 때 a를 b로 나눈 나머지r(a%b)로 b를 나눈 나머지(b%r)를 구한다. 이를 나머지가 0이 될 때까지 반복하면 이 나눠지는 값이 a와 b의 최대공약수가 된다.

유클리드 호제법 예시
위에서 설명한 유클리드 호제법은 다음의 예시 코드를 보면 좀 더 이해가 쉽다.
아래 코드는 유클리드 호제법으로 GCD를 구하고, 그 GCD로 LCM을 구하는 방법이다.

//GCD 구하기
const gcd=(a, b)=>{
	while(b !== 0){ //b가 0이 되면 최종적으로 Infinity가 리턴되므로 주의한다.
		let r = a % b;
		a = b;
		b = r; 
      //이 과정을 통해 다음 반복시 b%r을 새로운 나머지로 할당하게 된다.
	}
	return a;
}

//LCM 구하기
const lcm=(a, b)=>{
	return a * (b / gcd(a, b));
}

► 부분집합

부분집합은 어떤 집합의 원소로 만들 수 있는 집합으로, 개념은 따로 자세히 설명하지 않는다.
다만 알고리즘 문제에 부분집합의 개념을 적용하여 풀이하려면 다음의 사항을 알아둬야 한다.

  • 어떤 집합의 모든 부분집합을 멱집합이라고 한다.
  • 공집합과 자기자신도 부분집합이다.
  • 어떤 집합의 부분집합을 구하는 방법을 도식화하면 트리구조와도 같다.

부분집합 적용 예시
위에서 언급한대로 부분집합을 구하는 것은 트리구조와도 같으므로 재귀함수를 사용할 수 있다.

function powerSet () {
  	const targetSet = ['A', 'B', 'C']; //대상이 될 집합
	const result = []; //모든 부분집합(배열)들을 담을 2차원 배열

	const recursion =(subset, start)=>{
		result.push(subset);

		for(let i = start; i < targetSet.length; i++){
			recursion([...subset, targetSet[i]], i+1);
			//이렇게도 구현할 수 있습니다.
			//recursion(subset.concat(arr[i]), i+1);
		}
	}

    //공집합부터 시작하여 부분집합을 구한다.
	recursion([], 0);

	return result;
}
profile
나현
프론트엔드 개발자 NH입니다. 시리즈로 보시면 더 쉽게 여러 글들을 볼 수 있습니다!
이전 포스트

S4 Unit 10. [deploy] CI/CD

다음 포스트

S4 Unit 12. 미니 해커톤 회고

0개의 댓글