[230412] 즐겁지만 괴로운 알고리즘 (feat. 재귀함수)

Chapter 1 . 재귀함수 연습 + 복습 

어떠한 특정 조건에 걸려서 멈추기 전까지 계속 나를 부르는 재귀함수를 이용해서 다양한 예제를 연습해보았습니다. 

무한 츠쿠요미!

# Solve_flattenArr

* 함수 flattenArr을 재귀함수의 형태로 작성하여, 입력받은 다차원 배열을 1차원 배열로 리턴하세요. 
- Array Method flat(), flatMap() 사용 금지
- 반복문(for,while) 사용 가능.
- 원본 배열 변경 금지 
- 빈 배열을 입력 받은 경우는 빈 배열 리턴 

 

예시를 생각해보면 다음과 같이 입력을 받고 출력을 해야 합니다. 

1) 입력 : [ [1], 2, [3, 4], 5] 

2) 출력 : [ 1, 2, 3, 4, 5] 

 

 

배열 안에 배열이 있는 입력 이므로, 반복문으로 배열을 계속 (재귀) 돌다가 배열을 만나면 스프레드로 뿌려서 합쳐버릴 수 있게 만들 수 있습니다. ** 반복문 안에 요소가 배열일 경우와 배열이 아닐 경우로 구분하기 위해 배열을 구분해주는 Array.isArray() 메소드를 사용합니다. let result = []; 의 선언은 원본 배열을 해치지 않고 새로 생성한 result 배열 안에 1차원 배열을 집어 넣기 위해 생성했습니다. 저도 무의식중에 실수하는 것 이지만 result 배열은 재할당이 계속 일어나야 하므로 let으로 선언 하는 것을 주의해주세요. 

function flattenArr(arr) {
	// 1. 수행 조건 중 빈 배열을 입력 받은 경우, 빈 배열 리턴 
    if(arr.length === 0) {
    	return []; 
    }
    
    // 2. 반복문 
    let result = [];
    for( let i = 0 ; i < arr.length; i++){
    	// ** 요소가 배열이 아닐 경우, 
        if( !Array.isArray(arr[i]) ){
	//To DO
        }
        // ** 요소가 배열일 경우
        else{
	//To Do
        }
    }
}

 

 

이제 각각 조건안의 코드를 작성해봅시다. 요소가 배열이 아닌 경우는 그대로 새 배열에 push( )를 사용하여 넣어주면 됩니다. 

//생략
if( !Array.isArray(arr[i]) ){
	result.push(arr[i])
}

 

요소가 배열인 경우에는 해당 배열인 요소를 스프레드 메소드를 사용하여 새로운 배열에 똑같이 push( )로 넣어주면 됩니다. 다만 주의해야 할 점은 다차원 배열이 단순히 배열 안에 배열로 끝나는 것이 아니라 배열 안에 배열 안에 배열 안에... 이렇게 다중 중첩 되어있는 상태일 수도 있으니 이때 재귀함수 : 내가 만든 함수 flattenArr(arr) 로 계속 돌릴 수 있게 넣어주어야 합니다. 

//생략
else{
//const flatten = flattenArr(arr[i]); 
//위처럼 선언해서 push(...flatten)을 넣어주어도 됩니다. 
    result.push(...flattenArr(arr[i]));
}

return result

 

 

flattenArr 재귀함수는 요소를 계속 돌다가 더이상 배열 안에 배열인 요소가 없는 상태가 되면 첫 번째 if 문의 조건에 의해 종료되어 for 문을 빠져나오고 최종적으로 새로 만들어진 1차원 배열 result 를 return 함으로써 원하는 출력 값을 얻을 수 있습니다. 

 

 

Chapter 1-2 . 번외 - 코딩테스트 

※ 여기는 공부 중 - 추 후 업데이트 예정 ※

# 조합 

 

연습 : stackblitz

# reduce : 배열의 요소들을 앞 뒤로 누적해서 더하거나 곱할 수 있게 하기 

 

 

Chapter 2. Tree UI 구조 

이러한 Tree UI 구조일 경우 HTML에서 나열하는 것이 아닌 js 파일에서 DOM과 재귀함수를 통해 작성을 할수 있습니다. <ul> 구조 안에 <li> 안에 <input><span><ul> 의 구조가 반복되는 Tree 구조 입니다. "createTreeView()"를 재귀함수로 이용해서 원하는 만큼 html에 data의 구조를 나열할 수 있습니다. 

 

 

<ul>

.....┗ <li>....................음식

............┗ <input>

............┗ <span>     // menu[i].name

............┗ <ul>

....................┗ <li> ...<li>    // menu[i].children

.....┗<li>....................음료수

............┗ <input>

............┗ <span>     // menu[i].name

............┗ <ul>

....................┗ <li> ...<li>   

 

 

 

⇒ For문을 돌면서 각 구조의 DOM을 생성

const root = document.getElementById('root');

//currentNode : ul#root
function createTreeView(menu, currentNode) {

  for(let i = 0; i < menu.length; i++){
    const li = document.createElement('li');
    const ul = document.createElement('ul'); 
    const input = document.createElement('input');
    input.setAttribute('type', 'checkbox')
    const span = document.createElement('span'); 
    span.textContent = menu[i].name; 
    
  }

}

createTreeView(menu, root);

 

⇒ if문 조건으로 menu객체 안의 속성 값에 children이 존재할 때와 존재하지 않을 대로 구분 

** 따로 if문을 두지 않는다면 무한으로 UI 구조가 생성이 되겠죠. 이를 맊기 위해 menu 객체 안에 children이라는 속성이 없는 요소 (ex. 각 부분의 마지막 <li>)를 만나게 된다면 더이상 생성하지 않고 단순히 속성 값을 출력하라는 지시가 필요합니다. 

 for(let i = 0; i < menu.length; i++){
    //생략
    
    if(menu[i].children){  // menu[i]에 key가 children이 존재 할 때, 
      li.append(inputTag); 
      li.append(spanTag);
      li.append(ulTag);   
      createTreeView(menu[i].children, ul); 
    }
    else { // menu[i]에 key가 children이 존재하지 않을 때, 
      li.textContent = menu[i].name; // li태그의 콘텐츠에 menu[i].name만 넣기
    }
    currentNode.append(li); 
  }

제가 첫 번째로 풀었던 댕망진창 코드 ㅎㅎ

const root = document.getElementById('root');

//currentNode : ul#root
function createTreeView(menu, currentNode) {

  const span = document.createElement('span');
  const input = document.createElement('input');
  const ul = document.createElement('ul');


  for( let i = 0 ; i < menu.length; i++){
    // console.log(menu[i].name); //음료,음식,굿즈,카드
    const li = document.createElement('li');
  
    
    //base case
    if(menu[i].children){
      input.type = "checkbox";
      span.textContent = menu[i].name;
      li.appendChild(input);
      li.appendChild(span);
      // li.appendChild(ul);
      li.appendChild(createTreeView(menu[i].children, ul))
    }else {
      li.textContent = menu[i].name;
    }
    currentNode.append(li);
    
    // createTreeView(menu[i].children, ul);
    // ul.appendChild(createTreeView(menu[i].children), ul)


  
    // recursive case
    // if(menu[i].children === undefined){
    //   li.textContent = menu[i].name
      
    // }

  }
  return currentNode;

}

 

 

 

 

 

IF you want to learn more about the recursion, plus click the below link. 

⇒ Advanced 재귀함수