수학은 프로그래밍에 많은 도움이된다.
(컴퓨터가 계산기 이기때문에, 기본적으로 컴퓨터과학과 수학은 통하는부분이 있다.)
알고리즘 문제를 풀때 가장먼저 해야할 것은 무엇인가?
문제를 이해하고 어떻게 풀 것인지 전략을 세우는 것이다.
전략을 세우지 않는다면 어떤 자료구조를 사용할지, 어떤 알고리즘 기법을 사용할지 판단할 수 없다.
최근 코테에서등장하는 알고리즘 문제들은 단순히 알고리즘을 아는지 물어보는게아니라
어떤방법으로 풀어볼수있는지를 확인하는 문제들이 자주 등장한다. 즉 수학적사고 ,"컴퓨팅 사고를 할수있어?" 라고 물어보는것과 같다. 그 때문에 수학적 사고를 통해 컴퓨팅 사고를 할 수 있어야 한다.
다양한 수학개념이 있지만
크게 3가지
- GCD/LCM ( 최대공약수, 최소공배수 )
- 순열/조합
- 멱집합
1. GCD/LCM 최대공약수/최소공배수
문제 : 가로 xcm / 세로 ycm 인 직사각형 모양에 가장자리에 조명을 설치하는데 네 모퉁이는 반드시 설치하면서 일정한 간격으로 조명을 배열하려 할때 최소로 필요한 조명의 개수?
-> 최대공약수기 팔요하다고 알아낼수있을까?
일정한간격 => 공약수
최소로필요한조명의 갯수 => 최대공약수
m = GCD(x,y)
(x/m + y/m) < 두개의 변에 최소로 필요한 조명의개수
(x/m + y/m) * 2 = 직사각형 전체에 필요한 최소 조명갯수
문제 : 공장
직원이 A/B/C 세명이고
제작속도가 각각다르다.
A 는 55분마다 9개 생산 ,
B 는 70분마다 15개 생산 ,
C 는 85분마다 25개 생산
이들은 05:00부터 만들기시작해서
55,70,85분 동안 연속으로 제작한후 5분씩 쉰다.
이들 세명이 처음으로 동시에 쉴 시점이 퇴근 시간이라면 이날 하루에 제작한 물건의 개수는 모두 몇 개 인가?
다양한 풀이가 있을수 있지만
-> 최소공배수를 떠올리면 쉽고 빠르게 문제 해결이 될수 있다.
쉬는시간 5분씩 더하면
60/75/90 이 된다.
이때마다 생산을 시작한다.
세명이 동시에 쉴 시점은 세명이 쉬고 난 직후가 같은 시점이 된다.
따라서 공배수를 알아야 하고
쉬고난 직후가 처음으로 같은 시점을 구해야 하므로 최소공배수를 알아야 한다.
LCM(60,75,90) 은 900 이다.
A는 B,C와 쉬고 난 직후 처음으로 같은 시점까지 900/60 = 15턴을 반복하고 15턴 * 9개 = 135개 생산
B는 900/75 = 12턴을 반복하고 12턴 * 15개 = 180개 생산
C는 900/90 = 10턴을 반복하고 10턴 * 25개 = 250개 생산
그러므로 A,B,C가 하루에 생산하는량은 135+180+250 = 565개가 된다.
2. 순열/ 조합
문제 : 카드뽑기
[a,b,c,d,e] 5장의 카드를 가지고있다.
이 5장중 3장을 선택하고 나열한다고 하는데 두가지 조건이있다.
- 순서를 생각하며 3장을 선택한다.
- 순서를 생각하지않고 선택한다.
각 조건의 나열방법은 모두 몇가지 인가?
1번 조건에서 모든 가지 수를 구할때는 1장씩 나열 하면서 필요한 장수까지 도달하면 중지한다.
- 1장째의 카드를 선택하는 방법에는 5가지가 있다.
- 그 각각에 대해 2번째 카드를 선택하는 방법에는 4가지가 있다.
- 그 각각에 대해 3번째 카드를 선택하는 방법에는 3가지가 있다.
따라서 5X4X3 = 60이 된다.
순열은 순서를 생각하며 나열한다 는것에 주의해야한다.
- 5장에서3장을 선택하는 모든 순열의 수 ₅P₃ = (54321)/(2*1) = 60
- nPr = n! / (n-r)!
- 팩토리얼은 설명 생략
2번 조건에서 모든 가짓수를 구할때 3장을 하나의 그룹으로 선택한다
- 먼저 순열과 마찬가지로 순서를 생각하며 셉니다.
- 중복해서 센부분으로 나눗셈을 합니다.
조합은 일반화를 통해서 Combination의 약자 C로 표현하고
- 5장에서 3장을 선택하는 모든 조합의 수 = ₅C₃ = 5! / (3! * 2!) = 10
- 일반식 nCr = n! / r!(n-r)!
문제:소수찾기
한자리 숫자가 적힌 종이조각이 흩어져있다.
흩어진 종이조각을 붙여 소수를 몇개 만들수 있는지 알아내려 한다. 각 종이에 적힌 숫자가 적힌 배열이 주어진다면 종이조각으로 만들수있는 소수는 몇개인가?
위 문제에서 순열이 숨어있다는것을 알아차린다면 쉽게 문제를 해결할 수 있다.
전략을 세우자면
- n개의 숫자중에 1~k개 를 뽑아서 순열을 생성한다.
- 각 순열을 정수로 변환하고 해당 정수가 중복되지 않도록 하여 소수인지 검사한다.
- 소수이면 개수를 센다.
위문제에서 순서를 고려하지않고 조합으로 풀면 풀수없다.
문제 : 일곱난쟁이
일곱난쟁이의 키의 합이 100인걸 알고있고
난쟁이가 9명이라면 가짜 2명을 찾으면>
조합을 이용해서 일곱난쟁이를 찾을수 있다. 일곱난쟁이의 키의 합이 100이 라고 했으니
9명의 난쟁이중 7명의 난쟁이를 순서를 생각하지않고 그 합이 100이 되는경우를 찾으면 되는 문제이다.
3. 멱집합
어떤집합의 모든 부분집합을 멱집합이라고 한다.
예를 을어 집합 {1,2,3}이 있다고했을때
집합 {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 B : 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}
- step B : {2,3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면 {3}의 모든 부분집하에 {1}을 추가한 집합들을 나열하고 {3}의 모든 부분집합에 {1,2}를 추가한 집합들을 나열한다.
부분집합의 개수는 집합의 요소가 n개 일때 2ⁿ개가 된다.
앞서 배웟던 트리와 비슷한 모양이다.
왼쪽 선택 오른쪽 선택하지않음 으로 쭉 내려와서 뻗어나가면
트리구조가 되는것을 확인할수있다. 그림이나 사진은 마땅한게 없어서 나중에 추가
