[ 알고리즘 ] 순열, 조합, 부분집합

순열

→ 서로 다른 n개의 원소 중 r개를 뽑아 나열하는 것

→ 순서가 존재한다.

 

 

구현방법

예시) 1,2,3,4 숫자카드가 있을 때 숫자카드를 중복으로 사용하지않고 만들 수 있는 3자리 수를 모두 출력하시오

 

1. 반복문

    public static void main(String[] args) {
        for (int i = 1; i < 5; i++) {
            for (int k = 1; k < 5; k++) {
                if (i != k) { // 각 자리 숫자는 서로 달라야한다.
                    for (int j = 1; j < 5; j++) {
                        if (k != j && i != j) {  // 각 자리 숫자는 서로 달라야한다.
                            System.out.println(i + "" + k + "" + j);
                        }
                    }
                }
            }
        }
    }

 

 

 

2. 재귀

     - 숫자 선택 여부를 기록할 배열을 사용해 이미 사용된 숫자인지 아닌지 판단하여 숫자를 선택

     - findNum() 재귀 호출 후 visited[i] = false; 로 바꾸는 이유는 

       계속 true 상태로 유지할 경우 처음에 123이 완성되어 출력 후
       다음 수를 찾기 위해 함수가 실행될 때 이미 모두 선택된 숫자라고 판단해 수를 만들 수가 없다.

 public static boolean visited[] = new boolean[5];	// 숫자 선택여부를 기록할 배열

    public static void main(String[] args) {
        findNum(0, "");	// 선택된 숫자가 0개, "" 전달
    }

    public static void findNum(int cnt, String str) {	//선택된 숫자의 수 , 출력할 수를 저장할 문자열
        if (cnt == 3) {	// 선택된 숫자가 3개가 되었을 때 수를 기록해둔 문자열 출력
            System.out.println(str);
        } else {
            for (int i = 1; i < 5; i++) {
                if (!visited[i]) {	//아직 선택되지않은 숫자일 경우
                    visited[i] = true;	//선택 여부를 false에서 true로 바꾸고
                    findNum(cnt + 1, str + i + ""); // 다음 숫자를 고르기 위해 findNum 재귀호출
                    visited[i] = false;
                }
            }
        }
    }

 

 

 

 

---

조합

→ 서로 다른 n개의 원소 중 r개를 순서없이 고르는 것

 

 

구현 방법

예시) 1,2,3,4 숫자카드가 있을 때 숫자카드를 중복으로 사용하지않고 만들 수 있는 3자리 수를 모두 출력하시오

 

1. 반복문

    public static void main(String[] args) {
        for (int i = 1; i < 5; i++) {
            for (int k = i + 1; k < 5; k++) {	//앞에 선택된 수보다 큰 수 선택
                for (int j = k + 1; j < 5; j++) {	//앞에 선택된 수보다 큰 수 선택
                    System.out.println(i + "" + k + "" + j);
                }
            }
        }
    }

 

 

2. 재귀

    public static void main(String[] args) {
        findNum(0, "", 0);
    }

    public static void findNum(int cnt, String str, int beforeNum) {
    	//선택된 숫자가 3개일 경우 선택된 숫자들 출력
        if (cnt == 3) {
            System.out.println(str);
        } else {
        	//이전에 선택된 수보다 큰 수의 범위내에서 숫자 선택
            for (int i = beforeNum + 1; i < 5; i++) {
            	//다음 숫자를 고르기 위해 재귀 호출
                findNum(cnt + 1, str + i, i);
            }
        }
    }

 

 

---

 

순열, 중복순열, 조합, 중복조합 비교

예시 ) 1,2,3 카드가 있고 2장을 뽑아서 만들 때

 

순열

1,2 / 1,3 / 2,1 / 2,3 / 3,1 / 3,2

   ⇒ 중복된 숫자를 쓰지않는다.

   ⇒ 구성이 같아도 순서가 다르면 된다.

 

중복순열

1,1 / 1,2 / 1,3 / 2,1 / 2,2 / 2,3 / 3,1 / 3,2 / 3,3

   ⇒ 중복된 숫자를 쓴다.

   ⇒ 구성이 같아도 순서가 다르면 된다.

 

조합

1,2 / 1,3 / 2,3

   ⇒ 중복된 숫자를 쓰지않는다.

   ⇒ 구성이 달라야한다.

 

중복조합

1,1 / 1,2 / 1,3 / 2,2 / 2,3 / 3,3

   ⇒ 중복된 숫자를 쓴다.

   ⇒ 구성이 달라야한다.

 

 

---

 

부분집합

→ 어떠한 원소들로 이루어진 집합에서 원소를 골라 만든 집합

→ n개의 원소를 가지는 집합의 부분집합 수 : 2^n

 

접근 방식

→ 부분집합에 원소를 포함시키는가 시키지않는가

예시) {1,2,3,4} 집합의 부분집합 구하기

 

구현방법

예시) {1,2,3,4} 집합의 부분집합 구하기

 

1. 반복문

 public static void main(String[] args) {
        int visited[] = new int[5];
        for (int i = 0; i < 2; i++) {
            visited[1] = i;
            for (int k = 0; k < 2; k++) {
                visited[2] = k;
                for (int j = 0; j < 2; j++) {
                    visited[3] = j;
                    for (int l = 0; l < 2; l++) {
                        visited[4] = l;
                        for (int a = 1; a < 5; a++) {
                            if (visited[a] != 0)
                                System.out.print(a + " ");
                        }
                        System.out.println();
                    }
                }
            }
        }
    }

 

 

 

2. 재귀

   static boolean visited[] = new boolean[5];

    public static void main(String[] args) {
        findPowerSet(1, "");
    }

    public static void findPowerSet(int cnt, String str) {
    	//원소 4개에 대한 선택을 다 한 경우
        if (cnt > 4) { 
            System.out.println(str);
        } else {
            //해당 원소를 부분집합에 포함하는 경우
            findPowerSet(cnt + 1, str);
            //해당 원소를 부분집합에 포함하지않는 경우
            visited[cnt] = true;
            findPowerSet(cnt + 1, str + cnt);
            visited[cnt] = false;
        }
    }

 

 

 

 

---

 

 

구현 전 주의할 점

- 기저조건 꼭 설정하기 !!! 

- 중복 체크 관리 : boolean 배열 , 비트마스킹, Next Permutation

- 재귀 호출 시 매개변수 값을 a+1이 아닌 a+=1로 하는 경우 현재 메소드 스택의 a값이 변경되는 것을 조심하기 !!!!!!!