취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1275번 문제인 커피숍2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1275

이 문제에서는 배열이 주어지고, 배열의 구간합을 구한 뒤 수 하나를 다른 수로 바꾸는 쿼리가 반복하여 주어진다.

숫자가 계속 바뀔 수 있으므로, 세그먼트트리를 이용하여 이 문제를 푸는 것이 좋다.

숫자를 다른 수로 변경할 때, 원래 배열에 있던 수와 새로 바꾸려는 수의 차이만큼 업데이트를 해주면 된다는 점을 잊지 말자. 또한, 이 과정에서 원래 배열의 값도 갱신해주는 것을 잊지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
typedef long long ll;

using namespace std;

ll arr[100001];
ll seg[262145];

ll init(int L, int R, int sI) {
	if (L == R) return seg[sI] = arr[L];
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void update(int L, int R, int qI, ll qVal) {
	int sI = 1;
	while (L != R) {
		seg[sI] += qVal;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid;
			sI = sI * 2;
		}
		else {
			L = mid + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[sI] += qVal;
}

ll query(int L, int R, int qL, int qR, int sI) {
	if (qR < L || R < qL) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, Q; cin >> N >> Q;
	
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	init(1, N, 1);

	for (int q = 0; q < Q; q++) {
		int x, y, a; ll b; cin >> x >> y >> a >> b;
		if (x > y) swap(x, y);
		cout << query(1, N, x, y, 1) << '\n';
		update(1, N, a, b - arr[a]);
		arr[a] = b;
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21237번 문제인 Clockwise Fence이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/21237

이 문제에서는 x, y축에 수직이거나 수평한 길이 1인 변으로 이루어진 도형의 꼭짓점이 시계방향순으로 주어지는지 반시계방향순으로 주어지는지 출력하는 문제이다.

주어지는 다각형이 볼록다각형이라면 그냥 다각형을 구성하는 (한 직선 위에 있지 않은) 세 점을 골라 CCW 여부를 확인하면 되겠지만, 이 문제에서는 볼록다각형이라는 조건이 없으므로 CCW 계산만으로는 문제를 해결할 수 없다.

대신, 다각형의 넓이를 계산하는 사선공식(Shoelace Formula)을 이용하여 주어진 꼭짓점이 시계방향 순으로 주어졌는지 반시계방향 순으로 주어졌는지를 알아낼 수 있다.

사선공식의 계산 결과값이 양수일 경우 꼭짓점은 반시계방향 순으로 주어진 것이고, 음수일 경우 꼭짓점은 시계방향순으로 주어진 것이라고 판단할 수 있기 때문이다. 넓이가 0이 나오는 경우는 이 문제에서는 존재하지 않으므로 신경쓰지 않는다.

사선공식에 대하여 잘 모른다면 다음 링크를 참고하자.

en.wikipedia.org/wiki/Shoelace_formula

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int x[101];
int y[101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int ans = 0;
        int xx = 0, yy = 0;
        int slen = (int)s.length();
        for (int i = 0;i < slen;i++) {
            if (s[i] == 'N') yy++;
            else if (s[i] == 'S') yy--;
            else if (s[i] == 'W') xx--;
            else xx++; // else if (s[i] == 'E')
            x[i] = xx;
            y[i] = yy;
        }
        for (int i = 0;i < slen;i++) {
            ans += x[i] * y[i + 1] - x[i + 1] * y[i];
        }
        if (ans > 0) cout << "CCW\n";
        else cout << "CW\n";
    }
}

ps. 위 코드에서, Fence를 설치하기 시작한 좌표는 (0,0)이라고 가정하였다.

시작 좌표가 (0,0)이므로 맨 처음 좌표가 포함된 성분의 값은 0이 된다. 또한, 주어진 대로 펜스를 설치하면 맨 마지막에 다시 시작한 좌표인 (0,0)을 입력하게 되어, 이전에 입력된 값들의 영향을 받지 않고 ans에 0을 더하면서 식 계산을 마칠 수 있다. 따라서 위 코드는 올바른 결과값을 출력한다.

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11000번 문제인 강의실 배정이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11000

문제에서 주어진 조건을 잘 살펴보자.

모든 수업은 시작하는 시간이 끝나는 시간보다 앞서는 것을 알 수 있다.

현재 시간에 진행되는 수업의 수를 cnt라 하자. cnt의 초기값은 0이다.

관찰을 통해, 모든 수업시간의 시작시간과 끝 시간들을 정렬한 다음, 어떤 하나의 수업시작 시간을 만나면 현재 시점에서 cnt가 1 늘어나고, 수업 끝 시간을 만나면 현재 시점에서 cnt가 1 줄어든다는 것을 알 수 있다.

가장 많은 강의실을 필요로 하는 순간은 cnt가 최대인 순간이 될 것이라는 것을 알 수 있다.

cnt를 계산하는 과정에서 주의해야하는 점이 하나 있다. 바로 어떤 한 시간에 여러 수업이 동시에 시작하고 끝나는 경우이다. 이 경우, 끝나는 수업을 먼저 처리하고 나중에 시작하는 수업을 처리해야한다. 시작하는 수업과 끝나는 수업이 동시에 있을 때 시작하는 수업을 먼저 계산하고 현재 진행중인 수업의 수를 세면 실제보다 현재 진행되는 수업의 수보다 많은 수업의 수를 순간 cnt가 갖고 있게 되기 때문이다.

이를 쉽게 해결하기 위해, 글쓴이는 수업의 시작시간과 끝시간을 각 배열로 만들어 두 배열의 index를 관리하여 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>

using namespace std;
int S[200000];
int E[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i] >> E[i];
	}

	sort(S, S + N);
	sort(E, E + N);

	int mx = 0;
	int cnt = 0;
	int sidx = 0;
	int eidx = 0;

	while (sidx < N) {
		if (S[sidx] < E[eidx]) {
			cnt++;
			sidx++;
			if (mx < cnt) mx = cnt;
		}
		else {
			cnt--;
			eidx++;
		}
	}

	cout << mx;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10999번 문제인 구간 합 구하기 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10999

이 문제는 구간 갱신 쿼리가 포함되어 있다.

만약 구간 갱신 쿼리를 구간의 각 점에 대하여 한번씩 실행한다면 그 속도는 매우 느려질 수밖에 없다.

이럴 때에는, 모든 구간에 갱신 명령을 일단 하되, 갱신된 값에 접근이 필요할 때마다 해당 갱신을 실행하는, 지연 전파(lazy propagation)를 이용하여 문제를 해결할 수 있다.

이 문제에서 몇몇 구간합은 64비트 정수가 표현할 수 있는 범위를 넘어갈 수 있다.

그러나 오버플로우가 일어났을 때의 덧셈은 기대하는 대로 잘 정의가 되어있고, 이 문제의 쿼리는 정답이 64비트 정수가 표현할 수 있는 범위 내인 구간에서만 질의하므로 걱정할 필요 없이 평소처럼 구현하면 된다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

using namespace std;

ll arr[1000001];
ll seg[2097153];
ll lazy[2097153];

ll init(int L, int R, int sI) {
	if (L == R) return seg[sI] = arr[L];
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void propagate(int L, int R, int sI) {
	seg[sI] += lazy[sI] * (ll)(R - L + 1);
	if (L != R) {
		lazy[sI * 2] += lazy[sI];
		lazy[sI * 2 + 1] += lazy[sI];
	}
	lazy[sI] = 0;
}

ll update(int L, int R, int qL, int qR, ll qVal, int sI) {
	if (lazy[sI]!=0) propagate(L, R, sI);
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] += qVal;
		propagate(L, R, sI);
		return seg[sI];
	}
	return seg[sI] = update(L, (L + R) / 2, qL, qR, qVal, sI * 2) + update((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
}
ll query(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]!=0) propagate(L, R, sI);
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, K; cin >> N >> M >> K;
	M += K;

	for (int i = 1; i <= N; i++) cin >> arr[i];
	
	init(1, N, 1);

	for (int m = 0; m < M; m++) {
		int a; cin >> a;
		if (a == 1) {
			int x, y; ll z; cin >> x >> y >> z;
			update(1, N, x, y, z, 1);
		}
		else {
			int x, y; cin >> x >> y;
			cout << query(1, N, x, y, 1) << '\n';
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10868번 문제인 최솟값이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10868

이 문제는 RMQ(Range Minimum Query)를 구현해보는 문제이다.

범용성이 높은 Segment Tree로 RMQ를 다음과 같이 구현해보았다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[100001];
int seg[262145];

int init(int L, int R, int sI) {
    if (L == R) return seg[sI] = arr[L];
    return seg[sI] = min(init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1));
}

int query(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 1000000007;
    if (qL <= L && R <= qR) return seg[sI];
    return min(query(L, (L + R) / 2, qL, qR, sI * 2), query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    
    for (int i = 1; i <= N; i++) cin >> arr[i];
    
    init(1, N, 1);

    for (int T = 0; T < M; T++) {
        int x, y; cin >> x >> y;
        cout << query(1, N, x, y, 1) << '\n';
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2739번 문제인 구구단이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2739 

반복문 연습문제의 대표주자인 구구단 출력 문제이다.

n을 입력받으면, n * i = (n*i)\n 의 형식을 i를 1부터 9까지 반복하여 출력하면 된다.

"*"와 "="의 앞뒤로 공백이 들어있다는 점에 주의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	int N; cin >> N;
	for (int i = 1; i < 10; i++) {
		cout << N << " * " << i << " = " << N * i << '\n';
	}
}