숫자 카드: 백준 10815번 문제
n개의 카드를 받았을 때,
m개의 숫자카드 중 가지고있는 카드가 무엇무엇인지를 판단하는 문제
문제 이해 및 풀이
arr1에 n개의 숫자를 받고,
std::sort 알고리즘으로 미리 정렬해놓는다.
sort 알고리즘은 <algorithm> 헤더파일에 있고
퀵소트로 정렬하여 O(nlogn)의 시간복잡도를 가진다.sort(start, end, compare)으로
첫번째인자는 시작주소,
두번째인자는 끝주소,
마지막인자는 비교함수를 옵션으로 넣어줄 수 있다.
기본값은 오름차순 정렬이다.
다시 돌아와서,
m개의 숫자를 받아
각 숫자가 n개의 카드에 존재하는지 여부를 출력해주기 위해
바이너리서치 함수로 전달한다.
함수로 배열을 전달할 때 길이정보가 같이 넘어가지는 않으므로, 꼭 인자로 따로 넘겨주어야 한다.
재귀적 방법과 반복문을 사용하는 방법 두 가지가 있다.
재귀적 방법
처음 인덱스 0부터 끝까지 인자로 넘겨놓고,
매번 중간값을 확인한 후
더 클경우 중간값+1을 first값으로 재귀호출한다.
더 작을경우 중간값-1을 last값으로 재귀호출한다.
찾지 못했는데 first값이 last값을 초과해버리면 원하는 값이 없는것.
직관적 이해:search(first=1, first=2) 호출의 경우
인덱스 1 2에서 중간값은 1이되고 없을경우 중간값1+1=2가 초기값 first가 된다.
즉 search(first=2, last=2)가 된다.
이번호출에서는 중간값이 2가되고 fisrt=3 last=2가 되어 탈출조건을 만족한다.
void search(int* arr1, int a, int first, int last) {
if(first>last) {
printf("0");
return;
}
int mid = (first + last) / 2;
if(arr1[mid] == a) {
printf("1");
return;
}
else if(arr1[mid] < a)
search(arr1, a, mid+1, last);
else if(a < arr1[mid])
search(arr1, a, first, mid-1);
}
// 함수 호출부
search(arr1, arr2[i], 0, len-1);반복문 사용 방법
함수 호출에는 배열, 찾고자하는 값, 배열길이를 인자로 넘겨준다.
while문에서 마찬가지로 first가 last를 초과하는 순간을 탈출조건으로 잡는다.
void search(int* arr1, int a, int len) {
int first = 0;
int last = len-1;
int mid;
while(first<=last) {
mid = (first+last)/2;
if(arr1[mid]==a) {
printf("1");
return;
}
else if(arr1[mid]<a) {
first = mid+1;
}
else {
last = mid-1;
}
}
printf("0");
return;
}'IT' 카테고리의 다른 글
| 포인터변수의 이해와 주소연산자 (0) | 2022.06.28 |
|---|---|
| 배열과 포인터의 공통점과 차이점 (0) | 2022.06.28 |
| [백준 2609] 최대공약수와 최소공배수 (0) | 2022.06.21 |
| KaTeX: 더 빠른 성능의 수식 입력 라이브러리 (0) | 2022.06.20 |
| [백준 20353] C언어 기본 자료형 정리 (0) | 2022.06.16 |
