[JAVA] 알고리즘 String

완전 검색(완전 탐색, DFS)// 펙토리얼이므로 시간 복잡도가 굉장히 낮습니다.

- 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법

- Brute-force 혹은 generate-and-test 기법이라고도 불린다.

- 모든 경우의 수를 테스트한다.

-상대 적으로 설계는 빨리할수있다.

- 경우의 수가 상대적으로 작을 때 유용하다.

 

문제 예시

1)Baby-gin Game.

0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고,

3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.

그리고, 6장의 카드가 run,triplet으로만 구성된 경우를 baby-gin으로 부른다

6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.

 

ex) Baby-gin 조건

 - 667767 = triplet (666,777)

 - 054060 = run 1, triplet 1 (456,000)

 - 101123 = x (123, 011) (111, 023) 베이비진은아님

 

조심해야 할 것

- 입력 받은 숫자를 정렬한 후 확인 >123123 일경우 11 22 33 으로 오히려 확인이 불가할수도있음(탐욕 알고리즘적)

 

우리는 완전 검색을 사용해야한다.

그럴려면 

1. 고려할 수 있는 모든 경우의 수 생성하기

2. 테스트하기.

 

2) 여행사 BIG sale!

1. 출발, 도착 선택시 모든 도시를 여행시켜 드립니다! , 단 숙박비는 본인 부담

 - 순열 4!

2. 3개의 도시를 선택하면 숙박비를지원해줍니다! (숙박 비용)

 - 조합을 하나만 6C3

3. 2개 10%, 3개 20%, 4개 30% 할인!, 이동 경비는 무료 

 - 조합을 여러개 6C1,6C2,6C3,...

고객은 70만원의 비용을 가지고이다.

 

순열( nPr = n!)

 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열 

 - 서로 다른 n개 중 r개를 택하는 순열 

생성하는 방법

ex ) {1,2,3} 순열 생성하는 함수

 

 

 

조합 ( nCr )

- n개의 원소 중 r개 원소를 갖는 조합 생성

ex ) 4C2

 

package homework;
 
import java.util.Arrays;
 
public class johap {
 
    static int[] numbers;
    static int N=4, R=2;
    
    public static void main(String[] args) {
        numbers = new int[R];
        combination(0, 1);
    }
 
    static void combination(int cnt, int start) {
        
        if(cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i=start; i<=N; i++) {// i : 시도하는 수
            numbers[cnt] = i; // 현재 시도하는 수 뽑음
            combination(cnt+1,i+1);// cnt 1 추가, i는 또 뽑을 친구니까 com 해줘
            
        }
    }
}