(S3W1) TIL 47일차 220406 (코딩테스트 준비)

오늘의 학습목표

• 알고리즘이 무엇인지 설명할 수 있다.
• 알고리즘 문제를 이해하고 전략을 세울 수 있다.
• 알고리즘 풀이에 필요한 수도 코드를 작성할 수 있다.
• 수도 코드에서 세운 전략을 코드로 구현할 수 있다.
• 내가 구현한 알고리즘을 자바스크립트 언어로 설명할 수 있다.

학습내용

Math in Programming

우리가 사용하는 컴퓨터는 0과 1로 모든 연산을 실행합니다.
컴퓨터가 단순하게 연산하기 때문에, 기본적인 컴퓨터 과학과 수학은 통하는 부분이 있습니다.
그러므로 수학을 학습하는 것은 프로그래밍의 기본을 탄탄히 하는 일입니다.

알고리즘 파트에서 다루는 수학은 중학교 수준의 수학입니다.
프로그래밍을 위한 최소한의 수학이기 때문에,

수포자나 수학을 어려워하는 분도 충분히 따라올 수 있고, 학습해야만 하는 내용입니다.

 

Algorithm with Math

알고리즘 문제를 풀 때 먼저 해야 할 것은 문제를 이해하고 어떻게 풀 것인지 전략을 세우는 것입니다.

전략을 세우지 않는다면, 어떤 자료구조, 알고리즘 기법을 사용할지 판단할 수 없습니다.

최근 코딩 테스트에 등장하는 알고리즘 문제는

단순히 "너 이 알고리즘 알아?"라고 물어보지 않습니다.

요즘 출제되는 문제는 "특정 방법을 사용해서 풀어 볼래?"라고 물어보는 문제가 자주 등장합니다.

"특정 방법을 사용해서 풀어 볼래?"라는 질문은 

다시 말해 "컴퓨팅 사고를 할 수 있어?"라고 물어보는 것과 같습니다.

다양한 수학적 개념이 있지만, 알고리즘 문제와 코딩 테스트에 자주 등장하고 필요한 주요 개념들을

크게 3가지 개념 GCD/LCM(최대공약수, 최소공배수), 순열/조합, 멱집합을 소개하고 활용합니다.

 

Algorithm with Math - 순열 / 조합

문제: 카드 뽑기

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

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

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

1. 순열 공식 : nPr = n! / (n - r)!
   • 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60 가지
2. 조합 공식: nCr = n! / (r! * (n - r)!)
   • 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10 가지

 

문제: 소수 찾기

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

이 문제에는 순열이 숨어 있습니다. 만약 이 사실을 알아차린다면, 문제를 보다 쉽게 해결할 수 있습니다.

순열을 이용한다면, 다음과 같이 전략을 세울 수 있습니다.

1. n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성합니다.
2. 각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사합니다.
3. 소수이면 개수를 셉니다.

숫자는 순서에 의해 전혀 다른 값이 될 수 있습니다.

예를 들어 123과 321은 전혀 다른 숫자이지만 이 문제를 조합으로 접근하게 된다면, 123과 321은 같은 경우로 취급합니다. 따라서, 순서를 고려하지 않고 k 개를 뽑아내는 조합으로는 이 문제를 해결할 수 없습니다.

 

문제: 일곱 난쟁이

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

 

위 문제는 조합을 이용해서 일곱 난쟁이를 찾을 수 있습니다. 모든 일곱 난쟁이의 키를 합했을 때 100이 된다고 주어졌기 때문에, 9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고, 난쟁이 7명의 키를 합했을 때 100이 되는 경우를 찾으면 됩니다.

Algorithm with Math - GCD / LCM

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

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

문제: Mask States

방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 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입니다. (LCM; Least Common Multiple, 최소 공배수)

 

A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 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개가 됩니다.

 

문제: 조명 설치

이 문제에서 필요한 전구의 개수를 구하려고 할 때, 최대 공약수를 떠올리면 빠르게 문제를 해결할 수 있습니다.

모든 조명을 일정한 간격으로 설치해야 하므로, 가로변과 세로변의 공약수를 구해야 합니다.

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

 

최소로 필요한 조명의 개수를 파악해야 하기 때문에 최대 공약수가 필요합니다. 따라서 GCD(12, 24)는 12이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 12로 나누어 최소로 필요한 조명의 개수를 구할 수 있습니다. 

 

(Advanced) Algorithm with Math - 멱집합

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

집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개입니다. 그리고 이 모든 부분집합을 통틀어 멱집합이라고 합니다.

 

이렇게  모든 부분집합을 나열하는 방법은 다음과 같이 몇 단계로 구분할 수 있습니다.

부분집합을 나열하는 방법에서 가장 앞 원소가 있는지, 없는지에 따라 단계를 나누는 기준을 결정합니다.

멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인할 수 있습니다.

여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다.

따라서, 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있습니다.

 

예를 들어 PowerSet 이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet 함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여 해결할 수 있습니다.

 

문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.

 

오늘의 회고

오늘 챕터내용은 중학교 수준 수학이라 어렵지 않았지만,

이것을 코드로 구현한다는건 정말 쉽지 않다는 것을 느꼈습니다.

재귀.. 섹션2 때 한번 해도 너무 어렵네요 ㅠ

어우.. 그리고 아직 한문제 덜풀어서 주말이용해서 추가 학습해야 할 것 같습니다 ㅠㅠ