[알고리즘] 재귀 함수를 이용한 순열, 조합

2022. 8. 27. 17:00·알고리즘/풀이 힌트
반응형

순열? 

모든 경우의 수를 계산하는 알고리즘이다. ( 순서 고려 O )

[ 1, 3, 5 ] 가 주어졌다면 

1 3 5 

1 5 3

3 1 5

3 5 1

5 1 3

5 3 1

처럼 모든 경우의 수를 구하는 방법이다. 

function permutations(arr, n) {
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  arr.forEach((fixed, idx, arr) => {
    const rest = arr.filter((_, index) => index !== idx);
    const perms = permutations(rest, n - 1);
    const combine = perms.map((v) => [fixed, ...v]);
    result.push(...combine);
  });

  return result;
}

만약 arr 로 [ 1, 3, 5 ]가 주어지고 n이 3이라면 

 

if (n === 1) return arr.map((v) => [v]);

통해서 

[ 5 ], [ 3 ], [ 1 ] 이 return 된다. 

 

 const combine = perms.map((v) => [fixed, ...v]);

그것을 기존 배열에서 지운 [ 5 ]인 경우 [ 3 ]과 합쳐져서 [ 3, 5 ]가 되고 

이게 다시 [ 1 ]과 합쳐져서 [ 1, 3, 5 ]가 result 배열에 들어간다. 

 

이런식으로 반복해서 모든 경우의 수를 만들어낸다. 

 

조합 

주어진 배열에서 몇가지 경우의 수가 나오는지 계산하는 알고리즘이다. ( 순서 고려 X )

[ 1, 3, 4, 5 ]가 주어진다면 

1 3 4

1 3 5

1 4 5

3 4 5

의 경우의 수 를 구하는 공식이다. 

 

순열은 순서가 다르면 다른 경우의 수이지만 조합은 순서가 달라도 같은 경우의 수가 된다. 

function combinations(arr, n) {
  if (n === 1) return arr.map((v) => [v]);
  const result = [];

  arr.forEach((fixed, idx, arr) => {
    const rest = arr.slice(idx + 1);
    const combis = combinations(rest, n - 1);
    const combine = combis.map((v) => [fixed, ...v]);

    result.push(...combine);
  });

  return result;
}

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 풀이 힌트' 카테고리의 다른 글

[알고리즘] 배열끼리 비교해서 배열의 포함 관계 확인하기  (1) 2022.09.12
[알고리즘] 최소 신장 트리 ( Kruskal ) - JavaScript  (2) 2022.08.29
[알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘  (0) 2022.08.26
[알고리즘] 재귀함수 - JavaScript  (0) 2022.08.25
[알고리즘] 소수 구하기 - JavaScript  (0) 2022.08.23
'알고리즘/풀이 힌트' 카테고리의 다른 글
  • [알고리즘] 배열끼리 비교해서 배열의 포함 관계 확인하기
  • [알고리즘] 최소 신장 트리 ( Kruskal ) - JavaScript
  • [알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘
  • [알고리즘] 재귀함수 - JavaScript
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    네이버 부스트캠프
    react
    바질
    리얼클래스
    영어독학
    next.js
    ReactNative
    ChatGPT
    Babel
    식물
    Node.js
    프로그래머스
    리액트
    CSS
    영어회화
    네트워크
    Docker
    타입스크립트
    타일러영어
    덤프
    javascript
    자바스크립트
    redux
    다이소
    알고리즘
    리얼학습일기
    바질 키우기
    CCNA
    typescript
    webpack
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 재귀 함수를 이용한 순열, 조합
상단으로

티스토리툴바