lowerbound & upperbound

이분탐색은 정렬된배열에서 특정 값을 찾을때 유용하다.
이때 특정 값이 아니라 특정 값 이상을 찾아야 한다면, 이분탐색에서 살짝 변형이 필요하다.
그때 사용 하는 것이 lowerbound다.

lowerbound

시작 0, 끝을 배열의 길이로 둔다.

이후 찾는 값이 mid보다 크면 시작에 mid + 1, 찾는 값이 mid와 같거나 더 작으면 끝에 mid를 할당한다.

const lowerbound = (target,arr) => {
        let start = 0
        let end = arr.length
        while(start < end){
            const mid = Math.floor((start+end)/2);
            if(target > arr[mid]){
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
 }

upperbound

lowebound가 특정 값 이상을 찾는 알고리즘이라면 upperbound는 특정 값 초과를 찾는 알고리즘이다.

딱 하나 바뀐게 있다면, 부등호를 잘 보시라.
찾는 값이 mid이상이라면, 시작값에 mid + 1 아니라면 끝에 mid를 할당한다.

const upperbound = (target,arr) => {
        let start = 0
        let end = arr.length
        while(start < end){
            const mid = Math.floor((start+end)/2);
            if(target >= arr[mid]){
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return end;
 }

---

combination & permutation

조합과 순열. 확통시간에 많이 배웠다. 둘의 차이점은 무얼까?

• 조합(combination) : 순서가 상관없다. => [1,4]와 [4,1]은 순서가 다르지만 같은 값이다.
• 순열(permutation) : 순서가 상관있다. => [1,4]와 [4,1]은 순서가 다르기에 다른 값이다.

combination

const combination = (arr, k) => {
	const results = [];
	if (k === 1) return arr.map((el) => [el]); // 종료조건
	arr.forEach((currentEl, i, _arr) => {
		const nextComb = combination(_arr.slice(index + 1), k - 1); //현재 원소 다음원소부터 조합!
		const combinations  = nextComb.map((_combination) => [currentEl, ..._combination]); //현재 원소 다음원소부터 조합한 배열에, 현재 원소를 첫 원소로 삽입한다.
		results.push(...combinations);
	});

	return results;
};

permutation

const permutation = (arr, k) => {
	const results = [];
	if (k === 1) return arr.map((el) => [el]);
	arr.forEach((currentEl, i, _arr) => {
		const nextPermu = permutation(_arr.filter((_,_i) =>i !== _i), k - 1); //현재 원소를 제외한 모든 원소로 순열 생성
		const permutations  = nextPermu.map((_permutation) => [currentEl, ..._permutation]);
		results.push(...permutations);
	});

	return results;
};