simDev1234
심플하고 차분하게
simDev1234
전체 방문자
오늘
어제
  • 분류 전체보기
    • Computer Science
      • Basic Math
      • Data Structure
      • Algorithm
      • Database
      • OS
    • Language
      • Java
      • Kotlin
      • SQL
    • Framework
      • Spring
      • Orm&Mapper
      • 프로젝트로 스프링 이해하기
      • 스프링 라이브러리
    • Infra
      • Cloud
      • Docker
      • Redis
      • AWS, Azure
      • Device
    • Etc
      • CleanCoding
    • Git,Github

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 스프링
  • scanner #next() #nextLine()
  • 참조변수
  • 자바메모리구조
  • JVM메모리구조
  • 자바
  • 자바프로그래밍
  • null
  • 404
  • 자바프로그램
  • 컨트롤러
  • 참조타입
  • controllerTest

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
simDev1234

심플하고 차분하게

[기초 수학] 조합
Computer Science/Basic Math

[기초 수학] 조합

2022. 7. 11. 13:35

|  조합 (Combination)

✏️ 개념 정리

(1) 조합 : 서로 다른 N개의 수에서 R개를 뽑아 나열하는 경우의 수

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)

- nCr = n! / (n-r)!r! = nPr / r!  (단, 0 < r <= n)

 

(2) 중복 조합 : 순서 X, 중복 O

- nHr = n+r-1Cr

 

💻 구현하기

[ 조합 구현 _ 재귀 :  교환 없이 방문배열을 통해 출력하기 ]

✅  조합 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하지 않고 나열하는 것

 

✅  구현 방법

 

[입력]

서로 다른 n개의 수를 담은 배열(int[] arr)과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r=2),

방문위치를 알려줄 배열(int[] visited)을 인자로 받는다.

*알고리즘이 시작되면, 선택 가능 갯수(r)는 처음입력받은 수(r=2)이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.

*조합 알고리즘에서는 순서를 고려하지 않기 때문에, r을 기준으로 depth를 조정한다.

 

[처리]

선택 가능 갯수(r)를 기준으로, depth를 하나씩 방문하며 r == 0 일때에 출력한다.

 

※ 그림으로 본 조합 알고리즘 모습

✅  구현 하기

void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
}

'Computer Science > Basic Math' 카테고리의 다른 글

[기초수학] 점화식과 재귀함수  (0) 2022.07.11
[기초 수학] 순열  (0) 2022.07.08
[기초 수학] 집합과 경우의 수  (0) 2022.07.08
기초수학 총정리  (0) 2022.06.17
    'Computer Science/Basic Math' 카테고리의 다른 글
    • [기초수학] 점화식과 재귀함수
    • [기초 수학] 순열
    • [기초 수학] 집합과 경우의 수
    • 기초수학 총정리
    simDev1234
    simDev1234
    TIL용 블로그. * 저작권 이슈가 있는 부분이 있다면 댓글 부탁드립니다.

    티스토리툴바