📌 재귀함수
자기 자신을 호출하는 함수를 말합니다.
중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 사용합니다.
재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한으로 반복합니다. 재귀함수로 작성되는 코드는 반복문으로도 작성할 수 있습니다.
function recursion() {
console.log("This is");
console.log("recursion!");
recursion();
}📌 조합(Combination)
◼ 조합 : 중복X, 순서X
서로 다른 n개의 원소, r개를 중복 없게, 순서에 상관없이 나열(nCr)
특징
선택 값 이후의 값만 선택해 중복이 없습니다.
// [1, 2, 3, 4, 5]이 주어지고 그 중 3개를 선택한다면 (5C3)
선택 값 : 1, 이후의 값 : [2, 3, 4, 5] 중 2개씩 조합
// [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5]
선택 값 : 2, 이후의 값 : [3, 4, 5] 중 2개씩 조합
// [2, 3, 4], [2, 3, 5], [2, 4, 5]
선택 값 : 3, 이후의 값 : [4, 5] 중 2개씩 조합
// [3, 4, 5]
선택 값 : 4, 이후의 값 : [5] 중 2개씩 조합
선택 값 : 5, 이후의 값 : [] 중 2개씩 조합예제
// for 반복문 사용 시
const list = [1, 2, 3, 4, 5];
function combination(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
// 다음 값(i + 1)부터 반복
for (let j = i + 1; j < list.length; j++) {
// 다음 값(j + 1)부터 반복
for (let k = j + 1; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
combination(list);
// 재귀함수 사용 시
const list = [1, 2, 3, 4, 5];
function combination(list, r) {
const result = [];
function arr(items, index) {
if (items.length === r) {
result.push(items);
return;
}
for (let i = index; i < list.length; i++) {
arr([...items, list[i]], i + 1);
}
}
arr([], 0);
return result;
}
combination(list, 3);
/*
[1, 2, 3], [1, 2, 4], [1, 2, 5],
[1, 3, 4], [1, 3, 5],
[1, 4, 5],
[2, 3, 4], [2, 3, 5],
[2, 4, 5],
[3, 4, 5]
*/
◼ 중복조합 : 중복O, 순서X
서로 다른 n개의 원소, r개를 중복 있게, 순서에 상관없이 나열
특징
동일한 값을 2회 이상 선택할 수 있기 때문에 [1, 1, 1]이 허용됩니다.
예제
// for 반복문 사용 시
const list = [1, 2, 3, 4, 5];
function combination(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = i; j < list.length; j++) {
for (let k = j; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
combination(list);
// 재귀함수 사용 시
const list = [1, 2, 3, 4, 5];
function combination(list, r) {
const result = [];
function arr(items, index) {
if (items.length === r) {
result.push(items);
return;
}
for (let i = index; i < list.length; i++) {
arr([...items, list[i]], i);
}
}
arr([], 0);
return result;
}
combination(list, 3);
/* 총 35가지 경우의 수
[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5],
[1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5],
[1, 3, 3], [1, 3, 4], [1, 3, 5],
[1, 4, 4], [1, 4, 5],
[1, 5, 5],
[2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 2, 5],
[2, 3, 3], [2, 3, 4], [2, 3, 5],
[2, 4, 4], [2, 4, 5],
[2, 5, 5],
[3, 3, 3], [3, 3, 4], [3, 3, 5],
[3, 4, 4], [3, 4, 5],
[3, 5, 5],
[4, 4, 4], [4, 4, 5],
[4, 5, 5],
[5, 5, 5]
*/📌 순열(Permutation)
◼ 순열 : 중복X, 순서O
서로 다른 n개의 원소, r개를 중복 없이, 순서에 상관있게 나열(nPr)
특징
선택 값 이외의 잔여 값을 모두 선택합니다.
순서가 중요합니다. 선택시 처음(0번째)부터 다시 반복합니다.
// [1, 2, 3, 4, 5]이 주어지고 그 중 3개를 선택한다면 (5P3)
선택 값 : [1], 잔여 값 : [2, 3, 4, 5] 중 2개씩 조합.
/*
[1, 2, 3], [1, 2, 4], [1, 2, 5],
[1, 3, 2], [1, 3, 4], [1, 3, 5],
[1, 4, 2], [1, 4, 3], [1, 4, 5],
[1, 5, 2], [1, 5, 3], [1, 5, 4] */
선택 값 : [2], 잔여 값 : [1, 3, 4, 5] 중 2개씩 조합.
/*
[2, 1, 3], [2, 1, 4], [2, 1, 5],
[2, 3, 1], [2, 3, 4], [2, 3, 5],
[2, 4, 1], [2, 4, 3], [2, 4, 5],
[2, 5, 1], [2, 5, 3], [2, 5, 4]
*/
선택 값 : [3], 잔여 값 : [1, 2, 4, 5] 중 2개씩 조합.
/*
[3, 1, 2], [3, 1, 4], [3, 1, 5],
[3, 2, 1], [3, 2, 4], [3, 2, 5],
[3, 4, 1], [3, 4, 2], [3, 4, 5],
[3, 5, 1], [3, 5, 2], [3, 5, 4]
*/
선택 값 : [4], 잔여 값 : [1, 2, 3, 5] 중 2개씩 조합.
/*
[4, 1, 2], [4, 1, 3], [4, 1, 5],
[4, 2, 1], [4, 2, 3], [4, 2, 5],
[4, 3, 1], [4, 3, 2], [4, 3, 5],
[4, 5, 1], [4, 5, 2], [4, 5, 3]
*/
선택 값 : [5], 잔여 값 : [1, 2, 3, 4] 중 2개씩 조합.
/*
[5, 1, 2], [5, 1, 3], [5, 1, 4],
[5, 2, 1], [5, 2, 3], [5, 2, 4],
[5, 3, 1], [5, 3, 2], [5, 3, 4],
[5, 4, 1], [5, 4, 2], [5, 4, 3]
*/예제
// for 반복문 사용 시
const list = [1, 2, 3, 4, 5];
function permutation(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
for (let k = 0; k < list.length; k++) {
// 중복된 요소 제거
if (i === j || j === k || k === i) continue;
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
permutation(list);
// 재귀함수 사용 시
const list = [1, 2, 3, 4, 5];
function permutation(list, r) {
const result = [];
// 내부함수 : filter나 splice로 중복 제거
function arr(items, rest) {
if (items.length === r) { // base condition
result.push(items);
return;
}
for (let i = 0; i < rest.length; i++) {
// 1. splice 메소드로 rest 배열 만들기
const temp = rest.slice();
temp.splice(i, 1);
// 2. filter 메소드로 rest 배열 만들기
// const temp = rest.filter((el, idx) => idx !== i);
arr([...items, rest[i]], temp);
}
}
arr([], list);
return result;
}
permutation(list, 3);
/*
[1, 2, 3], [1, 2, 4], [1, 2, 5],
[1, 3, 2], [1, 3, 4], [1, 3, 5],
[1, 4, 2], [1, 4, 3], [1, 4, 5],
[1, 5, 2], [1, 5, 3], [1, 5, 4],
[2, 1, 3], [2, 1, 4], [2, 1, 5],
[2, 3, 1], [2, 3, 4], [2, 3, 5],
[2, 4, 1], [2, 4, 3], [2, 4, 5],
[2, 5, 1], [2, 5, 3], [2, 5, 4],
[3, 1, 2], [3, 1, 4], [3, 1, 5],
[3, 2, 1], [3, 2, 4], [3, 2, 5],
[3, 4, 1], [3, 4, 2], [3, 4, 5],
[3, 5, 1], [3, 5, 2], [3, 5, 4],
[4, 1, 2], [4, 1, 3], [4, 1, 5],
[4, 2, 1], [4, 2, 3], [4, 2, 5],
[4, 3, 1], [4, 3, 2], [4, 3, 5],
[4, 5, 1], [4, 5, 2], [4, 5, 3],
[5, 1, 2], [5, 1, 3], [5, 1, 4],
[5, 2, 1], [5, 2, 3], [5, 2, 4],
[5, 3, 1], [5, 3, 2], [5, 3, 4],
[5, 4, 1], [5, 4, 2], [5, 4, 3]
*/◼ 중복순열 : 중복O, 순서O
서로 다른 n개의 원소, r개를 중복 있게, 순서에 상관있게 나열
특징
동일한 값을 2회 이상 선택할 수 있기 때문에 [1, 1, 1]이 허용됩니다.
처음에 n개를 선택하고, 그 다음에 또 n개를 선택할 수 있기 때문에 총 경우의 수가 n^r이 됩니다.
예제
// for 반복문 사용 시
const list = [1, 2, 3, 4, 5];
function permutation(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
for (let k = 0; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
permutation(list);
// 재귀함수 사용 시
const list = [1, 2, 3, 4, 5];
function permutation(list, r) {
const result = [];
function arr(items) {
if (items.length === r) {
result.push(items);
return;
}
for (let i = 0; i < list.length; i++) {
arr([...items, list[i]]);
}
}
arr([]);
return result;
}
permutation(list, 3);
/* 총 125가지 경우의 수
[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5],
[1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5],
[1, 3, 1], [1, 3, 2], [1, 3, 3], [1, 3, 4], [1, 3, 5],
[1, 4, 1], [1, 4, 2], [1, 4, 3], [1, 4, 4], [1, 4, 5],
[1, 5, 1], [1, 5, 2], [1, 5, 3], [1, 5, 4], [1, 5, 5],
[2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 1, 4], [2, 1, 5],
[2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 2, 5],
[2, 3, 1], [2, 3, 2], [2, 3, 3], [2, 3, 4], [2, 3, 5],
[2, 4, 1], [2, 4, 2], [2, 4, 3], [2, 4, 4], [2, 4, 5],
[2, 5, 1], [2, 5, 2], [2, 5, 3], [2, 5, 4], [2, 5, 5],
[3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 1, 4], [3, 1, 5],
[3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 2, 4], [3, 2, 5],
[3, 3, 1], [3, 3, 2], [3, 3, 3], [3, 3, 4], [3, 3, 5],
[3, 4, 1], [3, 4, 2], [3, 4, 3], [3, 4, 4], [3, 4, 5],
[3, 5, 1], [3, 5, 2], [3, 5, 3], [3, 5, 4], [3, 5, 5],
[4, 1, 1], [4, 1, 2], [4, 1, 3], [4, 1, 4], [4, 1, 5],
[4, 2, 1], [4, 2, 2], [4, 2, 3], [4, 2, 4], [4, 2, 5],
[4, 3, 1], [4, 3, 2], [4, 3, 3], [4, 3, 4], [4, 3, 5],
[4, 4, 1], [4, 4, 2], [4, 4, 3], [4, 4, 4], [4, 4, 5],
[4, 5, 1], [4, 5, 2], [4, 5, 3], [4, 5, 4], [4, 5, 5],
[5, 1, 1], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 1, 5],
[5, 2, 1], [5, 2, 2], [5, 2, 3], [5, 2, 4], [5, 2, 5],
[5, 3, 1], [5, 3, 2], [5, 3, 3], [5, 3, 4], [5, 3, 5],
[5, 4, 1], [5, 4, 2], [5, 4, 3], [5, 4, 4], [5, 4, 5],
[5, 5, 1], [5, 5, 2], [5, 5, 3], [5, 5, 4], [5, 5, 5]
*/