● 문제 링크 : www.acmicpc.net/problem/10815
● 풀이에 참고한 링크 :
* C++에서 char 배열 최대 크기, int 배열 최대 크기, vector의 최대 크기 - 2heedu.tistory.com/53
* 지역 변수의 정적 할당은 스택의 크기만큼만 할당 가능(1MB), 지역 변수의 동적 할당(힙 영역)과 전역 변수 할당은 좀 더 큰 메모리 만큼 할당 가능
* C++ 배열/벡터 정렬 - twpower.github.io/71-use-sort-and-stable_sort-in-cpp
* C++ 동적 할당시 초기값 - boycoding.tistory.com/205
● 내 풀이1 (2020.12.31.) :
Visual Studio 환경에서 C++로 int 타입의 지역 변수를 정적 배열로 할당하면
배열의 크기는 약 250,000개까지 가능하다. (경우에 따라 오차는 발생)
이보다 큰 크기의 배열를 할당하려면 전역 변수로 할당하거나 동적 할당을 해야 한다.
이는 지역 변수의 정적 할당이 스택에서 이루어지기 때문인데,
스택의 기본 크기는 1MB이고 사전 설정을 통해 크기 조절이 가능하다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; cin >> N;
int* n = new int[N]; // 동적 배열
for (int i = 0; i < N; i++) {
cin >> n[i];
}
sort(n, n + N);
for (int i = 0; i < N; i++) {
printf("%d ", n[i]);
}
cout << endl;
int M; cin >> M;
int* m = new int[M]; // 동적 배열
for (int i = 0; i < M; i++) {
cin >> m[i];
}
sort(m, m + M);
for (int i = 0; i < M; i++) {
printf("%d ", m[i]);
}
cout << endl;
int index = 0;
for (int i = 0; i < M; i++) {
bool flag = false;
for (int j = index; j < N; j++) {
if (n[j] == m[i]) {
flag = true;
continue;
}
}
if (flag==true) {
index++;
printf("1 ");
}
else {
printf("0 ");
}
}
return 0;
}결과 : 실패
원인 : 출력 순서는 정렬하기 전의 순서여야 한다.
내 풀이2 (2020.12.31.) :
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int* n = new int[20000001]();
int N; cin >> N;
for (int i = 0; i < N; i++) {
int index; cin >> index;
n[index+10000000] = 1;
}
int M; cin >> M;
for (int i = 0; i < M; i++) {
int index; cin >> index;
printf("%d ", n[index+10000000]);
}
return 0;
}
결과 : 성공
분석 : 탐색에 대한 시간복잡도가 O(1)이지만 메모리를 많이 차지하는 방법
* 이분 탐색이란? wootool.tistory.com/62
* 이분 탐색 이용시, 탐색에 대한 시간복잡도가 O(n)에서 O(logn)으로 감소
* 주의 사항 : 이분 탐색은 먼저 리스트를 정렬한 상태에서 진행해야 함
* 이분 탐색 코드 예시
#include <iostream>
#include <time.h>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int size = 10; // 배열의 크기
int value_to_find; // 찾고자 하는 값
int index_to_find = -1; // 찾고자 하는 값의 인덱스
int* arr = new int[size]();
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100;
}
sort(arr, arr + size); // 정렬된 상태에서 진행
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
cout << endl;
printf("찾고자 하는 값 : "); cin >> value_to_find;
// 이진 탐색
int left = 0, right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > value_to_find) right = mid - 1;
else if (arr[mid] < value_to_find) left = mid + 1;
else
{
index_to_find = mid;
break;
}
}
printf("인덱스 = %d\n", index_to_find);
return 0;
}* 이분 탐색(=이진 탐색 =Binary Search) 알고리즘의 라이브러리화(함수화)
1) 배열 내 이분 탐색
#include <iostream>
#include <time.h>
#include <algorithm>
using namespace std;
int my_binary_search(int* arr, int size, int value) {
int index = -1; // 찾고자 하는 값의 인덱스
int left = 0, right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > value) right = mid - 1;
else if (arr[mid] < value) left = mid + 1;
else
{
index = mid;
break;
}
}
return index;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int size = 10; // 배열의 크기
int value_to_find; // 찾고자 하는 값
int index_to_find = -1; // 찾고자 하는 값의 인덱스
int* arr = new int[size]();
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100;
}
sort(arr, arr + size); // 정렬된 상태에서 진행
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
cout << endl;
printf("찾고자 하는 값 : "); cin >> value_to_find;
index_to_find = my_binary_search(arr, size, value_to_find);
printf("인덱스 = %d\n", index_to_find);
return 0;
}2) 벡터 내 이분 탐색
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
using namespace std;
int my_binary_search(vector<int>& vec, int size, int value) {
int index = -1; // 찾고자 하는 값의 인덱스
int left = 0, right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (vec.at(mid) > value) right = mid - 1;
else if (vec.at(mid) < value) left = mid + 1;
else
{
index = mid;
break;
}
}
return index;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int size = 10; // 배열의 크기
int value_to_find; // 찾고자 하는 값
int index_to_find = -1; // 찾고자 하는 값의 인덱스
vector<int> vec;
srand(time(NULL));
for (int i = 0; i < size; i++) {
vec.push_back(rand() % 100);
}
sort(vec.begin(), vec.end()); // 정렬된 상태에서 진행
for (int i = 0; i < size; i++) {
printf("%d ", vec.at(i));
}
cout << endl;
printf("찾고자 하는 값 : "); cin >> value_to_find;
index_to_find = my_binary_search(vec, size, value_to_find);
printf("인덱스 = %d\n", index_to_find);
return 0;
}3) C++ STL(algorithm 헤더 파일)에 있는 내장 함수 binary_search()
사용법 : binary_search(start_index, end_index, value_to_find); // arr와 vec 모두 가능
리턴값 : 탐색한 value의 index를 int 타입으로 반환하지 않고, 탐색한 value의 존재 유무만 bool 타입으로 반환
내 풀이3 (2020.12.31.) - 이분 탐색 이용
* 풀이에 참고한 링크 : jaimemin.tistory.com/991
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N;
int* arr_n = new int[N]();
for (int i = 0; i < N; i++) {
cin >> arr_n[i];
}
sort(arr_n, arr_n + N);
cin >> M;
int* arr_m = new int[M]();
for (int i = 0; i < M; i++) {
cin >> arr_m[i];
}
for (int i = 0; i < M; i++) {
printf("%d ", binary_search(arr_n, arr_n + N, arr_m[i]));
}
return 0;
}결과 : 성공
분석 : 시간복잡도 = mlog(n)
< 코딩 테스트에서 표준 라이브러리(STL) 사용 가능 유무 >
- 이 문제의 경우, binary_search 함수 때문에 algorithm 라이브러리를 사용했음
- 삼성 역량 테스트 B형은 stdio/iostream를 제외한 모든 라이브러리 사용 불가
- 대부분의 대기업(프로그래머스 기반 코딩 테스트)은 라이브러리 사용 가능
'알고리즘 > 이분탐색' 카테고리의 다른 글
| 백준 1654번 : 랜선 자르기 (0) | 2021.01.21 |
|---|---|
| 백준 2805번 : 나무 자르기 (0) | 2021.01.17 |
| 백준 1920번 : 수 찾기 (0) | 2021.01.16 |
| 이분 탐색 개념 (0) | 2021.01.16 |
