반복전략

반복전략은 수 많은 데이터를 가지고 동일한 연산을 수행 할 때 쓸 수 있는 전략입니다.
반복을 탈출 조건을 만족 할 때까지 반복하여 원하는 결과값을 얻는 전략입니다.

예를 들어 바닷물고기 리스트와 민물고기 리스트가 각각 가나다순으로 정렬되어 있다고 해봅시다. 이 것을 모두 합하여 가나다순으로 정렬해 물고기 리스트를 만들고 싶습니다. 이 것을 어떻게 해결할까요?
다음과 같은 반복전략을 통해 해결 할 수 있습니다.

반복할 절차는 다음과 같습니다.
1. 바닷물고기 리스트와 민물고기 리스트중 빈 것이 있는지 확인합니다.
2. 빈 것이 있을 경우에는 비어있지 않은 것의 제일 앞에 있는 원소를 물고기리스트에 추가합니다.
2-1. 비어있지 않은 리스트에서는 해당 원소를 삭제합니다.
3. 빈 것이 없을 경우에는 바닷물고기 리스트와 민물고기 리스트중 제일 앞에 있는 것들을 가나다순으로 비교합니다.
3-1. 비교한 것중 앞선 것을 해당 리스트에서 삭제합니다.
3-2. 삭제한 원소를 물고기 리스트에 추가합니다.
탈출조건은 다음과 같습니다.
1. 바닷물고기 리스트와 민물고기 리스트가 모두 비면 반복을 끝내고 물고기 리스트를 return합니다.

이것을 javaScript코드로 코딩하면 다음과 같다.

function merge(sea, fresh){
	const result = [];
    
    while(!(sea.length===0&&fresh.length===0)){
    	
        if(sea.length===0||fresh.length===0){
        	if(sea.length===0){
            	result.push(fresh[0]);
                fresh.shift();
            }else{
            	result.push(sea[0]);
                sea.shift();
            }
		}else{
        	if(sea[0]<fresh[0]){
        		result.push(sea[0]);
            	sea.shift();
        	}else{
        		result.push(fresh[0]);
            	fresh.shift();
        	}
        }
	}
    return result;
}

이러한 반복전략을 이용해 멱집합을 구할 수도 있습니다. 멱집합을 구하기 위해서는 중첩 루프를 이용합니다.

반복할 절차는 다음과 같습니다.
1. powerset을 복사합니다.
2. 복사한 powerset에 새로운 원소를 추가합니다.
3. 2에서 만들어진 powerset과 기존 powerset을 합쳐 새로운 Powerset을 만듭니다.
탈출조건은 다음과 같습니다.
1. 멱집합을 만들 집합의 모든 원소에 대해서 위 반복절차를 시행하면 반복을 그만둡니다.

이것을 javascript로 코딩하면 다음과 같습니다.

	function powerSet(set){                   //집합을 입력받아 멱집합을 만드는 함수.
    const powS=new Set();
    powS.add(new Set());
    for(let item of set){
        const setClone = cloneSet(powS);
        for(let el of setClone){
            el.add(item);
            powS.add(el);
        }
    }
    console.log(powS);
}
 
function cloneSet(set) {                      //집합을 깊은 복사하는 함수. 
    const clone = new Set();
    for (let item of set) {
      if (typeof item=== "object" && item != null) {
        clone.add(cloneSet(item));
      } else {
        clone.add(item);
      }
    }
  
    return clone;
}

참고자료
1. 한 권으로 그리는 컴퓨터과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루, 옮긴이 : 박연오, p72-76
2. 깊은 복사 함수