Hoeun Wang - Blog

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

Goricon에서 다른 문제들도 있었지만, 이 문제 유형은 알아두고 방법을 익히면 다른 같은 유형의 문제들도 쉽게 해결 할 수 있을거라는 판단이 들어 이 문제에 대한 풀이를 적어보고 완벽히 익혀보고자 한다.

문제 해석

어떤 한 수열을 입력받은 후, 1번을 입력받았을 땐 한 수에 x 만큼 값을 추가, 2번을 입력받았을땐 오른쪽으로 이동, 3번은 왼쪽으로 이동하여 최종적으로 변화된 수열을 출력하는 문제이다. 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include <tuple>
#include <string>
using namespace std;
long long a[200000];
int N, Q;
int x;
int start_point = 0;
int k, add_item;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> x;
		if (x == 1) {
			cin >> k >> add_item;
			k -= 1;
			a[(start_point + k) % N] += add_item;
		}
		else if (x == 2) {
			cin >> k;
			start_point = (start_point + N - k) % N;
		}
		else if (x == 3) {
			cin >> k;
			start_point = (start_point + k) % N;
		}
	}

	for (int i = 0; i < N; i++) {
		cout << a[(start_point + i) % N] << ' ';
	}




	return 0;
}

문제풀이

위 문제에서 중요한 부분은 바로

start_point = (start_point + N - k) % N;

이 문장과,

start_point = (start_point + k) % N;

이 문장이다.

나는 이 문제에서 1번을 입력받았을때 해당 숫자를 x 만큼 늘리는 과정은 어렵지 않다고 생각했다. 입력 받은 수 + x 를 해주고 다시 그 입력받은 수에 넣어주면 되기 때문이다.
하지만, 중요하다고 본게 2번 3번이다. 

나는 일단 전체적으로 수열이 이동하는 것이기때문에, start_point를 잡아주는것이 중요하다고 보았고, 배열의 start_point를 0으로 잡고, 계산했다.
먼저 오른쪽으로 이동하는 2번 같은 경우는 첫번째 코드와 같이 작성해보았는데, star_point에서 배열의 길이인 N만큼 더해주고, 입력받은 얼만큼 이동할 것인가?에 대한 k를 빼줬다.(늘어난 길이에서 k를 더해주는것이 아닌 빼주는것은 N만큼 더해줬으니 반대로 생각해주면 된다.) 그 후 N으로 나머지연산을 해주면 원래 배열의 길이로 돌아와 k만큼 이동한 배열을 얻을 수 있다.

다음으로 3번같은경우는 start_point에서 k만큼 더해준 후, (2번의 경우와 반대 ! N을 더해주지 않았으니.) 배열의 길이인 N으로 나머지 연산을 해주면 왼쪽으로 이동한 수열을 도출 해 낼 수 있다.

이 문제를 위 식을 생각하지 않고 배열안에 모든 수를 일일이 옮기려 하면, 시간과 코드가 길어지게 된다.
앞으로 위와 같은 문제 유형을 맞닥트렸을 때 위 식을 잘 생각해 내어 빠른 시간안에 문제를 해결해야겠다고 생각했다.

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

문제해석

단순하게 문제 속 수학식을 살펴보고 입력받은 값으로 계산하여 출력하여 주면 되는 문제이다.
알고리즘 기술과 관련된 지식이 필요하다기 보다는 정말 수학문제를 풀줄 알면 사람이면 누구나 이 문제를 해결할 수 있다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include <tuple>
#include <string>
#include <queue>
using namespace std;
int eh, el;
int a, b;
int x0;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> eh >> el;
	cin >> a >> b;
	cin >> x0;
	cout << a * x0 + b <<'\n';
	int hh = eh, ll = el * a;
	if (!hh || !ll) {
		cout << "0 0" << '\n';
	}
	cout << abs(hh) <<' ' << abs(ll) << '\n';
    
    return 0;
}

문제풀이

먼저 극한값을 구하는건 간단하게 해결할 수 있다. x가 x0에 가까워질때의 극한값이므로 a*x0+b를 해주면 쉽게 구할 수 있다.
그 후 델타값을 구하는건 수학적 지식이 필요한데, 델타는 입실론을 a로 나눈 값이다. 따라서 분자인 hh는 그대로 유지해주고 분모인 ll는 a를 곱해줘야한다. (그래야지 a로 나누는게 됨.)
그런 후 c++ 절댓값 라이브러리 abs() 함수를 사용하여 출력만 해주면 문제를 해결 할 수 있다.
정말 수학 문제 그자체. 아무래도 신입생들을 위한 알고리즘 문제이다보니 이런 수학 유형을 많이 내지 않았을까 싶다.

이번 연습은 3명이서 9문제중 7문제를 풀었다. 마지막에 시간이 좀 더 있었으면 F번을 풀을 수 있었을 거 같은데 아쉬웠다. 나는 오히려 이런 수학공식을 해결하여 문제를 푸는게 좀 더 나한텐 익숙하다. 알고리즘 문제를 많이 풀었기 보단 수학 공부한 기억이 더 많이 남아서가 아닐까 생각한다. 다른 팀원들은 수학 문제에 오히려 약하다고 하니 내가 수학문제가 나오면 맞추려고 노력해야겠다.

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

문제해석

이 문제는 큐에 수를 추가하고 가장 작은 값부터 출력해주는 문제이다.

선입선출의 특징을 가진 큐를 생각해서 어떻게 문제를 해결해 나가야 할지 고민해봐야한다.

코드

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

int N;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;

		if (a == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(a);
		}
	}

	return 0;

}

문제풀이

이 문제는 물론 다른 방법이 존재하지만, c++로 문제를 푸는 사람들은 우선순위 큐 STL을 사용하면 좋은 문제이다.

우선순위 큐인 priority_queue는 일반적인 queue와는 다르게 선입 선출 형태가 아닌 지정된 값을 통해 queue 내부의 우선순위를 정리 할 수 있다. 

우선순위 큐는

priority_queue<자료형, 구현체, 비교연산자> pq;

다음과 같이 정의 된다.

나는 자료형엔 int 구현체에는 queue를 사용해주었는데 비교연산자에서 greater<int>를 작성해주었다. greater<자료형>은 기본 비교연산자이며 가장 작은 값부터 나열을 시켜준다.(큰값부터 나열은 less<자료형> 활용해주기.)

이 STL을 사용하여 코드를 작성하면 아주 간단하게 문제를 해결할 수있다. STL을 잘 이해하고 활용하는 방법도 많이 시도해보도록 하자.

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

문제해석

비디오의 개수와 블루레이의 개수를 입력 받은 후 비디오의 길이를 각각 입력받고, 블루레이에 비디오를 분배 하였을 때, 블루레이의 최솟값을 구하는 문제이다.

코드

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
int N, M;
int a[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int max, min = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		max += a[i];	
	}
	min = *max_element(a, a + N);	

	while (min <= max) {	
		int mid = (min + max) / 2;	

		int sum = 0, count = 0;	
		for (int i = 0; i < N; i++) {
			if (sum + a[i] > mid) {
				sum = 0;
				count++;
			}
			sum += a[i];
		}
		if (sum != 0) count++;	
		
        	
		if (count > M) {
			min = mid + 1;
		}
		else {
			max = mid - 1;
		}
	}
    
	cout << min;
	return 0;
}

문제풀이

먼저 입력 수의 범위를 살펴보았을 때 100000 이하로 나타나져 있기 때문에 이분탐색으로 풀어야 한다는 것을 미리 깨달아야 한다.

그렇게 판단 후 문제를 풀어보면, 비디오 개수 (N) 블루레이 개수 (M) 각각의 비디오 길이 배열a 를 입력 받고 가장 최대크기의 블루레이 크기가 될 수 있는 모든 비디오들의 길이를 합한 값을 max라는 변수에 저장해주고, 가장 작은 블루레이 크기가 될 수 있는 비디오 길이중 가장 긴 값을 min에 넣어준다.

그런 후, max값이 min값보다 같거나 클때 동안 다음 과정을 반복해주면 되는데, 임의로 우리가 지정한 mid라는 블루레이의 크기 값에 비디오들을 하나씩 넣어보며 만약 값이 더 크게 되면 필요한 블루레이 갯수를 한개 증가시켜준다. 그렇게 계속해서 비디오를 넣어보며 합을 구해주고 그 합을 활용해 큰지 적은지 판단하여 둔다. 모든 비디오를 다 넣어준 후에 count 한 블루에이 개수가 M보다 크면 기존 블루레이 개수를 늘려주고 적으면 줄여준다.

그렇게 한 후 최종 답이 들어있는 변수인 min을 출력해주면 해결할 수 있는 문제이다.