[브루트포스][java] 순차탐색, 경우의 수

Sequential search(순차탐색) -시간복잡도 : O(N)

if 정렬이 되어있는 경우 이진탐색 -시간복잡도 : O(logN)

 

경우의 수

-순열(Permutation) : 선택 순서가 결과에 영향을 미치는 경우

ex

package Basic_Algorithm.concept.브루트포스;

//가장 큰 두자리 수 구하기
public class PermutaionTest {
    static int N=4;
    static int[] Nums={1,2,3,4};

    static int solve(int cnt, int used, int val){
        int ret=0;  //ret 리턴할 값
        if(cnt==2) return val;
        for (int i = 0; i < N; i++) {
            if((used&1<<i)!=0)continue; //사용한 숫자에 대해서는 continue
            ret=Math.max(ret,solve(cnt+1,used|1<<i,val*10+Nums[i]));
        }
        return ret;
    }
    public static void main(String[] args) {
        System.out.println(solve(0,0,0));
    }
}

-조합(Combination) : 선택 순서가 결과에 영향을 주지 않는 경우

ex)두 수의 합 가장 큰 수 구하기

package Basic_Algorithm.concept.브루트포스;

//두 수의 합 가장 큰 수 구하기
public class CombinationTest {
    static int N=4;
    static int[] Nums={1,2,3,4};
    //pos : 현재 위치, cnt : 선택된 갯수 val : 중간 결과값
    static int solve(int pos, int cnt, int val) {
        int ret = 0;  //ret 리턴할 값
        if (cnt == 2) return val;
        if (pos==N) return -1;
        ret = Math.max(ret, solve(pos + 1, cnt + 1, val + Nums[pos]));
        ret = Math.max(ret, solve(pos + 1, cnt, val));
        return ret;

    }
    public static void main(String[] args) {
        System.out.println(solve(0,0,0));
    }
}