TIL 49일차 알고리즘 심화 조합, 순열, 최대공배수, 최소공약수

shleecloud·2021년 10월 7일

Codestates

목록 보기

50/95

들어가며

알고리즘 심화 2일차다. 오늘로 코드스테이츠에서 진행하는 알고리즘 수업은 끝났다. 아침마다 푸는 Toy 프로젝트는 있겠지만 이론 수업은 끝났다. 알고리즘은 하루아침에 되는게 아니다. 고민하는 시간만큼 사고력이 길러지는 영역이라 오랫동안 꾸준하게 그리고 즐겁게 해야된다. 다행히 이번에 만난 페어분은 역대급 사이다 페어라서 정말 시간가는줄 모르게 재밌게 진행했다. 실력이 비슷한 페어는 오랜만이라 만족스러운 기분이다. Section3을 좋게 시작하니 피로도도 없고 기분이 좋다.

글을 어떻게 쓸까 고민되는데 정리할 내용 위주로 써야겠다. 오늘 글로 다 녹이기는 무리고 앞으로 공부할 내용을 적어보자. 너무 많은걸 한 번에 배우려고 해서 놓치는게 많을까봐 걱정이다.

나눌 수 없는 knapsack 알고리즘

어제자 Advanced 챌린지에서 본 알고리즘. 한정된 무게 안에서 가장 가치있는 물건을 가져올 수 있는 알고리즘이다. 동적 프로그래밍을 써야 겨우 해결된다. 유튜브 강의와 잘 정리된 블로그로 어느정도 이해가 됐다. 내 포스팅으로 녹여보고싶다.
https://youtu.be/xCbYmUPvc2Q
https://gsmesie692.tistory.com/113

순열, 조합

재귀로 구현한 순열과 조합은 간결하면서 강력하다. 코드 한 줄만으로 둘 사이를 오갈 수 있는 알고리즘을 정리중인데 쓰면 쓸수록 마음에 들고 멋있다. 이것도 정리하고 싶다.

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349

const getCombinations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1); // 해당하는 fixed를 제외한 나머지 뒤
    //const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열 

    const combinations = getCombinations(rest, selectNumber - 1); // 나머지에 대해서 조합을 구한다.
    const attached = combinations.map((combination) => [fixed, ...combination]); //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
    results.push(...attached); // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
}

const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]