05

반복의 횟수가 정해져있지 않을때

재귀함수 작성

재귀는 일단 안에서 한번 호출되므로 똑같은 메서드 안에 작성

recursive case

현재 내가 선택가능한 경우의 수가 무엇이냐 -> for loop
매 순간마다 선택의 경우의 수가 달라질 수 있음 -> 선택 여부를 표현하는 데이터

선택하는 과정에서 재귀호출이 일어난다

언젠가는 끝나야 한다
기저단계, base case
순서 - 가위바위보 판수

호출하고 나면 판수 - 1

판수가 0일때 끝난다

알고싶은것, 구하려고 하는 것에 대한 적절한 조치를 취해준다
결과 데이터에 추가할 수도 있고, 아니면 더할 수도있고

만들고싶은것 String배열의 ArrayList
재귀함수 호출시 요소로 outcomes 추가

내가 지금까지 내온것을 저장하는 playedsofar
재귀함수 호출시 요소로 new String[]{} 추가
마지막 탈출시 playedsofar를 outcomes에 추가해준다

현재 호출(판, 라운드, 경로, 위치, 현재단계)에서 가능한 선택 중에서
1번째 선택인 것을 담을 concatArray추가하고
첫번째 값을 concatArray에 추가

재귀함수 선언(){
base case
if(//이러면 끝나는 조건) {
// 할 수 있는거 다해보고 여기까지 왔다
// 무적권 리턴
// 리턴할 때 해야할 게 있나???
}

recursive case
for (int i = 0, i < 선택의 총 개수; i++) {
// i번째를 선택했다
// 지금 몇번째 순서인지 지금까지 선택한 정보가 필요한 것은 아닌지 등을 고려해서
// 파라미터를 고려한다
재귀함수()

}
}

06

public permutation (int chosenNum, Integer[] bucket, ArrayList freshArr, ,boolean[] isUsed, ArrayList)

if (choiceNum == 0) {
result.add(bucket)
return;
}

//recursive case
// 이미 선택한 것, 즉 choiceNum + 1에서 선택된 것을 어떻게 알지?
for (int i = 0; i < 3; i++) {
// 선택할 수 있는것만 선택하자
if(isUsed[i] == false) {
isUsed[i] = true;
permutation(choiceNum - 1, isUsed)
// 원복
isUsed[i] = false;
}
}

• 재귀 실행 과정

isUsed = [false, false, false];

permutation(3)

0 permutation(2) isUsed = [true, false, false];
			0 SKIP
            1 permutation(1) isUsed = [true, true, false];
            			0 SKIP
                        1 SKIP
                        2 permutation(0) isUsed = [true, true, true]; 
                        => 탈출 => **단계의 구분(원복)** => 바로 이전의 (2) 실행
            (2)
(1) 
(2)

• 반복문에만 집중해라
• 개괄적인 템플릿을 천천히 완성해나가는 식으로
• 순열 10개는 300만을, 11개는 4천만, 12-> 시간제한이 거의 걸리게 되어있음
  -> 시간제한이 거의 무조건 걸림 -> 탐색공간을 획기적으로 줄이는 방법 필요

07

• 조합은 대략 27개를 넘어가면 1억이 넘어간다 -> 그 이상은 시간제한이 걸린다

// 무엇을 구할 것인가 -> 재귀 함수의 리턴 타입
public RETURN_TYPErecursive() {

재귀의 수도 템플릿

public RETURN_TYPE recursive(재귀호출을 하면서, 즉 게임을 진행하면서 필요한 정보들을 선언) {
    // base case
    // 더 이상 경우의 수가 없거나
    // 목적을 달성했거나
    // 세상의 끝에 도달했거나
    if (끝이다) {
      // 항상 리턴
      // 이때 어떤 조작을 하고 싶은지에 따라 코드가 추가된다.
      // 예. 결과 배열에 지금까지의 결과를 add한다 등
      // 예. 하나 찾았으니까 정답에다가 1 더한다.
      return
    }


    // recursive case
    // 현재 호출 (상태, 라운드, 순서, idx, 남아있는 경우)
    // 현재에서 선택 가능한 경우를 모조리 검토
    // 거의 대부분 반복문으로 구현된다

    // 선택 가능한 경우가 항상 같다면 (ex. 가위바위보) -> so Simple
    // 선택 가능한 경우가 매번 바뀐다면 그 정보가 필요하다 -> flag (ex. isVisited, isUse)
    for (let i = 0; i < 선택의길이; i++) {
      // 선택을 해도 되는지 검사할 필요가 있으면 해야지
      if (선택해도 된다면) {
        // 선택을 하자
        // 선택을 했으니까 이건 내가 찜했다고 표시해야지 -> flag
        isUsed[i] = true;
        // 선택이 끝났으니까 다음 호출(라운드, 순서, idx)로 넘어가야지
        recursive()
        // 다음라운드 갔다가 돌아왔으니까
        // 현재 라운드 마저 해볼까?
        // 아까 건드렸던거 다시 원복해야지
        isUsed[i] = false;
      }

    }

  }