결정 알고리즘(Decision Algorithm)과 파라메트릭 서치(Parametric Search)
결정 알고리즘과 파라메트릭서치를 배우기 전에 이진 탐색(Binary Search, 이분 검색)에 대한 이해가 선행되어야 한다. 따라서, 이진 탐색에 대해서 먼저 배워보도록 하겠다.
순차 탐색(Sequential Search)
순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용하며, 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 결과를 찾을 수 있다.
구현
/**
* @param n 입력 데이터 개수
* @param target 찾고자 하는 문자열
* @param arr 배열
*/
public static int sequantialSearch(int n, String target, String[] arr) {
// 각 원소를 하나씩 확인하며
for (int i = 0; i < n; i++) {
// 현재의 원소가 찾고자 하는 원소와 동일한 경우
if (arr[i].equals(target)) {
return i + 1; // 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
}
}
return -1; // 원소를 찾지 못한 경우 -1 반환
}- 시간 복잡도
O(N)- 최악의 경우에는 데이터 개수가 N 개일 때 N 번의 비교 연산이 필요하기 때문이다.
이진 탐색(Binary Search)
이진 탐색이라고도 부르고 이분 검색이라고도 부른다. 이진 탐색은 말 그대로 반으로 쪼개서 찾고자 하는 값이 해당되지 않는 범위는 날리고, 다시 쪼개진 반에서 이분 검색을 실시한다. 이분 검색을 실시하기전에 오름차순 정렬이 되어있어야 한다.
특징
- 탐색 범위를 반으로 좁혀가면서 탐색
- 이진 탐색을 하기 위한 전제 조건(precondition) : 탐색을 실시하기전에
오름차순 정렬이 되어있어야 한다. - 입력 데이터 개수의 범위가 1,000 만을 넘어가면 이진 탐색 혹은
O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 한다. - 위치를 나타내는 변수 3개 사용 :
시작점(startPoint = 0), 끝점(endPoint = n-1), 중간점(middlePoint)- 각 Point 들은 값이 아닌 배열의
Index를 나타낸다.
- 각 Point 들은 값이 아닌 배열의
- 이진 탐색은 데이터를 절 반씩 줄여가면서 탐색하기 때문에 시간 복잡도는
O(logN)이다.
구현 절차
- 배열을 오름차순으로 정렬 (정렬이 안되어있다 가정) :
Arrays.sort(arr); - 시작점, 끝점 초기화
- 중간점 계산식 :
middlePoint = (startPoint + endPoint) / 2;- 중간점(middlePoint)이 실수일 경우에는 소수점을 버린다. (Ex. (0 + 3) / 2 -> middlePoint = 1)
- 중간점과 찾고자 하는 값(target)을 비교한다.
- 찾고자 하는 데이터가 더 작은 쪽에 속하면 끝점 index 를 감소 :
endPoint = middlePoint - 1; - 찾고자 하는 데이터가 더 큰 쪽에 속하면 시작점 index 를 증가 :
startPoint = middlePoint + 1; - 2번 또는 3번을 수행하고나서 1번(중간점 계산식)을 수행. 즉, 중간점을 다시 계산
찾으려는 데이터와 중간점(Middle) 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정
"이진 탐색에 대한 구현은 손 코딩으로도 나올만한 문제라고 한다. 따라서 절차를 잘 기억하고 있어야 한다."
반복문으로 구현
private static int n; // 입력 데이터 개수
private static int[] arr; // 탐색 대상인 배열
private static int target; // 찾고자 하는 값
public static int solution() {
// 찾고자 하는 값의 위치
int targetIndex = 0;
// 시작점, 끝점 초기화
int startPoint = 0;
int endPoint = n - 1;
// 배열 오름차순 정렬
Arrays.sort(arr);
// endPoint 의 index 가 더 크거나 같을 때 까지 반복
while(startPoint <= endPoint) {
// 중간점 계산
// while 문 안에 선언하는 이유는 아래에서 startPoint 와 endPoint 의 인덱스 변화가 있을때 다시 계산하기 위함이다.
int middlePoint = (startPoint + endPoint) / 2;
// 중간점이 target 값과 동일한 경우
if(arr[middlePoint] == target) {
targetIndex = middlePoint; // 문제에 따라서 위치 번호를 출력하라고 하면 middlePoint + 1 이 될 수도 있음.
break;
}
// 찾고자 하는 데이터가 더 작은 쪽에 속하면 끝점 index 를 감소
if(arr[middlePoint] > target) {
endPoint = middlePoint - 1;
}
// 찾고자 하는 데이터가 더 큰 쪽에 속하면 시작점 index 를 증가
else {
startPoint = middlePoint + 1;
}
}
return targetIndex;
}재귀로 구현
재귀는 사실 별로 추천하지 않는다. 현업에서도 재귀를 쓸일이 많이 없으며, 쓴다하더라도 재귀의 늪에 빠질 수 있기 때문에 가급적 추천하지 않는다. 또한, 재귀를 쓴다고하면 재귀를 쓴 이유부터해서 면접 때, 트집잡을게 많아진다고 생각한다.
public static int binarySearch(int[] arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else return binarySearch(arr, target, mid + 1, end);
}결정 알고리즘과 파라메트릭 서치
파라메트릭 서치(Parametric Search)는 Parametirc 이라는 단어를 보면 알 수 있듯이 매개 변수를 이용한 탐색 기법이라는 것을 알 수 있다. 파라메트릭 서치(Parametric Search) 는 최적화 문제 를 결정 문제 로 바꾸어 해결하는 기법이다. 즉, 결정 알고리즘(Decision Algorithm)을 사용한다. 결정 알고리즘은 이진 탐색(Binary Search)을 사용하는데 구하고자하는 답이, 원소의 나열 안(배열)에(<-startPoint---------------endPoint->) 존재하는 경우에 사용한다. 문제의 풀이 아이디어는 구하고자하는 답(answer)을 반복해서 조정한다.
자, 이해하기 쉽게 정리하자면 "파라메트릭 서치(Parametric Search)는 매개변수를 이용한 탐색 기법이며 최적화된 답을 구하기 위해 결정 알고리즘을 사용한다." 라고 할 수 있다.
대부분의 블로그 글을 보더라도 파라메트릭 서치(Parametric Search)는 최적화된 문제를 결정문제로 바꾸어서 푼다라고만 설명되어있다. 매개변수라는 포인트를 짚어서 설명한 글을 찾기가 힘들다. 책을 포함한 결정 알고리즘 문제 3개를 분석하면서 왜 Parametric 이라는 단어를 썼을까 분석해보았다. 개인적인 의견이 들어간 부분일 수 있어서 필터링 해서 받아들이면 될 것 같다.
파라메트릭 서치
- 파라메트릭 서치(Parametric Search)
- 매개 변수를 이용한 탐색 기법
- 최적화 문제를 결정 알고리즘을 사용하여 해결
- 결정 알고리즘은 이진 탐색을 사용
- 결정 알고리즘은 원소의 나열 안에 구하고자 하는 답이 존재하는 경우 사용
- 문제 풀이 아이디어 : 구하고자하는 답(answer)을 반복해서 조정
- 즉, 구하고자 하는 답(answer)는 반복문 안에서 계속해서 변경된다.
- 구하고자하는 답(answer)은 반복문안에서 계속해서 변경되는 중간점(middlePoint)를 의미한다.
- 즉, 결정 알고리즘에서는 최종적으로 middlePoint 가 answer 가 된다.
- 단순 이진 탐색 구현과의 차이점
- 함수를 사용한다.
- 결정 알고리즘에서 시작점(startPoint) : 입력 값 n 의 시작 범위 (1 <= n <= 10000 이므로 1)
- 결정 알고리즘에서 끝점(endPoint) : 배열의 마지막 원소 값(
arr[n-1]) - 반복문이 끝난 middlePoint 가 answer 가 된다.
- 문제를 읽고 파라메트릭 서치(Parametric Search) 사용해야하는지 안하는지에 대한 판단 기준
- 최적화된 값을 요구한다.
- 구하고자 하는 값의 범위가 상당히 큰 경우
- 이분 검색을 사용해야 하는 경우
- Hint. 위 세개와 비슷한 느낌을 받으며, 문제에서 다음과 같은 문구가 주어진다.
최댓값 혹은 최솟값 을 구하세요. 출력하세요.이러면 거의 결정 알고리즘(Decision Algorithm) 문제일 가능성이 높다.- Ex. 첫 줄에 ~ 최대 거리를 출력하세요.
- Ex. 첫 줄에 ~ 최솟값을 출력하세요.
다시, Parametric 이라는 단어가 왜 사용되었을지 분석해보자. "매개변수를 이용한다라는 의미가 무엇일까 ?" 매개변수는 함수(메서드) 시그니처에 존재하는 변수이다. 즉, 함수를 사용한다는 것이다.
함수를 사용하는데 그러면 어떤 함수를 만들라는 것인지 궁금할 수 있다. 핵심은 구하고자하는 답(answer)을 반복해서 조정하기 위한 판단을 내려주는 함수 를 만드는 것이다. 즉, 최적화된 값을 구하기 위해 판단을 내려주는 함수라고 생각하면 된다. 문제 마다 조건이 다르기 때문에 함수의 내부 구현 방식이 당연히 달라진다.
최적화된 값을 구하기 위해 판단을 내려주는 함수(decisionToFindTheOptimizedValue)를 사용한다라는 것까진 이해가 됐을것이다. 그러면 해당 함수에 어떤 파라미터(Parameter)를 넘겨주는지가 두 번째 핵심인데, 입력 값을 가지고 있는 배열과 구하고자하는 답(answer)을 파라미터로 넘겨준다. (만약, 배열을 static 으로 선언했다면 answer 만 넘겨주면 될 것이다. 어쨋든 함수 내부에서는 배열과 answer 둘 다 필요하다라는 의미이다.)
decisionToFindTheOptimizedValue 함수의 결과랑 조건(M)의 값과 비교하여 조건이 함수의 결과보다 작거나 같으면 시작점(startPoint)을 증가시키면서 answer 의 값을 중간점(middlePoint)으로 갱신해주면 된다. 함수의 결과보다 큰 경우에는 끝점(endPoint)을 감소시킨다. 근데 이 부분은 문제에서 최댓값을 구하는 경우에 그렇다.
최댓값을 구하는 경우
if(decisionToFindTheOptimizedValue(arr, middlePoint) >= m) {
answer = middlePoint;
startPoint = middlePoint + 1;
} else {
endPoint = middlePoint - 1;
}반면 최솟값을 구하는 경우에는 조금 달라질 수도 있다.
최솟값을 구하는 경우
if(decisionToFindTheOptimizedValue(arr, middlePoint) <= m) {
answer = middlePoint;
endPoint = middlePoint - 1;
} else {
startPoint = middlePoint + 1;
}문제 : 떡볶이 떡 만들기
해당 풀이는 "이것이 코딩 테스트다"에 나와있는 문제에 대한 풀이다.
public class Main {
private static int n; // 입력 데이터 개수
private static int m; // 조건(condition) : 손님이 얻고자 하는 떡의 길이
private static int[] arr; // 배열
public static void main(String[] args) {
initializeInputData();
System.out.println(decisionAlgorithm());
}
private static void initializeInputData() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
}
// 결정 알고리즘(Decision Algorithm)
private static int decisionAlgorithm() {
// 문제에 따라서, 오름차순 정렬을 해야할 수도 있고, 안할 수도 있다.
// 해당 문제에서는 필요 없는 코드이다.
// ascendingSort(riceCakes);
int answer = 0; // 구하고자하는 답
int startPoint = 1; // 입력 값 n 의 시작 범위 (1 <= n <= 1000000 이므로 1)
int endPoint = arr[n - 1]; // 배열의 마지막 원소 값
while(startPoint <= endPoint) {
int middlePoint = (startPoint + endPoint) / 2;
if(decisionToFindTheOptimizedValue(middlePoint) >= m) {
answer = middlePoint; // 구하고자하는 답(answer)을 반복해서 조정
startPoint = middlePoint + 1;
} else {
endPoint = middlePoint - 1;
}
}
return answer;
}
private static void ascendingSort(int[] arr) {
Arrays.sort(arr);
}
private static int decisionToFindTheOptimizedValue(int middlePoint) {
int sum = 0;
for(int element : arr) {
if(element > middlePoint) {
sum += element - middlePoint;
}
}
return sum;
}
}즉, 다음과 같이 정리할 수 있다. 결정 알고리즘을 구현하는 메서드 안은 이진 탐색 코드가 적용되어 있으며, 이진 탐색 코드에서는 최적화된 값을 구하기 위해 판단을 내려주는 함수를 만들어서 사용한다.
실제로 이와 비슷하거나 조금 어려운 수준의 결정 알고리즘을 사용하는 문제들의 풀이 형식을 보면 달라지는 곳은 딱 정해져있다. 최댓값을 구하는지 최솟값을 구하는지에 따라 while 문 내부가 달라지며,
문제의 조건에 맞는 최적화된 값을 구하기 위해 decisionToFindTheOptimizedValue() 함수의 내부 구현이 달라진다.
func decisionAlgorithm() {
Binary Search Algorithm code {
func decisionToFindTheOptimizedValue();
}
}단, 결정 알고리즘을 사용하는 모든 문제가 이렇다라는것은 아니다.(맞을 수도 있고 아닐 수도 있고), 하지만 몇몇 문제를 분석해본 결과 떡볶이 문제랑 비슷하거나 조금 더 어려운 수준의 문제는 위와 같은 스타일로 해결할 수 있는 것 같다.
References
'Algorithms > 기본 지식' 카테고리의 다른 글
| 서로소 집합 (0) | 2021.12.12 |
|---|---|
| 플로이드 워셜 알고리즘 (0) | 2021.12.12 |
| 최단 경로와 다익스트라 알고리즘 (0) | 2021.12.11 |
| 다이나믹 프로그래밍 (0) | 2021.12.11 |
| 재귀 함수(Recursion Function) (1) | 2021.12.08 |