[ 모각코 코딩테스트 Level 1 3일차 ] 탐색

선형 탐색 알고리즘

 

선형 탐색 알고리즘 : 데이터의 처음부터 끝까지 하나하나 확인하는 방식

 

배열의 첫 요소부터 하나하나씩 검사하기 때문에 원하는 값이 맨 마지막에 존재한다면

배열의 크기와 동일한 연산 횟수가 필요함. 즉 시간복잡도는 O(n)

 

my_arr = [ 1,2,3,4,5,6,7,8,9,10 ]

for index in my_arr :
	if index == 6 :
           print("성공")

 

 

이진 탐색 알고리즘 

 

이진 탐색 알고리즘 : 배열을 반으로 나누어서 원하는 값을 찾는 알고리즘

 

* 탐색을 하기전에 배열의 데이터가 크기 순서대로 정렬이 되어있어야 한다.

 

 

< 이진 탐색 알고리즘 과정 >

 

ⓐ 배열의 중간값을 찾고 찾고자하는 값보다 중간값이 작은지 큰지 확인한다.

ⓑ 중간값이 작다면 배열의 중간값을 기준으로 오른쪽에 있는 배열을 탐색한다.

    마찬가지로 오른쪽에 있는 배열의 중간값을 찾고 크기를 비교한다.

   

    중간값보다 작다면 배열의 중간값을 기준으로 왼쪽에 있는 배열을 탐색한다.

    마찬가지로 왼쪽에 있는 배열의 중간값을 찾고 크기를 비교한다.

 

ⓒ 원하는 값을 찾을 때까지 혹은 배열의 크기가 1이 될때까지 과정을 반복하면서 수행한다. 

 

 

< 이진 탐색 알고리즘 구현 >

 

탐색할 배열을 변경시키는 것이 아니라 시작 인덱스와 마지막 인덱스를 사용해 탐색할 배열의 범위를 제한한다.

 

# Python

def binary_search( my_list ,target):
    start = 0 # 탐색 배열의 시작 인덱스
    end = len(my_list)-1 # 탐색 배열의 마지막 인덱스

    while start < end :
        middle = ( start + end ) // 2 # 중앙값
        if target == my_list[middle] :
            return my_list[middle] 
        elif target < my_list[middle] : # 찾고자 하는 값이 중앙값보다 작을 때
            end = my_list[middle] - 1
        else : # target > my_list[middle] # 찾고자하는 값이 중앙값보다 클 때
            start = my_list[middle] + 1

    return "결과에 없습니다."

arr = [ 1,2,3,4,5,6,7,8,9,10 ]
print ( binary_search(arr,90))

 

이진 탐색 알고리즘의 최악의 경우는 탐색할 배열의 데이터가 총 1개가 남을 때 까지 반복하는 것이다. 

이진 탐색 알고리즘의 연산 횟수는 데이터 크기의 로그 2를 취한 것과 비례한다.

 

 

# C

#include <stdio.h>

int binary_search(int *arr, int length, int target) {
	int start = 0;
	int end = length - 1;
	int mid = 0;

	while (start < end) {
		mid = (start + end) / 2;
		if (arr[mid] == target) {
			return 1;
		}
		else if (arr[mid] < target) {
			start =  mid + 1;
		}
		else { // arr[mid] > target
			end = mid - 1;
		}
	}

	return 0;
}



int main() {
	int my_list[] = { 1,2,3,4,5,6,7,8,9,10 };
	int length = sizeof(my_list) / sizeof(int);
	int target = 9;


	int result = binary_search(my_list, length, target);

	if (result) {
		printf("일치하는 값 %d 존재", target);
	}
	else {
		printf("일치하는 값 %d 없음", target);
	}

}

 

# JAVA

public class BinarySearch {
    
    boolean binarySearch( int[] arr, int length, int target ){
        int start = 0;
        int end = length-1;
        int mid = 0;
        
        while ( start < end ){
            mid = ( start + end ) / 2;
            if ( target == arr[mid] ){
                return true;
            }
            else if ( target > arr[mid] ){
                start = mid + 1;
            }
            else { // target < arr[mid]
                end = mid - 1;
            }
        }
        return false;
    }
    
    
    public static void main(String[] args) {
        
        BinarySearch bs = new BinarySearch();
        
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int target = 9;
        int length = arr.length;
        
        boolean result = bs.binarySearch(arr,length,target);
        
        if ( result ){
            System.out.println("일치하는 값 " + target + " 존재");
        }
        else {
            System.out.println("일치하는 값 " + target + "없음");
        }
    }
}

 

---

[ 3일차 과제 ]

 

 

def binary_search( my_list, target) :
    start = 1
    end = max(my_list)


    while start < end :
        mid = ( start + end ) // 2
        sum = 0


        for index in my_list :
            sum += index // mid


        if sum > target :
            start = mid + 1
        else :
            end = mid - 1


    return mid


my_list = [215,513,712,803]
target = 10


result = binary_search(my_list, target)
print(result)

 

문제 자체가 이해가 되지 않음...ㅋㅋㅋㅋㅋㅋㅋㅋㅋ