C++ 알고리즘 기초22 -배열 심화2(최대, 최소 찾기, 정렬하기, 그리디 연습)-
1. 연습문제1
n개의 원소와 q개의 질의가 주어졌을 때 n개의 원소에 대해 각 질의를 수행하는 프로그램을 작성해보세요. 질의의 종류는 다음과 같습니다.
- 1 a
- a번째 원소를 출력합니다.
- 2 a
- 숫자 a가 있는지를 판단합니다. 만약 있다면 해당 원소가 몇 번째 원소인지를 출력합니다. 숫자 a가 2개 이상 있다면 index가 더 작은 원소를 출력합니다. 만약 a가 없다면 0을 출력합니다.
- 3 a b
- a번째 원소부터 b번째 원소까지 순서대로 공백을 사이에 두고 출력합니다.
문제 요구하는대로 구현하면 된다
a번째랑 index가 a인 것은 다르니까 헷갈리지 말고
C++ 특성상 첫 숫자 1,2,3중 하나를 받아 1,2,3인지 체크하고, 1,2면 하나만 더 받고 3이면 2개를 받고
#include <iostream>
using namespace std;
int main() {
// 여기에 코드를 작성해주세요.
int n,q;
cin >> n >> q;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
for(int i = 0; i < q; i++){
int x;
cin >> x;
if(x == 1){
int y;
cin >> y;
cout << arr[y-1];
} else if (x == 2){
int y;
cin >> y;
bool find = false;
int answer = -1;
for (int i = 0; i < n; i++){
if(y == arr[i]){
find = true;
answer = i+1;
break;
}
}
if (find == true){
cout << answer;
} else {
cout << 0;
}
} else if ( x == 3){
int a,b;
cin >> a >> b;
for(int i = a-1; i < b; i++){
cout << arr[i] << " ";
}
}
cout << endl;
}
return 0;
}
여기서 주의할 점이 x == 2일때 bool find = false;인데
처음에 bool find = false; 선언하고 중간에 bool find = true; 선언하면
bool find = false;한 순간 새로운 find를 선언해서...
for문 끝나고 if문으로 find 검사할때 for문 앞에있 는 bool find = false;를 찾아가지고
항상 find가 false로 인식되는듯?
} else if (x == 2){
int y;
cin >> y;
bool find = false;
int answer = -1;
for (int i = 0; i < n; i++){
if(y == arr[i]){
bool find = true;
answer = i+1;
break;
}
}
if (find == true){
cout << answer;
} else {
cout << 0;
}
2. 연습문제2
n1개의 원소로 이루어져 있는 수열 A의 정보와, n2개의 원소로 이루어져 있는 수열 B의 정보가 주어졌을 때 수열 B가 수열 A의 연속부분수열인지를 판단하는 프로그램을 작성해보세요.
수열 B가 수열 A의 원소들을 연속하게 뽑았을 때 나올 수 있는 수열이라면 연속부분수열이라 부릅니다.
예를 들어 수열 A가 [1, 5, 2, 6] 일때 수열 B가 [5, 2]라면 수열 B는 수열 A의 연속 부분 수열이지만, 만약 수열 B가 [5, 6]이라면 연속 부분 수열이 아닙니다.
B의 길이가 길 수 있어서 B의 길이가 길다면 A의 부분수열일수 없으니까 바로 NO를 출력
그렇지 않다면 브루트포스로 찾아본다
#include <iostream>
using namespace std;
int main() {
// 여기에 코드를 작성해주세요.
int n1,n2;
cin >> n1 >> n2;
int A[n1];
int B[n2];
for(int i = 0; i < n1; i++){
cin >> A[i];
}
for(int i = 0; i < n2; i++){
cin >> B[i];
}
if (n1 < n2){
cout << "No";
} else {
bool find = true;
for(int i = 0; i < n1-n2+1; i++){
find = true;
for(int j = i; j < n2+i; j++){
if (A[j] != B[j - i]){
find = false;
break;
}
}
if(find == true){
break;
}
}
if(find == true){
cout << "Yes";
} else {
cout << "No";
}
}
return 0;
}
여기서 핵심은 A의 시작 시점을 j = i로 찾으면... B의 시작 시점은 항상 0번부터 시작해야하므로, j-i로 인덱싱해야하고,
j의 최댓값은 n2+i-1로 해줘야한다는 것
for(int i = 0; i < n1-n2+1; i++){
find = true;
for(int j = i; j < n2+i; j++){
if (A[j] != B[j - i]){
find = false;
break;
}
}
if(find == true){
break;
}
}
3. 최댓값 찾기
배열 내에서 가장 큰 값을 찾을때, 최댓값의 초기값이 중요한데, 단순히 0으로 초기화한다면...
배열 내 원소가 음수가 섞여있으면 예상과는 다른 값이 나올 수 있다.
이를 해결하기 위한 방법으로는...
<climits> 헤더의 INT_MIN은 int 범위 내에서 가장 작은 값을 나타내며 이를 초기값으로 설정
#include <iostream>
#include <climits>
using namespace std;
int main() {
int arr[6] = { -1, -5, -2, -5, -3, -9 };
int max_val = INT_MIN;
for (int i = 0; i < 6; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
}
cout << max_val;
return 0;
}
>> -1
INT_MIN이 생각이 안나면, 배열의 첫번째 원소를 초기값으로 설정하고.. 두번째 원소부터 비교해나간다
#include <iostream>
using namespace std;
int main() {
int arr[6] = { -1, -5, -2, -5, -3, -9 };
int max_val = arr[0];
for (int i = 1; i < 6; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
}
cout << max_val;
return 0;
}
>> -1
4. 최솟값 찾기
최솟값을 찾을때는 climits 헤더에 존재하는 정수 범위내에서 가장 큰 값 INT_MAX를 이용
#include <iostream>
#include <climits>
using namespace std;
int main() {
int arr[6] = { 11, 15, 12, 15, 13, 19 };
int min_val = INT_MAX;
for (int i = 0; i < 6; i++) {
if (min_val > arr[i]) {
min_val = arr[i];
}
}
cout << min_val;
return 0;
}
>> 11
혹은 첫번째 원소를 초기값으로 설정하고 두번째 원소부터 비교를 해나간다.
#include <iostream>
using namespace std;
int main() {
int arr[6] = { 11, 15, 12, 15, 13, 19 };
int min_val = arr[0];
for (int i = 1; i < 6; i++) {
if (min_val > arr[i]) {
min_val = arr[i];
}
}
cout << min_val;
return 0;
}
>> 11
5. 연습문제3(그리디)
향후 n년 간의 자동차 가격 정보가 미리 주어졌을 때, 자동차를 단 한 번 사서 되팔 때의 이익을 최대화하고자 합니다. 낼 수 있는 최대 이익을 출력하는 프로그램을 작성해보세요. 단, 자동차를 사기 전에는 팔 수 없습니다.
유명한 그리디 문제
뒤에서부터 배열을 순회해서, 가장 큰 값을 저장해놓고, 매 순간 현재 가장 큰 값보다 작다면 차익을 구해 저장하고,
현재 가장 큰 값보다 크다면, 이 값을 갱신해준다
첫번째 원소까지 순회하면 차익의 최댓값을 출력
#include <iostream>
#include <climits>
using namespace std;
int main() {
// 여기에 코드를 작성해주세요
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int max = arr[n-1];
int answer = 0;
for(int i = n-2; i >= 0; i--){
if (arr[i] > max){
max = arr[i];
} else {
if (max-arr[i] > answer){
answer = max - arr[i];
}
}
}
cout << answer;
return 0;
}
6. 연습문제4(그리디)
N개의 숫자가 주어졌을 때, 주어진 숫자들 중 최댓값의 위치를 출력합니다. 만약 최댓값이 여러 개라면, 가장 왼쪽에 있는 최댓값의 위치를 출력합니다.
그 이후에는 위에서 구한 최댓값의 위치보다 더 왼쪽에 있는 숫자들 중 최댓값을 구해 그 위치를 출력합니다. 이 경우에도 최댓값이 여러 개라면, 가장 왼쪽에 있는 최댓값의 위치를 출력합니다.
위의 과정을 끊임없이 반복하며, 최종적으로 첫 번째 원소가 뽑히게 되면 이 과정을 종료합니다. 이러한 과정을 거쳐 구해진 최댓값의 위치들을 출력하는 프로그램을 작성해보세요.
그대로 구현해도 되지만 그리디하게 접근할 수도 있다
예를 들어 배열 [1,3,3,5,5]에서 답으로 출력되는 것은 4번째, 2번째, 1번째인데...
바꿔 생각하면 맨 처음 원소는 항상 최댓값이 될 수 있으므로 첫 원소를 기준 원소로 저장하고,
매 순간 기준 원소보다 커지면 해당 원소의 인덱스를 출력하는 방식으로 접근하면 된다
처음에 1이니까 위치 1을 저장해두고, 다음 2번째 3은 처음으로 1보다 커지니까 2번째를 저장하고 기준 원소를 3으로 변경
다음 3번째 3은 2번째와 같으니 넘어가고,
다음 4번째 5가 처음으로 2번째보다 커지니 4를 저장하고 5를 기준 원소로 저장..
마지막 5번째는 5와 같으니 넘어가고
#include <iostream>
using namespace std;
int main() {
// 여기에 코드를 작성해주세요.
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int index_arr[n+1];
int count = 1;
index_arr[count] = 1;
for(int i = 1; i < n; i++){
if(arr[i] > arr[index_arr[count]-1]){
count += 1;
index_arr[count] = i+1;
}
}
for(int i = count; i >= 1; i--){
cout << index_arr[i] << " ";
}
return 0;
}
7. 정렬함수 sort
<algorithm> 헤더에 sort()함수로 배열을 정렬할 수 있다
sort(start,end,key) 형태로 사용
start로 배열의 포인터 arr을 넣어주고
end로 배열의 포인터 arr + 배열의 길이 n을 넣어준다
마지막 key는 사용자 정의 함수로 원하는 기준에 맞춰 정렬하고 싶을때 직접 정의해서 사용
key를 쓰지 않으면 기본으로 오름차순 정렬을 해준다.
대신에 greater<자료형>()을 넣어주면 내림차순 정렬을 해준다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// 여기에 코드를 작성해주세요.
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr,arr+n,greater<int>());
cout << arr[0] << " " << arr[1];
return 0;
}
다음과 같이 compare함수를 직접 정의해서 내림차순 정렬할 수도 있다
bool compare(int x, int y) {
return x > y;
}
함수 쓰는법 아직 배우진 않았는데..
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int x, int y) {
return x > y;
}
int main() {
// 여기에 코드를 작성해주세요.
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr,arr+n,compare);
cout << arr[0] << " " << arr[1];
return 0;
}
[C++ STL] sort 정렬 함수 사용 방법 정리 (오름차순 & 내림차순)
INFO C++ STL 라이브러리의 algorithm 헤더는 sort 정렬 함수를 제공합니다. sort 정렬 함수는 intro sort 정렬 알고리즘을 이용하는데 이는 quick sort 정렬 알고리즘을 기반으로 한 heap sort 와 insertion sort 를
novlog.tistory.com
'알고리즘 > C++ 기초' 카테고리의 다른 글
| C++ 알고리즘 기초21 -배열 심화1(C++ 배열 초기화)- (0) | 2023.06.10 |
|---|---|
| C++ 알고리즘 기초20 -문자열 심화1(마지막 문자 인덱싱, length()함수 overflow 문제, to_string()함수, 문자열의 끝)- (0) | 2023.06.09 |
| C++ 알고리즘 기초19 -반복문 심화3(무한루프 만들기, 비교연산자 주의할점, 반복문에서 i값 가져오기)- (0) | 2023.06.07 |
| C++ 알고리즘 기초18 - 반복문 심화2(10의 자리와 1의 자리 구하는 방법 복기)- (0) | 2023.06.06 |
| C++ 알고리즘 기초17 -문자열 입력받기, 문자열 길이 구하기(length), 공백을 포함한 문자열 입력받기(getline)- (0) | 2023.05.30 |
