문제도 짧고 흔할 것 같이 생긴 문제였다. 당장 생각나는 것은 입력받은 값들을 순회(for)를 돌면서 그 순회 속에 순회(for)를 돌아서 전것들과 비교하면서 하는 것이였다. 하지만, 요즘 Time Limit을 신경쓰고 있어서 그런지 이중 순회(for)를 안쓰려고 했다.
그래서 생각해낸 방법은 입력 받은 수들을 배열(a)에 저장하고 그 값들을 또 새로운 배열(b)에 저장한다. 배열 a를 다시 sort 함수를 이용해 오름차순으로 정렬하고 다음 값과 같지 않으면 전체 인원 - 인덱스를 빼준다. 이러면, 다음 값이 같은 값이여도 등수문제를 해결할 수 있다.
이중 순회(for)를 안써서 시간상으로는 조금 더 빠르겠지만 메모리를 많이 잡아먹는 다는 단점과 라이브러리를 많이 사용한다는 단점이 있다.
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
using namespace std;
int c[101];
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i;
scanf("%d", &n);
int *a = (int *)malloc(sizeof(int) * (n+1));
int *b = (int *)malloc(sizeof(int) * (n+1));
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
memcpy(b, a, sizeof(int)*(n+1));
sort(a, a+n);
for(i=0; i<n; i++){
if(a[i] != a[i+1]){
c[a[i]] = n-i;
}
}
for(i=0; i<n; i++){
printf("%d ", c[b[i]]);
}
free(a);
free(b);
return 0;
}
배열 두 개를 가지고 코드를 짜 보았다. a 배열은 순전히 입력된 수만 저장하는 배열이고 b 배열은 인접한 두 수의 차이의 절대값을 index로 삼아 값을 바꿔주었다. 그래서 0이 아닌 값이 존재하면 유쾌한 점퍼(jolly jumper)가 아니므로 NO를 출력하고 모두 0이면 YES를 출력한다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, temp;
bool flag = true;
scanf("%d", &n);
int *a = (int *)malloc(sizeof(int)*n);
int *b = (int *)malloc(sizeof(int)*n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=0; i<n-1; i++){
temp = abs(a[i+1]-a[i]);
b[temp] = 0;
}
for(i=1; i<n; i++){
if(b[i]!=0){
flag = false;
break;
}
}
if(flag) printf("%s", "YES");
else printf("%s", "NO");
free(a);
free(b);
return 0;
}
결과는 통과하였다.
사이트의 답안
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n, i, now, pre, pos;
scanf("%d", &n);
vector<int> ch(n);
scanf("%d", &pre);
for(i=1; i<n; i++){
scanf("%d", &now);
pos=abs(pre-now);
if(pos>0 && pos<n && ch[pos]==0) ch[pos]=1;
else{
printf("NO\n");
return 0;
}
pre=now;
}
printf("YES\n");
return 0;
}
사이트의 답은 두 값의 차이의 절대값이 총 개수-1의 범위안에 있는지와 중복의 유무가 핵심이였다. 전 값 pre와 다음 값 now를 선언하고 두 값의 차이의 절대값을 pos 변수로 두었다. 제일 첫 번째 값을 pos로 입력을 받은 뒤 순회(for)를 돌며 절대값을 구하고 절대값이 총 개수보다 작은지를 판별하고 벡터의 pos 인덱스가 0인지를 확인하며 중복을 검사한다. 중복 값이 있다는 것은 나머지 부분에 무조건 공백이 존재한다는 것을 말해준다. 검사가 끝나면 pre값을 now로 바꿔주고 순회를 이어간다. 순회를 마치면 모든 값이 존재하므로 유쾌한 점퍼(Jolly Jumpers)가 된다.
C++ 의 표준 템플릿 라이브러리 (STL) 은 간단하며 효율적인 도구이다. 보통 C++의 STL은 임의 타입의 객체를 보관할 수 있는 컨테이너(Container)와 컨테이너에 보관된 원소에 접근할 수 있는 반복자(Iterator), 그리고 반복자들을 가지고 일련의 작업을 수행하는 알고리즘(algorithm)을 의미한다.
여기서 컨테이너는 객체가 어떤 타입이든 자유롭게 사용할 수 있다는 것이다. int나 string 같은 일반적인 타입이 아니라 임의로 만든 클래스의 객체들이여도 라이브러리의 기능들을 모두 활용할 수 있다.
2. 벡터(Vector)
그 컨테이너 중에서도 오늘은 벡터(Vector)에 대해서 알아본다. 먼저, 벡터는 배열 처럼 객체들을 순차적으로 보관하는시퀀스 컨테이너(Sequence Container)의 한 종류이다. 다른 예로는 list, deque가 있다.
벡터는 가변길이 배열로 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다.
사용법은 다음과 같다. 먼저, vector 라이브러리를 include 시켜줘야 한다. 그리고, vector<타입> 변수 명; 과 같이 선언해준다. 임의의 원소에 접근하는 것은 배열처럼[]를 사용한다. 또한, 맨 뒤에 원소를 추가하거나 제거하기 위해서는 push_back 과pop_back함수를 사용하면 된다. 임의의 위치에 있는 원소에 접근은O(1)로 수행하고 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시O(1)에 수행한다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for(vector<int>::size_type i = 0; i < v.size(); i++) {
cout << "vector 의 " << i + 1 << " 번째 원소 : " << v[i] << endl;
}
return 0;
}
11번째 줄을 보면 size_type의 변수 i가 존재한다. 이는 벡터의 크기를 리턴하는 함수인 size가 리턴하는 값의 타입이 size_type 멤버 타입으로 정의되어있기 때문이다.
3. 벡터의 특성
맨 뒤에 원소를 추가하는 작업(push_back)은 정확히 시간복잡도로 따지면 분할상환의 뜻을 가진 amortized O(1)이라고 한다. 보통 벡터의 경우 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당해 놓고 있기 때문이다. 예를 들어, 위의 예에서 원소의 개수가 3개지만 벡터는 이미 10가 정도 저장할 수 있는 공간을 미리 할당해 놓는 다는 것이다. 따라서, 새로운 원소를 추가해도 그냥 이미 할당된 공간에 그 원소를 쓰기만 하면 된다.
따라서 대부분의 경우에 원소의 추가, 삭제는 O(1)으로 이루어진다. 하지만, 할당된 공간을 다 채웠을 때는 얘기가 달라진다. 이 때는 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사하는 수 밖에 없다.
이 경우 nn 개의 원소를 모두 복사해야 하기 때문에 O(n)의 시간복잡도가 발생한다. 하지만 O(n)으로 수행되는 경우가 매우 적기 때문에, 전체적으로 평균을 내보았을 때 O(1)로 수행이 된다. 그림으로 설명하면 다음과 같다.
또한, 맨 뒤에 원소를 추가하거나 제거하는 것(O(1))은 빠르지만, 임의의 위치에 원소를 추가하거나 제거하는 것은 O(N)으로 느리다. 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 줘야하기 때문이다. 따라서 이는 N번의 복사가 필요하다.
따라서, 어떠한 작업을 하냐에 따라서 속도차가 매우 크기 때문에 C++ 표준 라이브러리를 잘 사용하기 위해서는 내가 이 컨테이너를 어떠한 작업을 위해 사용하는지 정확히 인지해 적절한 컨테이너를 골라야 한다.
4. 순회(for)로 원소 접근하기
컨테이너를 순회(for)문으로 접근하는 경우가 많은데 이는 포인터와 같은 객체인 반복자(Iterator)를 사용하는 경우도 있고 C++ 11버전 부터는 범위 기반 for문을 제공한다. 순회문에 들어갈 매개변수는 컨테이너의 원소를 받을 변수와 컨테이너를 정의해주면 된다. 이것은 e 변수에 v[i]를 한 것과 같다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for(int e : v) {
cout << "원소 : " << e << endl;
}
return 0;
}
5. 벡터의 생성자
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 빈 벡터 생성
vector<int> v;
2. 0으로 초기화 된 10개의 원소를 가지는 벡터 생성
vector<int> v(10);
3. 5로 초기화 된 10개의 원소를 가지는 벡터 생성
vector<int> v(10, 5);
4. v1 벡터를 복사해서 벡터 생성
vector<int> v(v1);
}
6. 벡터의 멤버변수
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
vector<int> v1;
1. v.front(); ==> 벡터의 첫 번째 원소를 참조한다.
2. v.end(); ==> 벡터의 마지막 원소를 참조한다.
3. v.push_back(2); ==> 벡터의 마지막 원소 뒤에 2를 추가한다.
4. v.pop_back(); ==> 벡터의 마지막 원소를 삭제한다.
5. v.size(); ==> 벡터의 원소의 개수를 리턴한다.
6. v.capacity(); ==> 벡터의 할당된 메모리의 크기를 리턴한다.
7. v.insert(2, 3); ==> 벡터의 2번째 위치에 3을 삽입하고 삽입한 곳의 iterator를 반환한다.
8. v.insert(2, 3, 4); ==> 벡터의 2번째 위치에 3개의 4를 삽입하고 삽입한 곳의 iterator를 반환한다.
9. v.swap(v1); ==> v 벡터와 v1 벡터의 요소와 capacity를 모두 바꿔준다.
}
7. 벡터 여러개 생성하기
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 벡터를 N개 생성
vector<int> v[3]; // v라는 벡터를 3개 생성
[비교] 벡터를 하나만 생성
vector<int> v1(3); // size가 3인 벡터를 1개 생성
2. 벡터 원소 넣기
v[0].push_back(1);
v[0].push_back(2);
v[1].push_back(1);
v[2].push_back(1);
v[2].push_back(2);
v[2].push_back(3);
3. 원소 접근
cout << v[0][2] << endl;
cout << v[1][1] << endl;
8. 벡터 Pair
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 동시에 Int 값을 넣을 수 있는 Pair 벡터 선언
vector<pair<int, int> > v[3]; // [주의] <pair<int, int> > 이 부분에서 끝에 띄어써야 함
2. 벡터 원소 넣기
v[0].push_back({3, 5});
v[0].push_back({2, 7});
v[1].push_back({1, 3});
v[1].push_back({5, 6});
v[2].push_back({2, 7});
3. 원소 접근
cout << v[1][1].first << " " << v[1][1].second << endl;
cout << v[0][0].first << " " << v[0][0].second << endl;
처음에는 이중 순회(for)를 돌아서 코드를 짰다. 하지만 입력값이 10만 이하인 것을 보고 안될것이라고 예상은 했다. 돌려봤지만 역시나 Time Limit이였고 이중 순회를(for) O(루트 N)이나 O(N)으로 접근하는 다른 방법이 필요했다. 곰곰히 생각해보았지만 답이 떠오르지 않아서 강의 초반부를 들었다. 강의를 들었을 때 머리를 뒤통수로 한대 맞은 듯한 느낌이 들었다.
원리의 핵심은 다음과 같다. 초기값으로 연속적인 며칠에 해당하는 K동안의 합을 구한다. 그리고 그 초기값을 바탕으로 K번째부터 순회(for)를 돌아 K번째에 해당하는 값은 더하고 그 인덱스(처음은 K)에 K값을 뺀 인덱스의 값을 빼준다는 것이다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, k, i, temp = 0, max = 0;
scanf("%d %d", &n, &k);
int *arr = (int *)malloc(sizeof(int) * n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
for(i=0; i<k; i++){
temp += arr[i];
max = temp;
}
for(i=k; i<n; i++){
temp = temp + arr[i] - arr[i-k];
if(temp > max) max = temp;
}
printf("%d", max);
free(arr);
return 0;
}
결과는 통과하였다.
사이트의 답안
#include<stdio.h>
#include<vector>
using namespace std;
int main(){
freopen("input.txt", "rt", stdin);
int n, k, i, sum=0, res;
scanf("%d %d", &n, &k);
vector<int> a(n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=0; i<k; i++){
sum=sum+a[i];
}
res=sum;
for(i=k; i<n; i++){
sum=sum+(a[i]-a[i-k]);
if(sum>res) res=sum;
}
printf("%d\n", res);
return 0;
}
