취미로 코딩하기

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

이번에 볼 문제는 백준 11505번 분제인 구간 곱 구하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11505

이 문제는 구간 합을 구하는 세그먼트 트리(segment tree)랑 마찬가지로 구현을 하면 되나, 값을 갱신할 때 나머지 연산과 곱셈 연산은 순서를 자유롭게 바꿀 수 없으므로 이 점에 유의하여 구현해야 한다.

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

#include <iostream>
using std::cin; using std::cout;
typedef long long ll;

ll arr[1000001];
ll segtree[2097153];

ll initseg(int L, int R, int sIdx) {
    if (L == R) segtree[sIdx] = arr[L];
    else segtree[sIdx] = initseg(L, (L + R) / 2, sIdx * 2) * initseg((L + R) / 2 + 1, R, sIdx * 2 + 1) % 1000000007;
    return segtree[sIdx];
}

ll update(int L, int R, int qIdx, int sIdx, ll val) {
    if (L == R && L == qIdx) segtree[sIdx] = val;
    else if (L<=qIdx && qIdx <= R) segtree[sIdx] = update(L, (L + R) / 2, qIdx, sIdx * 2, val) * update((L+R)/2+1,R,qIdx,sIdx*2+1,val) % 1000000007;
    return segtree[sIdx];
}

ll rmultq(int L, int R, int qL, int qR, int sIdx) {
    if (qL <= L && R <= qR) return segtree[sIdx];
    if (R < qL || qR < L) return 1;
    else return rmultq(L, (L + R) / 2, qL, qR, sIdx * 2) * rmultq((L + R) / 2 + 1, R, qL, qR, sIdx * 2 + 1) % 1000000007;
}

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

    int N, M, K; cin >> N >> M >> K;
    for (int i = 1;i <= N;i++) {
        ll x; cin >> x;
        arr[i] = x;
    }
    initseg(1, N, 1);
    for (int i = 0;i < M + K;i++) {
        ll q, a, b; cin >> q >> a >> b;
        if (q == 1) {
            update(1, N, a, 1, b);
        }
        else cout << rmultq(1, N, a, b, 1) << '\n';
    }
    return 0;
}

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

이번에 볼 문제는 백준 12016번 문제인 라운드 로빈 스케줄러이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12016

라운드 로빈 스케줄링(round-robin scheduling)에 대해서는 다음 링크를 참고하자:

en.wikipedia.org/wiki/Round-robin_scheduling

라운드 로빈 스케줄링은 위의 링크와 같이 작동하지만, 이 문제에서 위 라운드 로빈 알고리즘과 동일하게 진행하면서 값을 찾는 것은 매우 비효율적이다. 따라서 이 문제를 풀기 위해서는 다른 방법이 필요하다.

글쓴이는 이 문제를 풀기 위해 n개의 원소의 구간 최솟값을 반환할 수 있는 세그먼트 트리(segment tree)를 구현하고, 최솟값을 하나 읽을 때마다 입력으로 주어질 수 없는 큰 수(1000000001)로 해당 최솟값을 갱신하는 방법을 선택했다. 또한, 그때그때 범위에 남아있는 수를 알아야 출력할 값을 계산해낼 수 있으므로, n개의 리프 노드의 값이 1이고 구간 합을 반환하는 세그먼트 트리를 같이 구현하였다.

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

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::min;
typedef long long ll;

ll arr[100001];
int segtree[262145]; // 전체의 최솟값을 얻을 segtree
int cnttree[262145]; // 구간의 남은 원소개수를 셀 cnttree
int minindex;

int initsegtree(int L, int R, int sIdx) { // segtree의 초기화
	if (L == R) segtree[sIdx] = arr[L];
	else segtree[sIdx] = min(initsegtree(L, (L + R) / 2, sIdx * 2), initsegtree((L + R) / 2 + 1, R, sIdx * 2 + 1));
	return segtree[sIdx];
}

int segupdate(int L, int R, int sIdx, int minvalue) {
	if (L == R) {
		segtree[sIdx] = 1000000001;
		minindex = L; //업데이트하며 계산에 필요한 minindex값을 저장
	}
	else if (segtree[sIdx * 2] == minvalue) {
		segtree[sIdx] = min(segupdate(L, (L + R) / 2, sIdx * 2, minvalue), segtree[sIdx * 2 + 1]);
	}
	else segtree[sIdx] = min(segtree[sIdx * 2], segupdate((L + R) / 2 + 1, R, sIdx * 2 + 1, minvalue));
	return segtree[sIdx];
}

int initcnttree(int L, int R, int sIdx) { // cnttree의 초기화
	if (L == R) cnttree[sIdx] = 1;
	else cnttree[sIdx] = initcnttree(L, (L + R) / 2, sIdx * 2) + initcnttree((L + R) / 2 + 1, R, sIdx * 2 + 1);
	return cnttree[sIdx];
}

ll cntrq(int L, int R, int qL, int qR, int sIdx) { // L부터 R까지 현재 남아있는 숫자의 개수를 반환하는 쿼리
	if (qL <= L && R <= qR) return cnttree[sIdx];
	if (qR < L || R < qL) return 0;
	return cntrq(L, (L + R) / 2, qL, qR, sIdx * 2) + cntrq((L + R) / 2 + 1, R, qL, qR, sIdx * 2 + 1);
}

void cntupdate(int L, int R, int qIdx, int sIdx) { // 개수 업데이트: 1개 있던 것이 0개가 되는 것이므로 1씩 빼주는 것으로 충분
	if (R < qIdx || qIdx < L) return;
	cnttree[sIdx]--;
	if (L != R) {
		cntupdate(L, (L + R) / 2, qIdx, sIdx * 2);
		cntupdate((L + R) / 2 + 1, R, qIdx, sIdx * 2 + 1);
	}
}

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

	int N; cin >> N;
	for (int i = 1;i <= N;i++) {
		int x; cin >> x; arr[i] = x;
	}
	initsegtree(1, N, 1); initcnttree(1, N, 1); //초기화
	ll ans = 0;
	ll oldindex = 0;
	ll oldminvalue = 1;
	for (int i = N;i > 0;i--) {
		ll minvalue = segtree[1];
		segupdate(1, N, 1, minvalue);
		if (oldindex < minindex) {
			ans += cntrq(1, N, oldindex + 1, minindex, 1) + (minvalue - oldminvalue) * i;
		}
		else ans += cntrq(1, N, oldindex + 1, N, 1) + cntrq(1, N, 1, minindex, 1) + (minvalue-oldminvalue-1)*i;
		arr[minindex] = ans;
		cntupdate(1, N, minindex, 1);
		oldindex = minindex;
		oldminvalue = minvalue;
	}
	for (int i = 1;i <= N;i++) cout << arr[i] << '\n';
	return 0;
}

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

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

www.acmicpc.net/problem/2357

이 문제 또한 세그먼트 트리(segment tree)의 구현을 연습하기 위해 풀어본 문제이다.

단, 이 문제에서는 중간에 값을 갱신할 필요는 없기 때문에 조금 더 입문하기에 좋은 문제이지 않았나 싶다.

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

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::min; using std::max;

int arr[100001];
int minsegtree[400001];
int maxsegtree[400001];

int minseg(int L, int R, int segIndex) {
    if (L == R) minsegtree[segIndex] = arr[L];
    else minsegtree[segIndex] = min(minseg(L,(L+R)/2,segIndex*2),minseg((L+R)/2+1,R,segIndex*2+1));
    return minsegtree[segIndex];
}

int minquery(int L, int R, int queryL, int queryR, int segIndex) {
    if (queryL <= L && R <= queryR) return minsegtree[segIndex];
    if (R < queryL || queryR < L) return 1000000001;
    return min(minquery(L, (L + R) / 2, queryL, queryR, segIndex * 2), minquery((L + R) / 2 + 1, R, queryL, queryR, segIndex * 2 + 1));
}

int maxquery(int L, int R, int queryL, int queryR, int segIndex) {
    if (queryL <= L && R <= queryR) return maxsegtree[segIndex];
    if (R < queryL || queryR < L) return -1;
    return max(maxquery(L, (L + R) / 2, queryL, queryR, segIndex * 2), maxquery((L + R) / 2 + 1, R, queryL, queryR, segIndex * 2 + 1));
}

int maxseg(int L, int R, int segIndex) {
    if (L == R) maxsegtree[segIndex] = arr[L];
    else maxsegtree[segIndex] = max(maxseg(L, (L + R) / 2, segIndex * 2), maxseg((L + R) / 2 + 1, R, segIndex * 2 + 1));
    return maxsegtree[segIndex];
}

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

    int N, M; cin >> N >> M;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x;arr[i] = x;
    }
    minseg(1, N, 1);
    maxseg(1, N, 1);
    for (int i = 0;i < M;i++) {
        int a, b; cin >> a >> b;
        cout << minquery(1, N, a, b, 1) << ' ' << maxquery(1, N, a, b, 1) << '\n';
    }
    return 0;
}

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

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

www.acmicpc.net/problem/2042

이 문제는 세그먼트 트리(segment tree) 자료구조를 익히는 기본 문제이다.

세그먼트 트리를 익히기 위해 이 문제를 풀어보았다.

여러 책과 사이트를 참고하여 코드가 부산하지만, 처음으로 세그먼트 트리를 구현해보았다는 데에 의의를 두기로 했다.

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

#include <iostream>
using std::cin; using std::cout;
typedef long long ll;

ll arr[1000001];
ll segtree[4000001];
int N, M, K;

ll seg(int L, int R, int index) { // segment tree 만들기
    if (L == R) segtree[index] = arr[L];
    else segtree[index] = seg(L, (L + R) / 2, index * 2) + seg((L + R) / 2 + 1, R, index * 2 + 1);
    return segtree[index];
}

ll query1(int L, int R, int queryL, int queryR, int index) { // 구간 합 쿼리
    if (queryL <= L && R <= queryR) return segtree[index];
    else if (R < queryL || queryR < L) return 0;
    else  return query1(L, (L + R) / 2, queryL, queryR, index * 2) + query1((L + R) / 2 + 1, R, queryL, queryR, index * 2 + 1);
}

void query2(int L, int R, int qI, int segI, ll diff) { // 값 변경 쿼리
    if (qI < L || R < qI) return;
    segtree[segI] += diff;
    if (L == R) return;
    query2(L, (L + R) / 2, qI, segI * 2, diff);
    query2((L + R) / 2 + 1, R, qI, segI * 2 + 1, diff);
}

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

    cin >> N >> M >> K;
    for (int i = 1;i <= N;i++) {
        ll x; cin >> x; arr[i] = x;
    }
    seg(1, N, 1);
    for (int i = 0;i < M + K;i++) {
        ll a, b, c; cin >> a >> b >> c;
        if (a == 1) {
            query2(1, N, b, 1, c - arr[b]);
            arr[b] = c;
        }
        else cout << query1(1, N, b, c, 1) << '\n';
    }
    return 0;
}

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

이번에 볼 문제는 백준 15684번 문제인 사다리 조작이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15684

처음 이 문제를 읽을 때, "만약, 정답이 3보다 큰 값이면 -1을 출력한다." 부분을 놓쳐 어떻게 풀어야 좋을지 많은 고민을 했던 기억이 있다. 하지만 이 문제에서는 선을 3개까지만 그어보면 되므로, 모든 경우의 수를 전부 수행해보아도 제한시간 내에 문제를 해결할 수 있다.

사다리의 가로 선을 배열에 입력받을 때, 오른쪽 방향으로 이동해야 하는 막대기에는 1을, 왼쪽 방향으로 이동해야하는 막대기에는 -1을 집어넣고, 그 외에는 초기값으로 0을 주어 사다리가 문제에 조건에 맞는지 확인하기 위해 확인할 때 각 높이에 적혀있는 숫자를 더하는 식으로 사다리타기를 구현할 수 있다.

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

#include <iostream>
using std::cin; using std::cout;

int ladder[11][31]; // ladder[N번줄][i번행에서 +1이면 i+1번줄로 이동, -1이면 i-1번줄로 이동]

int N, M, H;

bool game() {
    for (int i = 1;i < N;i++) {
        int x = i;
        int h = 1;
        while (h <= H) {
            x += ladder[x][h];
            h++;
        }
        if (x != i) return 0;
    }
    return 1;
}

bool ladder1() {
    for (int i = 1;i < N;i++) {
        for (int h = 1;h <= H;h++) {
            if (ladder[i][h] == 0 and ladder[i + 1][h] == 0) { // 선을 그을 수 있는 곳이면
                ladder[i][h] = 1; ladder[i + 1][h] = -1;
                if (game()) return 1;
                ladder[i][h] = 0; ladder[i + 1][h] = 0;
            }
        }
    }
    return 0;
}

int cnt = 0;

bool ladder2(int i) {
    if (cnt == 2) {
        if (game()) return 1;
        else return 0;
    }
    for (;i < N;i++) {
        for (int h = 1;h <= H;h++) {
            if (ladder[i][h] == 0 and ladder[i + 1][h] == 0) { // 선을 그을 수 있는 곳이면
                ladder[i][h] = 1; ladder[i + 1][h] = -1;
                cnt++;
                if (ladder2(i)) return 1;
                cnt--;
                ladder[i][h] = 0; ladder[i + 1][h] = 0;
            }
        }
    }
    
    return 0;
}

bool ladder3(int i) {
    if (cnt == 3) {
        if (game()) return 1;
        else return 0;
    }
    for (;i < N;i++) {
        for (int h = 1;h <= H;h++) {
            if (ladder[i][h] == 0 and ladder[i + 1][h] == 0) { // 선을 그을 수 있는 곳이면
                ladder[i][h] = 1; ladder[i + 1][h] = -1;
                cnt++;
                if (ladder3(i)) return 1;
                cnt--;
                ladder[i][h] = 0; ladder[i + 1][h] = 0;
            }
        }
    }

    return 0;
}

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

    cin >> N >> M >> H;
    for (int i = 0;i < M;i++) {
        int a, b; cin >> a >> b;
        ladder[b][a] = 1;
        ladder[b+1][a] = -1;
    }
    if (game()) cout << 0;
    else {
        cnt = 0;
        if (ladder1()) cout << 1;
        else {
            cnt = 0;
            if (ladder2(1)) cout << 2;
            else {
                cnt = 0;
                if (ladder3(1)) cout << 3;
                else cout << -1;
            }
        }
    }

    return 0;
}

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

이번에 볼 문제는 백준 4485번 문제인 녹색 옷 입은 애가 젤다지?이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/4485

이 문제에서는 주어진 2차원 배열에서 지나가는 칸의 수의 합이 최소가 되는 경로를 찾는 문제이다.

이 문제는 2차원 배열 모양의 그래프에서 최단거리가 되는 경로를 찾는 문제로 볼 수 있으므로, dijkstra 알고리즘을 사용하면 간단히 문제를 풀 수 있다.

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

#include <iostream>
#include <queue>
#include <vector>
using std::cin; using std::cout;
using std::pair;
using std::priority_queue;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int num = 0;

void solve(int N) {
    int cave[125][125];
    bool visited[125][125];
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            int temp; cin >> temp;
            cave[i][j] = temp;
            visited[i][j] = false;
        }
    }
    priority_queue<pair<int, pair<int,int>>> pq; // {dist,{row,column}}
    pair<int, int> pair00 = { 0,0 };
    pair<int, int> pairnn = { N - 1,N - 1 };
    pq.push({ -cave[0][0],pair00 });
    pair<int, int> current = { 0,0 };
    while (!pq.empty()) {
        current = pq.top().second;
        int dist = -pq.top().first; pq.pop();
        if (visited[current.first][current.second]) continue;
        if (current.first == N - 1 and current.second == N - 1) {
            cout << "Problem " << num << ": " << dist << '\n';
            break;
        }
        visited[current.first][current.second] = 1;
        for (int i = 0;i < 4;i++) {
            int rr = current.first + dr[i];
            int cc = current.second + dc[i];
            if (0 <= rr && rr < N && 0 <= cc && cc < N) {
                if (!visited[rr][cc]) {
                    pq.push({ -dist - cave[rr][cc],{rr,cc} });
                }
            }
        }
    }
}

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

    int N; cin >> N;
    while (N != 0) {
        num++;
        solve(N);
        cin >> N;
    }
    return 0;
}