아직 재귀의 원리에 대해 정확히 숙지하고 있지 않아, 쓸 때마다 헷갈린다.
최근에 풀었던(페어분이) 재귀 관련 문제를 정리해보았다.
rockPaperScissors
문제
가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.
입력
- 없음
출력
- 2차원 배열(arr[i])을 리턴해야 합니다.
- arr[i]는 전체 경우의 수 중 한 가지 경우(총 세 번의 선택)를 의미하는 배열입니다.
- arr[i]는 'rock', 'paper', 'scissors' 중 한 가지 이상을 요소로 갖는 배열입니다.
- arr[i].length는 3
주의사항
- 최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
- 중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.
- 쉽게 생각해 올림픽 순위 결정 방식을 참고하면 됩니다.
- 금메달('rock')이 은메달('paper')보다 우선하고, 은메달('paper')이 동메달('scissors')보다 우선합니다.
입출력 예시
let output = rockPaperScissors();
console.log(output);
/*
[
["rock", "rock", "rock"],
["rock", "rock", "paper"],
["rock", "rock", "scissors"],
["rock", "paper", "rock"],
// ...etc ...
]
*/Advanced
- 가위바위보 게임의 수를 나타내는 양의 정수 rounds가 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 리턴하도록 함수를 작성해 보세요.
let output = rockPaperScissors(5);
console.log(output);
/*
[
["rock", "rock", "rock", "rock", "rock"],
["rock", "rock", , "rock", "rock", "paper"],
["rock", "rock", , "rock", "rock", "scissors"],
["rock", "rock", "rock", "paper", "rock"],
["rock", "rock", "rock", "paper", "paper"],
["rock", "rock", "rock", "paper", "scissors"],
["rock", "rock", "rock", "scissors", "rock"],
// ...etc ...
]
*/< CODE >
//################################< Advanced >##################################
const rockPaperScissors = function (rounds) {
rounds = rounds || 3;
const rps = ['rock', 'paper', 'scissors'];
const outcomes = [];
// 재귀 -> 배열의 모든 요소의 경우의 수를 훑기 위한 적절한 방법
let permutate = function (roundsToGo, playedSoFar) {
if (roundsToGo === 0) { // rounds가 0일 경우 outcones 배열에 삽입하고, 재귀에서 빠져나옴(base case)
outcomes.push(playedSoFar);
return;
}
for (let i = 0; i < rps.length; i++) { // rpg 배열 한 번 씩 순회하며 i번째 요소 변수에 담음
let currentPlay = rps[i];
permutate(roundsToGo - 1, playedSoFar.concat(currentPlay)); //(recursive case)
/**
* 처음 실행된 반복문은 rps를 전부 순회해야 끝이 남.
* 그러나 한 번 반복할 때마다 permutate 함수가 실행되고, rounds의 숫자는 짧아지며, playedSoFar에 요소가 계속 쌓일 것
* 결국, roundsToGo가 0이 될 때까지 이 반복문은 rps[i]가 0일 것이며, playedSoFar에는 [rock, rock, rock]이 되어 outcones에 Push하고, 종료하게 된다.
* return이 되었으니, 한 번의 재귀 호출이 끝. 마지막 호출 바로 전으로 돌아가,
* for문은 i = 1을 가리키게 될 것이고, [rock, rock, paper]을 삽입한 뒤 호출을 하게 됨.
* roundsToGo가 0이 되어, 해당 배열은 outcomes 배열에 삽입됨.
* 모든 호출의 반복문이 끝날 때까지 반복하며 outcomes에 경우의 수 요소들이 담기게 된다.
*/
}
};
permutate(rounds, []); // 최초 함수 실행(빈 배열과 함께)
return outcomes;
};
//################################< Basic >##################################
const rockPaperScissors = function () {
const rps = ['rock','paper','scissors'];
const rounds = 3;
const count = 0;
const outcomes = [];
const permutate = (count, playedsoFar) => {
if(rounds === count) {
outcomes.push(playedsoFar)
return;
}
permutate(count+1, playedsoFar.concat(rps[0])
permutate(count+1, playedsoFar.concat(rps[1])
permutate(count+1, playedsoFar.concat(rps[2])
}
permutate(count, []);
return outcomes;
}< POINT >
🔰 (for Advanced) 함수의 인자에 특정 값이 주어졌을 시 그 값을 그대로 쓰고, 아닐시 기본값을 할당해주기 위해
|| (true를 만나면 바로 실행하는 특성)연산자 활용function rockPaperScissors (rounds) { rounds = rounds || 3 ...}🔰 세가지 경우의 수(가위, 바위, 보)를 를 배열(rpg)에 담아두고, count변수와 (Advanced시 rounds로 진행 가능) 결과를 담을 배열(outcomes) 선언.
🔰 count와 진행하는 배열을 인자로 받아
count === rounds가 될 때(Advanced: rounds === 0) ourcomes에 진행중인 배열을 푸쉬 ->base case,
아니면 count+1 (/rounds - 1) 시키며 진행 중인 배열에 rpg의 요소 중 순서대로 하나씩 concat 한 후 재귀 -> recursive case🔰 concat을 사용 : push 같은 경우엔 반환값이 length이고, concat은 반환값이 배열이다.
재귀가 어떻게 이루어지고 있는지 헷갈려서 직접 돌려보았다.(새창에서 열기하면 원본으로 보임)
중간중간 캡쳐한 것이라 처음부터는 X
재귀 과정 중 count가 3 - 2 반복하며 마지막 인덱스 요소들 3개가 차례로 순환하며 만들어진 배열들이 모두 리턴되면 비로소 두번째 요소가 한번 순환, 두번째 요소의 재귀호출 밑의 재귀 호출이 진행되어 두번째 요소의 다음 값 삽입 후 호출, ..마지막 인덱스 요소 값 순환 반복
(ex> ["paper","rock","sicissor"]->["paper","rock"] -> ["paper"] -> ["paper","paper"]->["paper","paper","rock"] - 밑에서 두번째 캡쳐화면 참고- )
마지막에는 만들어진 배열 리턴 후 ["s","s","s"] -> ["s","s"]-> ["s"] -> [] 순으로 회귀하며 끝난다.
인덱스마다 세가지 선택의 경우의 수가 있는데, 시작 순서대로 각각 한가지 선택할때마다 3가지의 귀속된 경우의 수가 붙는다.
-> 순열 관련 문제인데 재귀를 응용해서 푸는 것이었다.
순열 : n 개 중에서 일부만을 선택하여 나열하는 것(순서를 지키며 나열)
집밥이 그리워
문제
김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.
밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.
입력
인자 1: sideDishes
- String 타입의 영문으로 된 반찬이 나열되어 있는 배열
출력
- Array 타입을 리턴해야 합니다.
- 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수가 담긴 배열
주의사항
- 반찬은 영문으로 작성이 되어 있습니다.
- 반찬은 중복되지 않습니다.
- 반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
- 반찬은 3개 이상 99개 이하입니다.
- 출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다.
입출력 예시
let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
console.log(output);
/*
[ [],
[ 'eggroll' ],
[ 'eggroll', 'fishSoup' ],
[ 'eggroll', 'fishSoup', 'kimchi' ],
[ 'eggroll', 'kimchi' ],
[ 'fishSoup' ],
[ 'fishSoup', 'kimchi' ],
[ 'kimchi' ]
]
*/< CODE >
function missHouseMeal(sideDishes) {
// 결과를 담을 배열을 선언
let result = [];
// sideDishes를 사전식 순서로 정렬
sideDishes.sort();
// 모든 조합을 검사하는 재귀 함수
const sidePowerSet = (idx, sideDish) => {
// 탈출 조건
if (idx === sideDishes.length) {
// 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push
result.push(sideDish);
return;
}
// idx번째 요소가 포함되지 않는 경우
sidePowerSet(idx + 1, sideDish);
// idx번째 요소가 포함되는 경우
sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
};
// 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행
sidePowerSet(0, []);
// 결과를 사전식 순서로 정렬
return result.sort();
}< POINT >
🔰 inner 재귀가 하는 일: 주로 idx를 3까지 올려주는 역할. 인자는 계속 받은 그대로
🔰 outer 재귀가 하는 일: 실질적으로 배열에 값 넣어주는 역할. 리턴 후 inner에서 회귀되어 밑으로 내려오면 그 값과 인덱스값 함께 갖고 재귀 호출
멱집합 : 어떤 집합의 모든 부분집합
나열 방법에서 단계를 나누는 기준은 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지
임의의 원소를 제외하면서 집합을 작은 단위로 줄여나간다.
헷갈린 부분 : 차례대로 sideDishes의 요소들 훑어보며 중복되지 않은 부분집합들 만들어 리턴..해야할 것 같은디 어떻게 빈배열부터 쭉 리턴시킬수있을까?
👉 일단 sort 시키고, 맨 밑에서 인덱스와 진행 중인 배열을 인자로 받는 재귀를 돌린다. ( 0, [] 부터 시작) idx === sideDishes.length 되면 탈출조건이므로 리턴
👉 inner / outer재귀 선언, inner로 idx를 올리고 outer로 직전 요소와 새로운 요소 담은 배열 재귀(멱집합 개념에 따라)
result에 들어갈 수 있는 배열 요소들
1. outer에서 결합한 요소들 담은 배열
2. inner에서 idx 만족시 리턴된 배열 (inner에서만 돌리다가/ outer에서 결합한 요소들에 idx올려서)
