"Upper bound"와 "Lower bound" - 배열'에서 '같은 수의 개수' 구하기! (C언어)

알고리즘 문제를 풀다보면 여러 수를 입력한 후,
특정한 수의 개수를 구하는 문제가 있죠.
대충 '정렬해서 푸는 문제'인 건 알겠는데, 도대체 '그 수의 개수를 어떻게 구하는가!'
 
여기서 새로운 알고리즘이 나옵니다.
바로 "Upper bound"와 "Lower bound"!
간단하게 설명하자면, '이분 탐색을 응용한 알고리즘' 입니다.
아래에서 더욱 자세히 다뤄보겠습니다!

<챕터>

1. Upper/Lower bound의 개념
2. 코드 및 코드 설명

 

---

 

1. Upper/Lower bound의 개념

 

Lower bound

 
"Lower bound"는 '배열에서 찾고자 하는 값(key) 이상의 최초값의 인덱스(배열 순서)를 찾는 알고리즘' 입니다.
쉽게 예를 들자면,
[1 1 2 2 2 3 4 4]라는 배열이 있을 때, key값이 2가 주어졌다면,
'key값 이상의 최초값'인 '배열의 3번째'가 반환됩니다.
 

Upper bound

 
"Upper bound"는 '배열에서 찾고자 하는 값(key) 초과의 최초값 인덱스(배열 순서)를 찾는 알고리즘'입니다.
이것도 쉽게 예를 들자면,
[1 1 2 2 2 3 4 4]라는 배열이 있을 때, key값이 2가 주어졌다면,
'key값 초과의 최초값'인 '배열의 6번째'가 반환됩니다.
 

---

 
두 개의 공통점이 있다면,
'Upper/Lower bound는 key값이 존재하지 않아도 값이 반환됩니다.'
 
예를 들어 Lower bound일 때,
[1 1 2 2 2 4 4 5]라는 배열이 있을 때, key값이 3 주어졌다면,
'key값 이상의 값'인 '배열의 6번째'가 반환됩니다.
Upper bound도 비슷하죠!
 
'배열에 key값이 존재하지 않는 상황'이라면,
"Upper bound와 Lower bound의 반환값은 서로 같습니다."
key값이 없는 상황에서 key이상의 값이나, key초과의 값이나 같은 말이니까요.
 

코드 및 코드 설명

 

* Upper bound와 Lower bound 위주로 설명하기 위해 배열 입력 및 정렬 과정은 생략합니다. ** 꼭 미리 배열을 정렬해 주세요! *

 

Lower bound

 
일단은, 이분 탐색에 대해 알아야 합니다.
'이분 탐색'은 배열에서 원하는 값을 찾는 알고리즘 중 하나로,
비교 할 배열의 범위 인덱스 앞(left), 뒷(right) 부분, 그리고 그 가운데 인덱스(mid)를 구하고
left가 right의 값과 같아지거나 값을 넘어버릴 때까지
arr[mid] < key이면 left = mid, arr[mid] > key이면 right = mid를 한 후
다시 left와 right의 mid를 구한 뒤 이 행동을 반복하여 배열 내 key값을 구하는 알고리즘입니다.
 
쉽게 생각해서 '가로로 긴 종이에 세로로 빨간 줄을 그리고,
그 종이를 반으로 접은 뒤 빨간 줄이 있는 부분만 남기고 나머지 부분을 찢어버리는 행동을
빨간 줄만 남을 때까지 반복'하는 겁니다.
 
Lower bound는 'key값 이상의 최초값'을 구하기 때문에 조금 코드가 달라집니다.
 

int lowerBound(int arr[], int key, int len)		// key값 이상의 최초값 - left를 key값에 미리 key값 이상 최초값에 같다놓고 right를 원하는 값에 두기 or 첨부터 right를 원하는 값에
{
	int left = 0, right = len;

	while (left < right)	// left와 right가 같거나 left값이 right보다 커질 때까지
	{
		int mid = (left + right) / 2;

		if (arr[mid] < key)
		{
			left = mid + 1;		// arr[mid]가 key값과 작을 때 left를 mid + 1로
		}
		else
		{
			right = mid;	// arr[mid]가 key값보다 같거나 클 때 right를 mid로
		}
	}


	return right;
}

 
일단, 코드를 짤 때 '반환값은 right기준'으로 할 겁니다.
일단, 배열(arr)과 key값, 그리고 배열의 길이(len)를 받아준 다음, left = 0, right = len으로 설정합니다.
이후 left < right일 동안 left ~ right의 중간값(mid)를 구해주고,
arr[mid]가 key보다 작으면 left = mid + 1arr[mid]가 key보다 같거나 크면 right = mid로 해주세요.
 
왜 left = mid + 1, right = mid이냐면,
이 코드는 left를 미리 key값의 인덱스에 가져다놓고, right가 left에 곂칠 때까지 기다리거나,
바로 right를 key값 인덱스에 가져다놓고 left가 곂칠 때까지 기다리기 때문입니다.
 
left = mid + 1이 실행되려면 arr[mid]값이 key값 전에 있어야 합니다.
즉, left = mid + 1이란 코드는 mid = key일 땐 실행되지 않는다는 뜻이죠.
그러면 left가 key값에 있을 때 left는 더 이상 값이 변하지 않을 겁니다.
 

Upper bound

int upperBound(int arr[], int key, int len)		// key값 초과의 최초값 - left를 미리 key값 초과 최초값에 같다놓고 right를 원하는 값에 두기 or 첨부터 right를 원하는 값에
{
	int left = 0, right = len;

	while (left < right)
	{
		int mid = (left + right) / 2;

		if (arr[mid] <= key)
		{
			left = mid + 1;		// arr[mid]가 key보다 같거나 클 때 left를 mid + 1
		}
		else
		{
			right = mid;	// arr[mid]가 key보다 작을 때 right를 mid로
		}
	}


	return right;
}

 
Lower bound의 설명과 비슷합니다.
반환값은 right기준이며, left가 'key값 초과 최초값'에 있을 시 더 이상 left값을 바뀌지 않습니다.
 

최종 코드

/* =============[ Upper bound, Lower bound Algorithim ]=============

	* 이분 탐색을 응용한 알고리즘
	* 
	* Lower Bound - 찾고자 하는 값 '이상'의 최초값 인덱스를 찾는 알고리즘
	* Upper Bound - 찾고자 하는 값 '초과'의 최초값 인덱스를 찾는 알고리즘
	* 
	* 찾고자 하는 값이 없어도 값이 나온다. - 만약 찾고자 하는 값이 없다면 Lower Bound = Upper Bound
	* 배열에서 같은 수가 여러 개 있을 때 그 수를 구하려면 Upper Bound - Lower Bound를 하면 된다.
	* 최종적으론 right를 반환함

	================================================================= */

#include <stdio.h>

#define ARR_LEN 18

int lowerBound(int arr[], int key, int len)		// key값 이상의 최초값 - left를 key값에 미리 key값 이상 최초값에 같다놓고 right를 원하는 값에 두기 or 첨부터 right를 원하는 값에
{
	int left = 0, right = len;

	while (left < right)	// left와 right가 같거나 left값이 right보다 커질 때까지
	{
		int mid = (left + right) / 2;

		if (arr[mid] < key)
		{
			left = mid + 1;		// arr[mid]가 key값과 작을 때 left를 mid + 1로
		}
		else
		{
			right = mid;	// arr[mid]가 key값보다 같거나 클 때 right를 mid로
		}
	}


	return right;
}

int upperBound(int arr[], int key, int len)		// key값 초과의 최초값 - left를 미리 key값 초과 최초값에 같다놓고 right를 원하는 값에 두기 or 첨부터 right를 원하는 값에
{
	int left = 0, right = len;

	while (left < right)
	{
		int mid = (left + right) / 2;

		if (arr[mid] <= key)
		{
			left = mid + 1;		// arr[mid]가 key보다 같거나 클 때 left를 mid + 1
		}
		else
		{
			right = mid;	// arr[mid]가 key보다 작을 때 right를 mid로
		}
	}


	return right;
}

int main()
{
	int arr[ARR_LEN] = { 1,1,2,3,3,3,4,4,7,7,7,7,7,7,9,9,9,9 };	// 임의의 정렬된 문자열
	int key = 0;

	scanf("%d", &key);

	int keyNum = upperBound(arr, key, ARR_LEN - 1) - lowerBound(arr, key, ARR_LEN - 1);	// arr내의 key값 개수 구하기

	printf("%d", keyNum);


	return 0;
}

 
Uppee/Upper bound를 구한 뒤, 둘의 차를 구한 후 이를 출력하는 코드입니다.
그 차를 구하면 '배열 내의 key값의 개수'를 알 수 있습니다.

---

 
이상으로 글을 마치겠습니다.끝까지 봐주셔서 감사합니다 :)
 

---

 

2023.07.17 - [Note/알고리즘] - "이중 연결리스트(Doubly Linked List)" 알고리즘 짜보기! - 초보자도 쉽게!
2023.10.21 - [Diary/코딩 잡 지식] - "float(실수) 타입의 저장 방식"에 대해 알아보자! - '0.1 + 0.2 == 0.3이 틀렸다고?'
2023.08.10 - [Diary/코딩 잡 지식] - "CUI(CLI)? GUI? 그게 뭔데?" - 'CUI와 GUI의 차이' 알아보기!