Algorithm with Math
기본적인 컴퓨터 과학과 수학은 통하는 부분이 있음.
알고리즘 문제를 풀 때 가장 먼저 해야 할 것은 무엇일까?
문제를 이해하고 어떻게 풀 것인지 전략을 세우는 것.
문제 풀이를 위해 전략을 세우지 않으면, 어떤 자료구조를 사용할지, 어떤 알고리즘 기법을 사용할지
판단할 수 없음.
최신 트렌트는 " 너 이 알고리즘 알아?" 가 아니라 "이 방법을 사용해서 풀어 볼래?" 라고 물어봄.
따라서 수학적 사고를 통해 컴퓨팅 사고를 할 수 있어야함.
오늘은
-
GCD / LCM
-
순열 / 조합
-
멱집합
순열
기본적인 중복순열 알고리즘 (for 문)
Example) 4파이3 표현
let arr = [2, 3, 4, 5] // 얘가 N쪽
let result = [];
for (let a = 0; a < arr.length; a++) { // for문의 개수가 R쪽
for (let b = 0; b < arr.length; b++) {
for (let c = 0; c < arr.length; c++) {
result.push([arr[a], arr[b], arr[c]])
}
}
}아니 근데 이게 너무 어렵잖아. 20 P 15 면은 for문 15개 쓸거임? ㄴㄴ 재귀 쓰자고
중복순열을 재귀 알고리즘으로!!
let arr = [2, 3, 4, 5]
let result = [];
const recursion = (count, burket) => {
//base case
if (count === 0) {
// burket을 result에 넣고 여기서 burket은 일회용 배열임
result.push(burket)
// 아무것도 리턴하지 않음.
return;
}
// 어쩃든 arr배열을 순회하긴 해야하니까 반복문 하나는 필요함
for (let i = 0; i < arr.length; i++) {
// 현재 요소 선언
let curEl = arr[i]
// 재귀
recursion(count - 1, burket.concat(curEl))
}
// 마지막으로 result 리턴
}
// 재귀 함수 실행 3은 3번 뽑기 그 다음 일회성 빈배열 선언
recursion(3, [])
console.log(result);기본적인 순열 알고리즘 (for문)
Example) 4P3 표현
let arr = [2, 3, 4]
let result = [];
for (let a = 0; a < arr.length; a++) {
for (let b = 0; b < arr.length; b++) {
for (let c = 0; c < arr.length; c++) {
if (a === b || b === c || a === c) continue; // 중복요소 걸러내는것 멋지네
result.push([arr[a], arr[b], arr[c]])
}
}
}
console.log(result)
조합
노동조합(union) 이 아님 ㅎ
combination임 조합의 특징은 순서에 상관없다. 뭔 순서? 나열하는 순서!
( [1, 2] === [2, 1] )
기본적인 조합 알고리즘 (for문)
let arr = [2, 3, 4, 5]
let result = [];
for (let a = 0; a < arr.length; a++) {
for (let b = a + 1; b < arr.length; b++) { // 다음순서부터 for문돌림 이야 아이디어 ...
for (let c = b + 1; c < arr.length; c++) {
result.push([arr[a], arr[b], arr[c]])
}
}
}
console.log(result)조합을 재귀 알고리즘으로!
let arr = [2, 3, 4, 5, 6, 7]
let result = [];
const recursion = (count, i, burket) => {
// base case
if (count === 0) {
result.push(burket)
return;
}
// for 문 한번 돌림
for (; i < arr.length; i++) {
let curEl = arr[i]
// rescursive case
recursion(count - 1, i + 1, burket.concat(curEl))
}
// 리턴
return result;
}
// 재귀 함수 실행한번 하고
recursion(3, 0, []);
console.log(result)GCD / LCM
Example) Mask States
방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)
최소공배수로 푸는 건 내가 아니가.. 이 문제가 왜 어디서 최소공배수인가?
세 명이 처음으로(최소로) 동시에(공통) 쉬는 시점 (배수 인이유는 쉬는 시점은 55분 그 다음 +55분 이런식인 배수의 패턴)
Example) 조명 설치
코드스테이츠 라운지에 있는 가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)
최소니까 최소 공배수 아니냐 ㄴㄴㄴ 평범한 함정임.
조명 개수를 최소로 해야하면 어떻게 해야할까? => 각 길이의 간격을 최대한 넓게해서 조명을 설치해야한다
=> 최대 공약수 생각해야함 ㅎ 나 천재임
멱집합
멱집합 문제가 트리문제는 아니지만 트리 비슷하게 사용할 수 있음!!
Exmaple) 멱집합 코드
let set = [1, 2, 3];
let result = [];
const sidePowerSet = (idx, subset) => {
// 재귀 함수이기 때문에 탈출 조건을 만듭니다.
if (idx === set.length) {
// 만약, idx와 result의 길이가 같다면(마지막까지 검토한 경우) result에 subset를 삽입하고 push합니다.
result.push(subset);
return;
}
// idx번째 요소가 포함되지 않는 경우
sidePowerSet(idx + 1, subset);
// idx번째 요소가 포함되는 경우
sidePowerSet(idx + 1, [...subset, set[idx]]);
};
// 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행합니다.
sidePowerSet(0, []);
console.log(result)끗!
