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

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)
  • 태그

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

티스토리툴바