BOJ 2805 나무 자르기

www.acmicpc.net/problem/2805

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

설명

1박 2일의 상근이가 나무가 필요한데, 벌목하고 잘린 나무를 사용한다는 내용입니다. 이때 벌목할때 쓰는 목재절단기는 한번에 H만큼 높이까지 모든 나무를 한번에 자를 수 있다고 합니다. 환경을 생각하는 상근이는 나무가 최대한 잘려나가지 않고 필요한 나무를 얻어내는것이 목표입니다.

 

만약 나무 4개가 20m, 15m, 10m, 17m가 있고 상근이가 필요한 나무는 7m일때 목재절단기의 높이가 15m가 되면 첫번째 나무에서 5m, 네번째 나무에서 2m를 얻어낼 수있으므로 잘리는 높이를 15m로 정해주어야하죠. 필요한 나무를 다 채우면서 나무를 최대한 높게 자르려면 절단기의 높이를 어떻게 정해야할까요?

 

풀이

나무의 수 N과 구하고자 하는 상근이의 나무 M이 주어지고 범위가 1<= N <= 1,000,000, 1<= M <= 2,000,000,000입니다. 보통 이런식으로 말도 안되는 큰 값을 범위로 주면 log가 섞여있는 알고리즘으로 풀어야합니다. 떠올려볼 수 있는 알고리즘이 빠른 정렬 알고리즘, 이진탐색 등이 있겠네요.

우선 중간 정도의 높이 정해보고 만약 상근이가 가져갈 수 있는 양이면 점차적으로 높이를 높이는 방식으로 접근하면 됩니다. 

어떤 높이 height가 주어졌을때 이 height로 잘린 트리의 남은 부분을 전부 합쳐 M 이상이면 이 height는 H의 조건을 만족하게 됩니다. 이 함수가 아래의 isPossible이지요.

bool isPossible(unsigned int height) {
	unsigned int taken = 0;
	for (int i = 0; i < N; i++) {
		if (trees[i] >= height)
			taken += (trees[i] - height);
		if (taken >= M) return true;
	}
	return false;
}

 

그래서 만약 그 높이가 가능하다면 높이를 올립니다. 그리고 다시 가능한지 확인하죠. 아래의 코드는 이진탐색의 코드입니다.

isPossible에서 true가 반환되었다면 일단 답이 될 후보이며 ret에 그 값을 저장해놓습니다. 그리고 left의 값을 mid + 1로 증가시켜 자를 높이를 높게만들죠. isPossible이 false가 반환되었다는 것은 이 값은 답 후보가 아니라는 겁니다. 그래서 자를 높이를 아래로 조정합니다.

right는 입력에서 들어올 수 있는 가장 큰 값으로 지정을 했는데, 정석대로 풀려면 나무들을 순회하면서 가장 큰 나무의 높이가 right가 되어야겠죠? 하지만 이진탐색은 빠르니까 가장 큰 값을 지정해도 문제는 없습니다.

int solve() {
	unsigned int left = 0, right = 1000000000;
	unsigned int mid,ret;
	while (left <= right) {
		mid = (left + right) / 2;
		if (isPossible(mid)) {
			ret = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return ret;
}

 

그리고 이진 탐색에서 나무들은 모두 정렬된 상태여야합니다. 그래서 문제를 풀기 전에 sort로 정렬합니다. 아래는 전체 코드입니다.

#include <iostream>

using namespace std;
int N;
long long M;
long long trees[1000001];
bool isPossible(unsigned int height) {
	unsigned int taken = 0;
	for (int i = 0; i < N; i++) {
		if (trees[i] >= height)
			taken += (trees[i] - height);
		if (taken >= M) return true;
	}
	return false;
}
int solve() {
	unsigned int left = 0, right = 1000000000;
	unsigned int mid,ret;
	while (left <= right) {
		mid = (left + right) / 2;
		if (isPossible(mid)) {
			ret = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return ret;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> trees[i];

	cout << solve() << endl;

}

 

위 풀이의 시간은 O(N log(M)) 입니다. isPossible은 모든 나무를 돌아가며 연산하기 때문에 N, 그리고 이진 탐색의 뼈대인 solve함수가 log M이 되죠.

반응형
블로그 이미지

REAKWON

와나진짜

,

백준 BOJ(10815)

www.acmicpc.net/problem/10815

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

 

숫자 카드중에 가지고 있는 카드가 있다면 1 아니면 0을 출력해주는 그런 문제입니다. 이진탐색만 알면 바로 풀 수 있는 그런 문제입니다.  이진탐색에 관한 내용은 아래를 참고하시기 바랍나다.

reakwon.tistory.com/60

 

[알고리즘] 그림을 통한 이진탐색(Binary Search) 개념과 C 코드구현

이진탐색 배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠? 너무 쉽습니

reakwon.tistory.com

풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int n, m;
int mine[500001];
int binarySearch(int left, int right, int num) {
	if (left == right) return mine[left] == num;
	int mid = (left + right) / 2;
	if (mine[mid] == num) return 1;
	if (mine[mid] > num)
		return binarySearch(left, mid, num);
	return binarySearch(mid + 1, right, num);
}
int main() {
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
		scanf("%d",&mine[i]);
	sort(mine, mine + n);
	scanf("%d",&m);
	for (int i = 0; i < m; i++) {
		int card;
		scanf("%d",&card);
		printf("%d ",binarySearch(0,n-1,card));
	}
	printf("\n");

	return 0;
}

 

탐색을 위해 문제의 입력을 갖고 있는 카드를 우선 정렬합니다. 위 코드가 해답인 코드입니다. 그리고 난 후 이진탐색으로 그 카드의 인덱스가 있는지 확인하는 방법으로 카드가 있는지 아닌지 확인할 수 있습니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

하한(Lower bound), 상한(Upper bound)

하한, 상한은 배열이 이미 정렬된 상태에서 적용되어야합니다. 상한, 하한은 모두 이진 탐색(Binary Search)로 구현이 되어있기 때문이죠. 여기서 이진 탐색은 아래의 코드인 것을 알고 계시겠죠? 이진 탐색의 기본 코드는 아래와 같습니다. 이진 탐색의 탐색 속도는 O(lg 2)의 속도를 자랑하지요. 

 

 

int BinarySearch(int s, int e, int number)
{
    int left=s,right=e,mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == number) return mid;
        if (arr[mid] > n) right = mid -1;
        else left = mid + 1;
    }
    return -1;
}

 

하한이란? (Lower Bound)

특정 값 K보다 같거나 큰 값이 처음 나오는 위치가 됩니다. 즉, K값 이상인 값이 맨 처음 나오는 위치여야합니다. 아래는 그 예를 나타내는 표입니다. 이때 맨 앞 요소의 index는 0으로 시작합니다.

배열
1 2 2 4 4 5 6 6 6 9 9
lower_bound
lower bound( 4 )  3
lower bound( 5 )  5
lower bound( 9 )  9

하한을 Binary Search방식으로 구현한 코드는 아래와 같은데요.  number값을 이상인 값이 mid 위치에서 발견되었다면  왼쪽으로 더 가다보면 아예 작은 수를 만나게 되고 left와 right의 역전 현상이 발생되어 멈춥니다. 멈추기 전에 우리는 가장 마지막에 arr[mid] >= number인 상황을 lower_bnd에 저장한 상황이죠. 

int Binary_Search_Lower_Bound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int lower_bnd = -1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] >= number)
        {
            lower_bnd = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    return lower_bnd;
}

범위를 좁혀가는 상황을 그림으로 표현했습니다.

 

- C++의 lower_bound 사용

C++에서는 라이브러리 함수 형태로 lower bound를 지원합니다. 아래와 같은 형식을 사용하게 되는데요. 사용법은 이렇습니다. 


lower_bound( 정렬한 배열 포인터, 정렬한 배열 포인터의 끝 주소, 값) - 정렬한 배열 포인터

여기서 정렬한 배열의 포인터는 알겠는데, 정렬한 배열 포인터의 끝 주소값은 어떻게 구할까요? 그냥 마지막 원소의 주소를 넣어주거나 배열의 주소 + 배열의 사이즈로 넣어주면 됩니다. 

lower_bound의 반환 값은 하한값의 주소를 돌려주기 때문에 만약 index를 얻으려면 정렬한 배열 포인터를 빼주면 됩니다. 이 함수의 사용법은 밑의 예제 코드에서 upper_bound의 함수와 같이 사용해보도록 하겠습니다.

상한이란? (Upper Bound)

특정 값 K보다 큰 값이 처음으로 나오는 위치가 됩니다. 즉, K값 초과인 값이 맨 처음으로 나오는 위치입니다. 몇 가지 예를 들어볼까요?

배열
1 2 2 4 4 5 6 6 6 9 9
upper_bound
upper bound( 4 ) 5
upper bound( 5 ) 6
upper bound( 9 ) -1 

이 역시 Binary Search로 구현되는데요. 구현한 모습은 아래와 같습니다. 중간의 비교문이 반대로 됐음을 알 수 있죠? 이것은 arr[mid]의 값이 number의 이하일때 number와 최대한 같은 값의 index를 찾기 위함입니다.

 

 

int Binary_Search_Upper_Bound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int upper_bnd=-1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] <= number)
        {
            upper_bnd = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    return upper_bnd+1 >= N ? -1: upper_bnd+1;
}

 

만약 이렇게 돼서 while루프가 멈추었다면 arr[upper_bnd]값은 number값 초과 직전의 값일 것입니다. 그렇다면 arr[upper_bnd+1]의 값은 number보다 큰 값일 테지요. 그래서 마지막 return에서 +1을 해주는데, 이것이 배열의 사이즈를 넘어갈 수 있으니까 사이즈 체크하여 return합니다. 

C++에서 당연히 lower_bound함수가 존재하듯 upper_bound의 함수 역시 존재하며 사용법은 동일합니다. 단, 아래와 같이 사용할때 상한 값을 못찾아줄때도 있는데, 이때는 배열의 인덱스를 넘어가는 값을 갖게됩니다.


  upper_bound(정렬한 배열 포인터, 정렬한 배열 포인터의 끝 주소, 값) - 정렬한 배열 포인터

 

이제까지 설명한 내용을 예제 코드를 통해서 확인해보세요. 직접 구현한 BinarySearch 형식의 upper_bound, lower_bound도 같이 구현되어있습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100];
int N = 11;
int BinarySearchLowerBound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int lower_bnd = -1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] >= number)
        {
            lower_bnd = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    return lower_bnd;
}

int BinarySearchUpperBound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int upper_bnd=-1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] <= number)
        {
            upper_bnd = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    return upper_bnd+1 >= N ? -1: upper_bnd+1;
}


int main(void) {


    arr[0] = 4; arr[1] = 2; arr[2] = 4; arr[3] = 1; arr[4] = 9;
    arr[5] = 2; arr[6] = 6; arr[7] = 6; arr[8] = 6; arr[9] = 9, arr[10] = 5;
    
    //정렬
    sort(arr, arr + N);

    printf("정렬된 배열\n");
    for (int i = 0; i < N; i++) printf("%d ",arr[i]);
    printf("\n");
    
    printf("Lower Bound\n");

    printf("%d lower bound:%d\n", 4, BinarySearchLowerBound(0, N - 1, 4));
    printf("%d lower bound:%d\n", 5, BinarySearchLowerBound(0, N - 1, 5));
    printf("%d lower bound:%d\n", 2, BinarySearchLowerBound(0, N - 1, 2));
    printf("%d lower bound:%d\n", 1, BinarySearchLowerBound(0, N - 1, 1));
    printf("%d lower bound:%d\n", 9, BinarySearchLowerBound(0, N - 1, 9));

    printf("%d lower bound:%d\n", 4, lower_bound(arr, arr + N, 4) - arr);
    printf("%d lower bound:%d\n", 5, lower_bound(arr, arr + N, 5) - arr);
    printf("%d lower bound:%d\n", 2, lower_bound(arr, arr + N, 2) - arr);
    printf("%d lower bound:%d\n", 1, lower_bound(arr, arr + N, 1) - arr);
    printf("%d lower bound:%d\n", 9, lower_bound(arr, arr + N, 9) - arr);
  

    printf("Upper Bound\n");

    printf("%d upper bound:%d\n", 4, BinarySearchUpperBound(0, N - 1, 4));
    printf("%d upper bound:%d\n", 5, BinarySearchUpperBound(0, N - 1, 5));
    printf("%d upper bound:%d\n", 2, BinarySearchUpperBound(0, N - 1, 2));
    printf("%d upper bound:%d\n", 1, BinarySearchUpperBound(0, N - 1, 1));
    printf("%d upper bound:%d\n", 9, BinarySearchUpperBound(0, N - 1, 9));

    printf("%d upper bound:%d\n", 4, upper_bound(arr, arr + N, 4) - arr);
    printf("%d upper bound:%d\n", 5, upper_bound(arr, arr + N, 5) - arr);
    printf("%d upper bound:%d\n", 2, upper_bound(arr, arr + N, 2) - arr);
    printf("%d upper bound:%d\n", 1, upper_bound(arr, arr + N, 1) - arr);
    printf("%d upper bound:%d\n", 9, upper_bound(arr, arr + N, 9) - arr);   //배열의 인덱스 초과된 값이 나옴
  
}

 

 

그리고 위 코드의 결과입니다. 마지막 upper_bound의 값이 다름을 확인해보세요.

 

 

전체 코드의 결과

 

반응형
블로그 이미지

REAKWON

와나진짜

,

이진탐색


배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠?


너무 쉽습니다.

int arr[10] = { 3,5,6,8,9,11,14,15,18,20 };
int i;
int data = 18;
int found = -1;
for (i = 0; i < sizeof(arr); i++)
	if (arr[i] == data) found = arr[i];

printf("found:%d\n", found);
이러한 탐색시간은 O(n)에 해당합니다. 배열원소를 하나하나씩 전부 일치하는지 확인하기 때문이죠.

이보다 빠르게 찾을 수는 없을까요? 이 탐색시간을 O(logn)으로 수행할 수 있는 방법이 바로 이진탐색(Binary Search)입니다.


개념

이진탐색은 우선 정렬된 배열에서만 사용가능합니다. 정렬되지 않았다면 정렬을 해주어야하지요. 

또한 이진탐색은 3개의 변수가 사용이 됩니다. 바로 left, mid, right이지요. 초기상태에서 배열의 가장 첫번째를 가리키고 있는 left, 배열의 가장 끝을 가리키고 있는 right, left와 right의 중간을 가리키고 있는 변수가 mid입니다.


우리가 찾는 원소를 data라고 합시다. 우리는 mid의 값을 중요하게 생각해야 돼요. mid자리에 있는 원소가 data와 같다면 그 원소를 찾게 된 것이죠.


만약 mid자리에 있는 원소보다 data가 크다면 left~mid까지 범위는 탐색할 필요가 없게 되지요. 반대로 mid자리 원소보다 data가 작다면 mid~right까지의 범위는 탐색할 필요가 없습니다.


찾지 못 한다면 범위를 바꾸어줘야합니다. left~mid까지의 범위를 탐색할 필요가 없다면 이제 left=mid+1이 되고 mid 역시 left, right의 중간값인 (left+right)/2가 됩니다. 그 반대도 역시 마찬가지죠. 정리하자면 이렇습니다.





1. 찾을 data가 배열의 mid보다 크다면 mid+1부터 right까지 검색

2. 찾을 data가 배열의 mid보다 작다면 left부터 mid-1까지 검색

이제 실제로 어떻게 데이터가 검색되는지 보도록하지요.


배열의 원소 arr = { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20}이라고 칩시다.

다음은 여기서 18을 찾는 과정을 보여줍니다.



우선 초기에 left=0, mid=4, right=9입니다. mid의 값은 (left+right)/2로 계산된 값입니다. arr[mid]와 data를 비교해보니 data가 더 크군요. 그러니까 left와 mid까지의 범위는 볼 필요가 없습니다. 정렬된 배열이기 때문에 18보다 작은 것들은 left~mid까지이니까요.




이제 범위를 옮기도록 하지요. left=mid+1이 되고 mid는 그 중간 값인 (left+right)/2가 됩니다. 이제 다시 arr[mid]와 data를 비교해보니 data가 더 크지요? 다시 범위를 바꿉니다



이제 left와 mid는 같은 값이 되고 다시 arr[mid]와 data를 비교해보니 일치합니다. data가 배열에 있다는 것을 알게 됐습니다.


만일 data를 찾지 못한다면 left와 right는 서로 뒤집히게 됩니다. 그러니까 left가 right보다 더 크게 변한다는 의미입니다.



구현


아래코드는 원소가 존재한다면 몇번째에 위치하는지 인덱스를 구해냅니다. 구현을 통해서 위의 결과를 확인해보세요. 

int binarySearch(int *arr,int size,int data) {
	int left = 0;
	int right = size - 1;
	
	while (left<=right) {
		int mid = (left + right) / 2;
		if (arr[mid] == data)
			return mid;
		if (arr[mid] > data)
			right = mid - 1;
		else
			left = mid + 1;
	}

	return -1;
}


초기 left=0, right=size-1입니다. 가장 처음과 끝을 가리키고 있지요. while루프의 탈출조건은 left가 right보다 같거나 작을때까지 입니다. 


while루프에서는 우선 mid의 값을 구하고 이 mid 원소와 data를 비교하여 같은지 확인합니다. 원소를 찾지 못하면 left와 right의 값을 바꿉니다.

간단하죠?


이진탐색은 재귀함수로도 간단하게 구현이 가능합니다.


int binarySearch(int *arr,int left,int right,int data) {
	if (left > right) return -1;

	int mid = (left + right) / 2;
	
	if (arr[mid] == data) return mid;
	if (arr[mid] > data)
		return binarySearch(arr, left, mid - 1, data);
	return binarySearch(arr, mid + 1, right, data);
}


재귀함수도 너무 간단하죠? 기자사례는 위의 while루프와 같다는 것을 알 수 있습니다. 재귀함수의 종료 조건이되지요.


그 후 내부 코드는 while루프의 내부 코드와 유사하다는 것을 알 수 있습니다. 그렇죠?


아참, 주의할것은 호출할때 binarySearch(arr,0, (sizeof(arr)/sizeof(int))-1, data)로 호출해야합니다. 만약 arr의 크기가 10이라면 9를 right의 매개변수로 전달하는 것이죠. 왜냐면 크기가 10인 배열의 마지막 인덱스는 9이기 때문이죠.


시간복잡도

결국 이진탐색은 반으로 계속 줄여가면서 원소를 탐색하기 때문에 시간복잡도는 O(logn)이라는 사실을 알 수 있습니다. O(n)에 비해서는 훨씬 빠른 속도입니다.




하지만 배열이 정렬된 상태여야 된다는 점이 조금 아쉬운 부분이기는 하지만 하나의 배열에서 검색을 자주하는 상황이라면 한번 정렬만 하면 다음부터는 계속 O(logn)의 속도로 원소를 찾을 수 있죠.


반응형
블로그 이미지

REAKWON

와나진짜

,