완전탐색 / 모의고사

완전탐색 

 

  상대적으로 구현이 간단하고, 해가 존재한다면 항상 찾게 된다.

  완전 탐색으로 푼다면 기본적으로 시간 복잡도가 O(2^N)이나, O(N!) 이므로 INPUT의 값이 작아야한다.

 

DFS / BFS 와 조합해서 풀이가 되는 문제가 꽤 있음.

 

 

 

방식은 대개

 

EX) { a, b, c, d } 중 2개를 뽑아서 일렬로 세운다면, 

ab ac ad

ba bc bd 

ca cb cd 

da db dc 

이처럼 다 찾거나, 

반복문을 필요한 개수 만큼 돌리게 된다.

 

for (int i=0; i < size; i++ ) {
	for (int j=0; j < size; j++) {
     	for (int k=0; k < size; j++) {
        	......
    	}
    }
}

 

https://programmers.co.kr/learn/courses/30/lessons/42840?language=java 

코딩테스트 연습 - 모의고사

 

 

int[] answers = {1,3,2,4,2};
int[] one = {1, 2, 3, 4, 5};
int[] two = {2, 1, 2, 3, 2, 4, 2, 5};
int[] three = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

int[][] arrays = {{1, 2, 3, 4, 5},{2, 1, 2, 3, 2, 4, 2, 5},{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}};
    
    	for (int i=0; i < 3; i++) {
            
            int count = 0;
            int k = 0;
            
            for (int j=0; j < answers.length; j++) {

                if(answers[j] == arrays[i][k]) {
                    count++;
                }

                if (k == arrays[i].length) {
                    k = 0;
                    continue;
                }

                k++;
            }

            counts[i] = count;
        }

 

i 번 수포자가 답과 동일한 찍기를 했는지 채점한다. 

 

순서대로 채점했을 때 모두 2개씩 정답을 맞췄다.