자료구조/알고리즘 - 코딩 테스트 2

Algorithm with Math

수학과 알고리즘

Math in Programming

컴퓨터 과학과 수학은 통하는 부분이 많다
→ 수학을 학습하는 것은 프로그래밍 기본을 탄탄히 하는 것

 

알고리즘에서 다루는 수학은 기본적으로 크게 어렵지 않음(중학교 수준의 수학)
→ 최소한의 수학이므로 이 정도는 해 줘야 한다?

Algorithm with Math

알고리즘 문제를 풀 때는 문제를 어떻게 이해하고 풀 것인지 전략을 세우는 것이 중요
→ 코딩 테스트에서는 단순히 특정 알고리즘을 아는지 묻는게 아니라 특정 기법을 사용해서 풀어봐라는 식의 문제가 출제된다
→ 수학적 사고를 통해 컴퓨팅 사고를 할 수 있어야 한다

 

최소한, GCD/LCM(최대공약수, 최소공배수), 순열/조합, 멱집합에 대한 수학적 개념 및 알고리즘은 잘 알고 있어야 한다
→ 핵심은 수학을 공부하는 것이 아닌, 문제가 어떤 수학적 개념을 요구하는지 파악해서 그 것을 통해 컴퓨팅 사고를 하는 것

 

순열 / 조합

순열은 순서를 생각하는 것이고, 조합은 순서를 생각하지 않는 것

 

카드 뽑기의 예시로 알아보자

[A, B, C, D, E]로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.

1. 순서를 생각하며 3장을 선택
2. 순서를 생각하지 않고 선택

각 조건을 만족하면서 카드를 나열하는 방법은 모두 몇 가지?

 

순열

위에서 조건1(순서를 생각)을 만족하는 모든 경우의 수를 구하는 것
→ 모든 카드를 1장씩 나열하면서 나열된 카드가 3장에 도달하면 카드의 나열을 중지

 

다음과 같은 방법으로 경우의 수를 구한다

* 첫번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 존재
* 첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법에는 네 가지가 존재
* 두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법에는 세 가지가 존재

따라서 5 X 4 X 3 = 60 가지의 방법이 존재
→ 이렇게 n개 중에서 일부만을 선택하여 나열하는 것이 순열
→ 순열은 반드시 순서를 지키면서 나열해야 한다

 

즉, [A, B, D]와 [A, D, B] 두 경우 모두 A, B, 그리고 D라는 같은 카드를 3장 선택했지만, 나열하는 순서가 다르므로 서로 다른 경우로 파악해야 한다

 

순열의 공식 정리

* 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60

* 일반식 : nPr = n! / (n – r)!

* ! 은 팩토리얼(factorial)로 n! 은 n에서부터 1씩 감소하여 1까지의 모든 정수의 곱
(n 보다 작거나 같은 모든 양의 정수의 곱)

* 5! = 5 X (5 - 1) X (5 - 2) X (5 - 3) X (5 - 4) = 5 X 4 X 3 X 2 X 1 = 120

* 팩토리얼에서 0!과 1!은 모두 1

 

기본적인 순열의 알고리즘을 코드화하면 다음과 같다

const getPermu= function(arr, num){
  let result=[];
  if(num===1){  //base case
    return arr.map(el => [el])  //각 요소에 대해 배열 껍데기 씌워서 출력
    // n개중에서 1개 선택할 때(nP1), 바로 모든 배열의 원소 return. 1개선택이므로 순서가 의미없음.
  }
  // 재귀 케이스
  arr.forEach((cur, idx, originArr) => {

    //! 중복 순열, 순열, 조합에서 이 부분. rest 부분만 바뀐다고 보면 된다!
    const rest = [...originArr.slice(0,idx), ...originArr.slice(idx+1)] 
    // 해당하는 cur를 제외한 나머지 배열 

    const permu = getPermu(rest, num-1);  
    // 맨 앞의 cur는 반드시 포함되어야 하므로 이를 제외한 나머지에 대해서 순열을 돌린다
    const attached = permu.map(el => [cur,...el]);  
    // 돌아온 순열에 떼 놓은(cur) 값 붙이기
    result.push(...attached)  //// 배열 spread syntax 로 모두다 push
  })

  return result;  //결과 배열을 리턴
}

조합

위에서 조건2(순서를 상관x)을 만족하는 모든 경우의 수를 구하는 것
→ 3장을 하나의 그룹으로 선택해야 한다

 

다음과 같은 방법으로 경우의 수를 구한다

* 순열로 구할 수 있는 경우를 찾는다

* 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다

순열에서는 순서를 고려하지 않는다는 점을 생각해야 한다

 

위의 예를 통해 조합의 경우의 수를 구하면, 먼저 순열인 5P3 = 543 =60 에서
중복된 경우의 수를 나눠야 하는데, 그 경우의 수는 3장의 카드를 순서를 생각하며 나열한 모든 경우의 수와 같다
→ 즉, 3장의 카드를 순열로 뽑는 경우의 수와 같으므로, 3P3=321=6 이다
→ 순열로 구할수 있는 경우/ 중복된 경우의 수 이므로 60/6 =10 그러므로, 조합의 경우의 수는 10

 

이를 공식으로 보면,

* 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10

* 일반식: nCr = n! / (r! * (n – r)!)

 

  const getCombination = function(arr, num){
    const result=[];
    // base case
    if(num===1){
      return arr.map(el => [el]) // 각 요소에 배열 껍데기만
    }
    // 재귀 케이스
    arr.forEach((fixed, idx, originArr) => {
      const rest=originArr.slice(idx+1);  // 나머지를 구하고  나머지에 대한 조합을 한번 재귀 돌리자
      const combinations = getCombination(rest, num-1)  // fixed꺼 하나 빠졋으므로 num-1
      const attached = combinations.map( el => [fixed, ...el])  // 조합돌린 거에서 fixed를 앞에 합쳐주자
      result.push(...attached); // 결과 배열에 그 값들을 넣어 넣어
    })
    return result; 
  }

이를 바탕으로 간단한 문제 예시들을 살펴 보자

 

문제: 소수 찾기

한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다. 흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 종이에 기록된 모든 숫자가 배열로 주어진다면, 이 종잇조각으로 만들 수 있는 소수는 몇 개인가요?

→ 순열로 접근하는 문제이다

 

기본 전략

1. n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성

2. 각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사

3. 소수이면 개수를 카운트

숫자는 순서에 의해 전혀 다른 값이 될 수 있으므로, 조합이 아닌 순열로 접근해야 한다

 

문제: 일곱 난쟁이

왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다. 하루 일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉" 명이었던 겁니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. (뛰어난 수학적 직관력을 가지고 있던) 백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다. 아홉 난쟁이 각각의 키가 주어질 때, 원래 백설 공주와 평화롭게 생활하던 일곱 난쟁이를 찾는 방법은 무엇인가요?

→ 조합으로 접근하는 문제
→ 9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고 키를 합했을 때, 100이 되는 경우를 찾는다

 

순열과 조합을 활용하는 문제는 먼저 문제를 이해하고 지문 속에서 힌트를 얻어 활용할 수 있어야 하는게 포인트!

GCD / LCM (최대 공약수/ 최소 공배수)

다음의 개념들을 기본적으로 숙지하고 있어야 함

* 약수: 어떤 수를 나누어 떨어지게 하는 수

* 배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수

* 공약수: 둘 이상의 수의 공통인 약수

* 공배수: 둘 이상의 수의 공통인 배수

* 최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수

* 최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

 

문제: Mask 생산

방역용 마스크를 제작/판매하는 Mask 회사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

→ 최소 공배수 로 접근하는 문제

 

A, B, C의 작업 시간과 쉬는 시간 5분을 더하면 A, B, C는 각각 60분, 75분, 90분마다 마스크를 생산
세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직 후가 같을 시점
→ 따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로 최소 공배수를 생각

 

LCM(60, 75, 90) = 900
→ (60=2235, 75=355, 90=2335) 이니깐, 공통 배수를 뽑으려면, 2^23^25^2 이므로, 4925= 36*25=900 이다

 

이를 적용해 문제를 풀어 보면,

 

A는 900/60 = 15 번 작업하고, 15번 X 9개 = 135개의 마스크를 생산
B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개 생산
C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 생산

 

→ A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개

 

문제를 답을 도출하는 것도 중요하지만, 해당 문제에서 최대 공약수와 최소 공배수를 활용하겠다는 문제 해결 전략을 세우는 것이 가장 중요!

문제: 조명 설치

건물의 라운지에 있는 가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야 하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)

→ 최대 공약수로 접근하는 문제
문제 해결 전략을 떠올리려면 반복적인 훈련과 학습이 필요

 

모든 조명을 일정한 간격으로 설치해야 한다 → 가로변과 세로변의 공약수를 구한다

 

가로와 세로 각각 나누어서 나머지가 없이 떨어지는 수들을 나열한 뒤, 공통된 수만 모으면 공약수를 구할 수 있다
그리고 공약수를 기준으로 조명을 설치하면, 길이가 다른 가로와 세로여도 일정한 간격으로 나누어 조명을 설치할 수 있다

 

최소로 필요한 조명의 개수 를 파악해야 하기 때문에 최대 공약수가 필요

GCD(12, 24)는 12이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 12로 나누어 최소로 필요한 조명의 개수를 구할 수 있다

 

(12/12 + 24/12)2=(1+2)2= 6

 

→ 그러나 이 문제에서는 꼭지점을 제외한 직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하므로 12를 제외한 최대 공약수로 문제를 해결해야 함

 

그 다음 최대 공약수가 6이므로,
(12/6 + 24/6)2 = (2+4)2 = 12

 

멱집합

어떤 집합이 있을 때, 이 집합의 모든 부분 집합 을 멱집합이라고 한다

ex) 집합 {1, 2, 3}의 모든 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개

 

모든 부분 집합을 나열하는 방법은 다음과 같다.
부분 집합을 나열하는 방법에서 가장 앞 원소(혹은 임의의 집합 원소)의 존재 유무(있는지 없는지)에 따라 단계를 나누는 기준을 결정

 

* Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.

    - Step B: 2를 제외한 {3}의 부분집합을 나열합니다.

        - Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}

        - Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}

    - Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.

        - Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, 
        {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 
        모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}

* Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.

    - Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, 
    {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 
    {1, 2}를 추가한 집합들을 나열합니다.

        - Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, 
        {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 
        {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}

        - Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, 
        {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 
        {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}

원소가 있는지, 없는지 2가지 경우를 고려하므로 집합의 요소가 n개일 때, 모든 부분 집합의 개수는 2^n개이다.

 

위의 예에서 {1,2,3}의 멱집합을 구하는 단계가 다소 복잡해 보일 수 있지만, 이 패턴은 자세히 보면 트리 구조와 비슷한 형태이다(물론 트리 문제는 아니다)

 

멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠고 있음
여기서의 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 구조
→ 문제를 작은 단위로 줄여나가는 재귀를 응용

 

예를 들어 PowerSet 이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet 함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여 간다.
문제가 가장 작은 단위로 줄어들고(base case), 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있다