21.8.25 알고리즘

탐색

완전탐색

브루트포스라고 부르며 컴퓨터의 빠른 계산성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성이 가장 최악인 방법.

구현방법
반복문

for(int i = 0; i < temp.length; i++){
	if (i == answer){
    	return i;
        }
 return -1;       
}

반복문-재귀함수

public int solution(int[] answer, int index){
	if(answer[index] == 10){
    	return index;
    }
    else {
    	return solution(answer, index + 1);
    }
}

이분탐색

이진검색이라고도 하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법
구현방법
left,right,center

public int solution(int[] x){
int left = 0;
int right = x.length - 1; /* 함수 시작시 left, righr 선언*/
	while(left <= right){ // left가 right보다 작거나 같다면 계속 반복
    		int mid = (left + right) / 2; // 시작과 동시에 mid값을 계산
            if(x[mid] == 10){ 
            	return mid; //맞으면 정답 인덱스 반환
            } else if (x[mid] < 10){
            	left = mid + 1; // 작으면 left를 mid + 1;
            } else if (x[mid] > 10){
            	right = mid - 1; // 크면 right를 mid - 1;
            }
 	}
    return mid;
}

깊이우선탐색

너비우선탐색