[ 오늘의 TODO ]
코드 스테이츠) 목 내용 복습// 수학을 이용한 알고리즘 문제- 패스트 캠퍼스) 인강 3개 이상 듣기 // optional
생활) 물 1L 이상 마시기
[ 오늘의 복습 ]
오늘 복습할 내용은 고등학생 때 배운 수학 문제를 코딩으로 구현해보는 과정이다. 전체적인 방향은 개념에 대한 기본적인 설명과 코드로 구현하는 방법에 대해 배워보겠다. 이때, 코드는 지금 일반적으로 구글링하면 나오는 코드를 구현하고, 코드 스테이츠에서 자체적으로 제공해주는 코드는 언급하지 않겠다.
1. 순열
보자기 안에 가, 나, 다, 라, 마 한글이 적힌 카드가 들어가 있다. 눈을 감고 보자기에서 카드를 총 세 장 꺼낼 때, 순서대로 꺼내는 모든 경우의 수를 구해보도록 하자.
중요한 포인트는 순서를 생각하지 않는다는 것이다. 이 말은 처음에 '가', '나', '다' 를 뽑는 경우의 수와 '나', '가', '다' 를 뽑는 경우의 수를 다르게 본다는 의미다.
먼저, 순열을 구하는 코드는 다음과 같다.
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const rest = callback.filter((x, idx) => idx !== i)
const recursive = recursion(rest, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
// 코드 해석
// arr 는 보자기 안에 담겨있는 모든 카드들을 배열에 담은 것이다
// choiceNum 은 몇 번을 뽑을 것인지를 의미한다.
// base case 인 choiceNum === 1 은 마지막으로 카드를 뽑는 순간을 의미한다
// arr.forEach 는 카드를 한 장 뽑는 모든 경우의 수를 의미한다.
// 즉, 보자기(arr) 안에 카드가 가, 나, 다 카드(arr의 요소)만 남았다고 한다면
// 가 카드를 뽑았을 경우, 나 카드를 뽑았을 경우, 다 카드를 뽑았을 경우
// 각 경우를 한 번 씩 찾아보는 행위를 forEach 로 하고
// 뽑은 카드를 fixed 에 넣는다
// rest 는 카드를 뽑고 보자기에 남은 카드들을 배열로 만든 것이다.
// filter 를 통해 뽑은 카드를 제거했다.
// recursive 는 카드를 뽑은 후 남아있는 카드들끼리 다시 한 번 뽑는 행위를 의미한다.
// choiceNum 이 뽑는 행위를 몇 번할 것인를 가리키므로 -1을 해준다.
// 내가 카드를 한 장 뽑고 뒤에 나오는 모든 경우의 수를 결합하는 것이다.
// 이 부분이 이해가 안 간다면 재귀를 다시 한 번 공부해보거나 디버깅을 해보는 것이 좋다.
// 이 로직에서 재귀의 핵심은 choiceNum이 1인 (마지막으로 카드를 뽑는 지점) base case 까지 도달해서
// someChoiceNum (우리가 뽑기로 한 카드) 까지 되돌아오며 Return 한다는 점이다
// 헷갈리지 말아야할 것은 base case 까지 찍고 되돌아오는 건 맞지만
// base case 에 찍힌 것이 가장 먼저 뽑은 카드가 아니라 가장 마지막에 뽑은 카드라는 점이다.
가, 나, 다, 라, 마 카드를 순서를 고려해서 뽑는 로직은 다음과 같다.
const bag = ['가', '나', '다', '라', '마']
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const rest = callback.filter((x, idx) => idx !== i)
const recursive = recursion(rest, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
const answer = recursion(bag, 3).map((el) => el.join(''))
console.log(answer)
2. 조합
조합은 순열과 다르게 순서를 따로 고려하지 않는 경우다. 즉, 위에서는 순서를 고려해 '가나다' 와 '나가다' 를 다른 경우의 수로 보았다. 순서가 중요하기에 첫 번째 뽑은 가 와, 두 번째 뽑은 가 는 다르기 때문이다. 그러나 조합에서는 이 둘을 같은 경우로 본다. 즉, '가나다', '가다나', '나가다', '나다가', '다가나', '다나가' 이 모든 경우는 다 같은 경우인 것이다.
순열과 조합은 로직이 비슷한데 딱 한 곳만 고치면 된다. 바로 rest 부분이다. 아이디어는 이거다. 위에서 여섯 가지의 경우가 모두 같은 경우라고 본다면, 우리는 저걸 모두 묶어 '가나다'만을 출력하면 된다. 그렇다면 '가나다'를 뽑았는데 '나가다'를 뽑지 않게 할 방법은? '가나다'를 뽑았으면 '나'를 뽑을 때 '가'는 전혀 신경쓰지 않고 뽑으면 된다. 즉 '나' 카드를 뽑고 그 이후에 카드를 뽑을 때 '나' 이전에 존재했던 '가'를 뽑지 않도록 만든다는 것이다. 왜냐하면 '가' 와 '나' 가 함께 쓰이는 경우의 수는 이미 '가'에서 처리했기 때문이다. 뽑는 순서를 생각해보면 forEach 때문에 '가' => '나' => '다' 로 배열의 요소를 탐색할 것이다. 그렇기에 '가'를 탐색한 순간에 '가'와 '나'가 함께 조합되는 경우의 수가 이미 들어간 거고, 이후 '나'를 탐색할 때는 '가'와 '나'가 결합하는 경우의 수는 이미 '가' 를 탐색할 때 찾아냈으므로, '가'를 고려하지 않는다는 것이다.
이를 코드로 구현하면
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const rest = callback.slice(i+1)
const recursive = recursion(rest, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
return recursion(someArr, someChoiceNum)
}
// callback.slice(i+1) 을 통해서 i 이전의 수는 고려하지 않는다는 걸 보여준다.
이제 보자기 안에 담겨있는 카드를 순서에 상관없이 조합하는 경우의 수를 구하자면
const bag = ['가', '나', '다', '라', '마']
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const rest = callback.slice(i + 1)
const recursive = recursion(rest, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
const answer = recursion(bag, 3).map((el) => el.join(''))
console.log(answer)
3. 중복 순열
중복 순열이란 순서는 고려하나 한 번 뽑았던 것도 다시 뽑을 수 있는 경우를 의미한다. 즉, 보자기 안에 가, 나, 다, 라, 마 가 있고 그 안에 가를 뽑는다고 했을 경우, 그 카드를 빼 놓는 것이 아니라 다시 보자기에 넣어서 카드를 뽑는 것을 뜻한다.
이것도 rest 의 문제다. 우리는 순열 코드에서 filter 를 통해 뽑았던 카드를 제거했다. 하지만, 중복 순열에서는 그 카드를 제거하지 않으면 된다.
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const rest = callback
const recursive = recursion(rest, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
return recursion(someArr, someChoiceNum)
}
// 리팩토링 1차 : rest 선언을 따로 없앤다.
const recursion = (arr, choiceNum) => {
let result = []
if (choiceNum === 1) return arr.map((el) => [el])
arr.forEach((fixed, i, callback) => {
const recursive = recursion(callback, choiceNum - 1)
const combine = recursive.map((el) => [fixed, ...el])
result.push(...combine)
})
return result
}
return recursion(someArr, someChoiceNum)
}
// 리팩토링 2차: 만약 arr 에 대한 선언과 할당이 외부 스코프에 존재하는 경우
// 원본 배열에 아무런 영향을 주지 않는 순수함수 이므로 이런 로직이 가능하다.
const recursion = (choiceNum) =>{
let result = []
if(choiceNum === 1) return arr.map(el => [el]);
arr.forEach((fixed) => {
const recursive = recursion(choiceNum-1)
const combine = recursive.map(el => [fixed, ...el])
result.push(...combine)
})
return result
}
4. 멱집합
멱집합이란 모든 부분집합을 의미한다. {1, 2, 3} 이 있을 경우, [ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} ] 이 멱집합이 된다. 멱집합을 구할 때에 중요한 점 첫 번째는 멱집합을 구할 때 {1, 2} 든 {2, 1} 이든 상관이 없다는 점이다. 이 부분은 우리가 조합할 때 생각했던 것과 유사하게 생각하면 될 것 같다.
멱집합 만드는 자세한 설명은 일단 로직을 보면서 해보겠다. 다음의 설명은 내가 내 페어 분에게 이 멱집합에 관한 로직을 설명할 때 썼던 주석들을 갖고 왔다.
function powerSet(arr) {
// check표시 해줄 배열
// check 란 이 요소를 넣을 것인가 말 것인가를 체크하는 거라 생각하면 된다.
let check = new Array(arr.length).fill(0)
// 부분집합 최대 length : 자기 자신.
// {1, 2, 3}
// check 는 무엇인가?
// check 는 이 요소가 부분집합에 들어가게 할 것인가 말 것인가를 판정하는 것이다
// 0 대신 false
// 1 대신 true 를 사용해도 된다.
// depth 가 arr.length 가 되면 부분집합으로 리턴한다.
// [0, 0, 0] => depth 0
// [0, 0, 0]
// [0, 0, 0]
// [0, 0, 0] => 공집합 {}
// [0, 0, 1] => {3}
// [0, 1, 0]
// [0, 1, 0] => {2}
// [0, 1, 1] => {2, 3}
//
// [1, 0, 0] => depth
// [1, 0, 0] => depth 2
// [1, 0, 0] => depth 3 => {1}
// [1, 0, 1] => depth 3 => {1, 3}
// [1, 1, 0] => depth 2
// [1, 1, 0] => depth 3 => {1, 2}
// [1, 1, 1] => depth 3 => {1, 2, 3}
// {}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
let powerSetArr = []
const dfs = (depth) => {
// ? check에 1인 index와 같은 index에 있는 arr만 filter해서 넣어준다.
if (depth === check.length) {
powerSetArr.push(arr.filter((v, idx) => check[idx]))
} else {
// ! 포함되는 경우
check[depth] = 1
dfs(depth + 1)
// ! 포함되지 않는 경우
check[depth] = 0
dfs(depth + 1)
}
}
dfs(0)
return powerSetArr
}
이런 로직 말고도 다른 로직이 존재했다.
// [1, 2, 3]
// [] => 공집합
// [1], [2], [3]
// [1, 2], [1, 3], [2, 3]
// [1, 2, 3]
// i = 0 => dfs(1, [1])
// res.push([1])
// i = 1 => dfs(2, [1, 2])
// res.push([1, 2])
// i = 2 => dfs(3, [1, 2, 3])
// res.push([1, 2, 3])
// i = 2 => dfs(2, [1, 3])
// res.push([1, 3])
// i = 1 => dfs(2, [2])
// res.push([2])
// i = 2 => dfs(3, [2, 3])
// res.push([2, 3])
// i = 2 => dfs(3, [3])
// res.push([3])
const subsets = (nums) => {
const result = [];
const dfs = (start = 0, arr = []) => {
result.push(arr);
for (let i = start; i < nums.length; i++) {
dfs(i + 1, [...arr, nums[i]]);
}
};
dfs();
return result;
};
말로 설명하면서 보여드렸을 때 페어 분께서 잘 이해해주셨는데.. 말없이 글만 쓰니 잘 이해가 되실지는 모르겠다.
'코드스테이츠 > 코드스테이츠 @ 개발 복습' 카테고리의 다른 글
| [코드 스테이츠] 90일차, "13주차 복습 (1)" (0) | 2021.10.16 |
|---|---|
| [코드 스테이츠] 85일차, "12주차 복습 (3)" (0) | 2021.10.11 |
| [코드 스테이츠] 83일차, "12주차 복습 (1)" (0) | 2021.10.09 |
| [코드 스테이츠] 63일차, "9주차 복습 (2) - Redux" (0) | 2021.09.19 |
| [코드 스테이츠] 62일차, "9주차 복습 (1) - Styled-Component, useRef" (0) | 2021.09.18 |