[2021.11.14] Problem solveing
http://koistudy.net/?mid=prob_page&NO=767
- 순위 구하기 (large)
- 문제 요약
n명의 순위를 구하려고 하는데, 만약 점수가 같다면 같은 등수로 처리한다.
- 해설
여러가지 방법(pair, struct, etc...)이 있을 수 있지만, 구조체를 vector에 넣어서 해결해 보았다. 구조체를 vector에 넣으면 어떻게 접근해야 하나 고민을 많이 했었다. 왜냐하면, 그냥 구조체의 인덱스에 배열처럼 접근하려 하면 전역으로 선언된 벡터에서 에러가 나기 때문이었다. 그래서 찾아본 결과 2가지 가능한 경우가 존재하는 것을 알게 되었다.
1. 구조체의 이름 설정
말 그대로 vector에 넣기 전에 구조체를 이름으로 선언해 저장해 놓은 뒤 넣는 방법이다.
구조체의 이름은 다음과 같이 선언할 수 있다.
struct point { // 구조체 선언
int x, y;
};
vector<point> a;
int main()
{
int n; cin >> n;
while(n--){
point t; // 구조체의 이름 설정
int k; cin >> k;
t.x = k; // 스캔한 데이터를 구조체 원소에 저장
t.y = 0;
a.push_back({t.x, t.y}); // vector에 구조체 원소 저장
}
}
2. vector를 배열처럼 사용
이 방법은 vector라는 가변길이 배열의 크기를 정해서 사용하는 방법이다.
vector 배열의 이름 옆에 소괄호를 치고, 배열의 크기를 설정해 줄 수 있다.
struct point {
int sco, x, y;
};
int main()
{
int n; cin >> n;
vector<point> a(n); // vector의 크기를 설정하여 선언
for(int i=0; i<n; i++) cin >> a[i].sco; // 구조체 배열처럼 사용
}
본론으로 돌아와서, 필요한 경우를 다 찾아보자.
일단 점수를 저장할 변수가 필요하다. 그런 다음에는 정렬을 한 후에 순위를 저장할 변수가 필요하고, 다시 원래대로 되돌릴 때 기준이 될 변수가 필요하다. 이 3가지 경우를 구조체로 묶고 경우에 따라 정렬해 주면 된다.
source code - 순위 구하기 (large)
#include <bits/stdc++.h>
using namespace std;
struct point {
int sco, x, y;
};
bool w(point p, point q) {
return p.sco > q.sco;
}
bool l(point p, point q) {
return p.y < q.y;
}
int main()
{
cin.tie(NULL); ios_base::sync_with_stdio(false);
int n; cin >> n;
vector<point> a(n);
for(int i=0; i<n; i++) {
cin >> a[i].sco;
a[i].y = i+1;
}
sort(a.begin(), a.end(), w);
/*
for(int i=0; i<n; i++) {
cout << a[i].sco << " ";
}*/
for(int i=0; i<n; i++) {
if(a[i].sco == a[i-1].sco) {
a[i].x = a[i-1].x;
} else {
a[i].x = i+1;
}
}
sort(a.begin(), a.end(), l);
for(int i=0; i<n; i++)
cout << a[i].x << "\n";
return 0;
}
http://koistudy.net/?mid=prob_page&NO=704
-- 학교가기1 (small)
- 문제 요약
0으로 표시된 곳은 공사 중이라 지나가지 못하고, 1로 표시된 곳으로만 갈 수 있다. (1, 1)에서 시작하여 (n, n)까지 갈 수 있는 총 경우의 수를 구해보자.
- 해설
정말 아주 단순하게 그래프 탐색을 통해 해결할 수 있다. small 이니까 굳이 양방향 탐색은 생각하지도 말고, 그냥 DFS 하면 된다.
(1, 1)에서 시작해서 쭉 파고 들어가기 시작하는데, 오른쪽과 아래로만 이동할 수 있다고 했으므로 두가지의 경우에만 탐색을 돌려준다. 만약 배열을 벗어나면 return; 해주고, 두 경우 다 0 이면 return; 해준다. 만약 (n, n)에 도달하였다면? 답에 체크해 준다.
source code - 학교가기1 (small)
#include <bits/stdc++.h>
using namespace std;
int n, d[20][20], cnt;
int dx[] = {1, 0};
int dy[] = {0, 1};
void f(int p, int q) {
if(p == n && q == n) cnt++;
if(p < 1 || q < 1 || p > n || q > n) return;
if(d[p][q] == 0) return;
for(int i=0; i<2; i++) {
f(p+dx[i], q+dy[i]);
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin >> d[i][j];
f(1, 1);
if(!cnt) {
cout << "-1\n";
} else {
cout << cnt << "\n";
}
return 0;
}
http://koistudy.net/?mid=prob_page&NO=1401
-- Range Minimum Query
세상에 날먹 트리는 없다!
- 문제 요약
구간에서 최솟값을 구하는 문제이다. 여기서 2가지 쿼리가 존재하게 된다.
첫번째 쿼리 : 주어진 구간에서 최솟값을 찾으시오.
두번째 쿼리 : a번째 값을 b로 바꾸시오. ( 처음에 트리에서 말하는 줄 알았는데, 보니까 입력되는 배열에서 ^^ )
- 해설
https://ialy1595.github.io/post/binary-indexed-tree/
트리에 관해서 설명해 놓은 엄청나게 좋은 블로그가 있다. ( 강추!! )
첫번째 쿼리면 최솟값을 출력하고, 두번째 쿼리이면 해당 인덱스를 교체해 주고 트리를 다시 만들면 된다.
솔직히 설명할 것은 딱히? 없다. 다만 갱신할 때 시간이 조금 걸려서 TLE가 뜬다.
source code - Range Minimum Query(TLE)
#include <bits/stdc++.h>
using namespace std;
int base, tr[1<<19];
int wldnjs(int l, int r) {
l += base-1;
r += base-1;
int res = INT_MAX;
while(l <= r){
if(l%2==1){
res = min(res, tr[l]);
l++;
}
if(r%2==0){
res = min(res, tr[r]);
r--;
}
r /= 2;
l /= 2;
}
return res;
}
int main()
{
int n, m; cin >> n >> m;
for(base = 1; base < n; base <<= 1);
for(int i = base; i < base+n; i++)
scanf("%d", tr + i);
for(int i=base-1; i>0; i--)
tr[i] = min(tr[i<<1], tr[(i<<1)+1]);
/*
for(int i=1; i<base+n; i++)
printf("%d ", tr[i]);*/
while(m--){
int k, l, r; cin >> k >> l >> r;
if(k == 1){
printf("%d\n", wldnjs(l, r));
} else {
l += base-1;
tr[l] = r;
for(int i=base-1; i>0; i--)
tr[i] = min(tr[i<<1], tr[(i<<1)+1]);
}
}
return 0;
}
빠른 갱신 트리가 존재하는지 알아 봐야 할 것 같다. 아니면 생각을 좀 더 하던지....