유클리드 & 선형검색 & 이진 탐색

이한수·2022년 8월 6일

알고리즘

목록 보기

4/5

🚓유클리드 호제법

두 정수의 최대공약수를 구하는 알고리즘 입니다.

//최대 공약수
int a = scan.nextInt();
int b = scan.nextInt();


while(a != b){
	if(a > b){
    	a%=b;
    }else{
    	b%=a;
    }
}


Systemo.out.println(a);

//큰수에서 작은 수를 뺴는 방식도 있지만 , 
//단계가 나머지를 이용한느 것보다 상대적으로 많습니다.

//최소 공배수 구하기
// 두 정수를 곱하고 최대 공약수를 나누는 방식이 있습니다.

int a = scan.nextInt();
int b = scan.nextInt();
int multifly = a*b;


while(a != b){
	if(a > b){
    	a%=b;
    }else{
    	b%=a;
    }
}

System.out.println(multifly/a);

🚓선형 검색

임의의 배열에서 원하는 데이터를 찾는 알고리즘입니다.

정렬되지 않은 배열을 의미합니다. 정렬도니 배열의 경우 선형검색보다는 이진 검색을 사용하는 것이 효율적이기 때문입니다.

//for문을 이용하여 앞에서부터 탐색합니다.

int a = 53;
int [] arr = new int[] {1,7,34,66,43,88,53,68,15,53};
//10개짜리 배열

int pos = -1;

for(int i=0 ; i<arr.length(); i++){

	if(arr[i] == a){
    	pos = i;
    	break;
    }
}

//53이라는 값이 처음 발견된 시점에 종료합니다.

🚓이진 검색

정렬된 배열에서 원하는 데이터를 찾는 방식입니다.
검색 대상 배열의 중앙 요소를 확인한 뒤 , 3가지 경우를 확인합니다.
- 찾는 값과 같으면 인덱스를 표시하고 종료.
- 찾는 값보다 크다면, 검색 대상을 앞으로 줄입니다.
- 찾는 값보다 작다면, 검색 대상을 뒤로 줄입니다.

일반적인 예시를 하나 들자면 , 1~10까지의 숫자 중 자신이 생각하는걸 맟춰보라 친구들에게
문제를 냈을 경우 입니다.

저희는 선택의 폭을 줄이고자 중간 값인 5를 먼저 언급하게되는 것과 같은 원리라 보시면 됩니다.

//찾는값
int a = 45;

//값을 찾을 배열
int arr[] = new int[] { 23,28,32,36,40,45,49,56,75,89};

//인덱스값 담아줄 변수
int pos = -1;

//배열의 첫 인덱스
int left = 0;

//배열의 마지막 인덱스
int right = arr.length() -1;

//배열 범위의 중간값을 담아줄 변수
int middle;

//pos에 인덱스 값이 담겼으면 값을 발견했다는 의미.
//left가 right를 초과하는 순간 배열의 모든 곳을 이미 탐색했다는 의미.
while(pos != -1 && left <= right){
	middle= (left+right)/2;
    
    if(arr[middle] == a){
    	pos = middle;
    }else if(arr[middle] > a){
    	right = middle-1;
    }else{
    	left = middle+1;
    }
}