백준 BOJ 3184번 : 양
문제 난이도 : Silver I
알고리즘 분류 : DFS
'#'으로 분리된 우리 안에 양과 늑대가 있을 때, 양이 늑대보다 많다면 양은 늑대를 쫓아내고 그 외의 경우에는 늑대가 양을 잡아먹는다고 할 때 시간이 지난 뒤 총 양의 수와 늑대의 수를 구하는 문제이다.
DFS를 이용하여 각 우리 안에 있는 양과 늑대의 수를 구해주고, 문제에서 제시한 조건에 맞게 총 양의 수와 늑대의 수에 값을 더해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, c, d;
vector<vector<char>> v;
vector<vector<bool>> vis;
void f(int x, int y) {
vis[x][y] = true;
if(v[x][y] == 'o') c++;
else if(v[x][y] == 'v') d++;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int k=0; k<4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(vis[nx][ny] || v[nx][ny] == '#') continue;
f(nx, ny);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
v.resize(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vis.resize(N, vector<bool>(M));
int a = 0, b = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(vis[i][j] || v[i][j] == '#') continue;
c = 0, d = 0;
f(i, j);
if(c > d) d = 0;
else c = 0;
a += c;
b += d;
}
cout << a << " " << b << "\n";
}
여담으로 백준 BOJ 3187번 : '양치기 꿍' 문제와 동일하다.
v를 k로 바꿔주기만 하면 역시 정답 처리를 받을 수 있다.
백준 BOJ 1303번 : 전쟁 - 전투
문제 난이도 : Silver I
알고리즘 분류 : DFS
'B'로 나타내어진 아군과 'W'로 나타내어진 아군이 직사각형 격자 안에 출력될 때 이들이 뭉쳐진 문자의 수의 제곱만큼 힘을 낸다고 할 때, 두 팀의 힘을 각각 출력하는 문제이다.
위의 문제와 거의 동일하게 visit 여부를 체크하면서 DFS로 문제에서 요구하는 값을 구해줄 수 있다.
뭉쳐진 문자의 개수를 구한 뒤 그 제곱을 a와 b 중 알맞은 곳에 더해 답을 구하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, cnt;
vector<vector<char>> v;
vector<vector<bool>> vis;
void f(int x, int y) {
vis[x][y] = true;
cnt++;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int k=0; k<4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(vis[nx][ny] || v[nx][ny] != v[x][y]) continue;
f(nx, ny);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> M >> N;
v.resize(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vis.resize(N, vector<bool>(M));
int a = 0, b = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(vis[i][j]) continue;
cnt = 0;
f(i, j);
if(v[i][j] == 'W') a += cnt*cnt;
else if(v[i][j] == 'B') b += cnt*cnt;
}
cout << a << " " << b << "\n";
}
백준 BOJ 17129번 : 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유
문제 난이도 : Silver I
알고리즘 분류 : BFS
주어진 맵에서 2에서 시작하여 0인 칸을 따라 이동할 때 3, 4, 5 중 하나에 방문하는 가장 가까운 경로의 길이를 출력하는 문제이다. (만약 도달할 수 없다면 NIE를 출력하면 된다.)
간단한 BFS 문제로, 예외 처리만 간단히 구현해주면 쉽게 해결이 가능하다.
다만 BFS는 기본적으로 동일 solved.ac 난이도 문제들에 비해 코드가 길어지므로 조건 처리 등에서 실수하지 않도록 주의한다. (예를 들면 char로 받았는데 int 값으로 비교를 한다던가 하는 실수가 있다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> vis(N, vector<int>(M, -1));
queue<pair<int, int>> q;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
cin >> v[i][j];
if(v[i][j] == '2') {
vis[i][j] = 0;
q.push({i, j});
}
}
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if(v[x][y] >= '3' && v[x][y] <= '5') {
cout << "TAK\n";
cout << vis[x][y] << "\n";
return 0;
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(vis[nx][ny] != -1 || v[nx][ny] == '1') continue;
vis[nx][ny] = vis[x][y] + 1;
q.push({nx, ny});
}
}
cout << "NIE\n";
}
백준 BOJ 1527번 : 금민수의 개수
문제 난이도 : Silver I
알고리즘 분류 : 브루트포스
주어진 두 수의 범위 내에 있는 4와 7로만 이루어진 수의 개수를 구하는 문제이다.
알고리즘의 분류는 브루트포스이지만 두 수 사이의 모든 수를 다 확인해보라는 문제가 아니다. (범위가 10억이기 때문에 시간 초과가 발생한다.)
4와 7로만 이루어진 수들을 모두 만들어보고 그 중에서 범위에 해당하는 것들을 세면 된다.
처음에는 이진수의 0과 1에 4와 7을 붙이는 방법을 생각해봤는데 모든 이진수는 1로만 시작하기 때문에 이러한 방법은 오히려 어려워진다.
따라서 재귀함수를 이용하여 1부터 10억보다 큰 4와 7로만 이루어진 수들을 만들고 벡터에 저장하여 개수를 세주는 방법으로 구현했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
void f(int cur, int x, string str) {
if(str.length() == x) {
v.push_back(stoll(str));
return;
}
f(cur+1, x, str + "4");
f(cur+1, x, str + "7");
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
for(int i=1; i<=10; i++) f(0, i, "");
int ans = 0;
for(int i=0; i<v.size(); i++)
if(v[i] >= a && v[i] <= b) ans++;
cout << ans << "\n";
}
백준 BOJ 17086번 : 아기 상어 2
문제 난이도 : Silver II
알고리즘 분류 : 브루트포스, BFS
상어까지의 최소 거리가 가장 긴 지점에서의 최소 거리를 구하는 문제이다.
즉, 상어까지의 최소 거리의 최댓값을 가지는 어떤 지점을 찾으면 된다.
브루트포스로 모든 좌표에 대해 BFS를 각각 수행하는 브루트포스 + BFS 문제이다.
이중 for문으로 모든 좌표에 대해 반복문을 돌려주고 각 좌표에 대해 BFS를 통해 가장 가까운 상어의 거리를 찾는다.
이후 답을 갱신하면서 그 최댓값을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> v(N, vector<int>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
vector<vector<int>> vis(N, vector<int>(M, -1));
vis[i][j] = 0;
queue<pair<int, int>> q;
q.push({i, j});
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int k=0; k<8; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(vis[nx][ny] != -1) continue;
vis[nx][ny] = vis[x][y] + 1;
q.push({nx, ny});
}
}
int dist = INT_MAX;
for(int k=0; k<N; k++)
for(int l=0; l<M; l++)
if(v[k][l] == 1) dist = min(dist, vis[k][l]);
ans = max(ans, dist);
}
cout << ans << "\n";
}
백준 BOJ 2942번 : 퍼거슨과 사과
문제 난이도 : Silver II
알고리즘 분류 : 유클리드 호제법
두 사과를 몇 명의 사람들에게 같은 개수씩 하나도 남지 않게 나눠주는 모든 경우를 구하는 문제이다.
두 수의 공약수 개수씩 나눠줘야만 남김없이 모두 동일하게 나누어줄 수 있다.
따라서 두 수의 최대공약수의 약수를 모두 구하고 두 수를 약수로 나눈 수들을 구해주면 된다.
참고로 __gcd 함수를 사용하면 헤더파일에 내장되어있는 gcd 기능을 사용할 수 있다.
N의 약수는 O(N^(1/2))에 구할 수 있으므로 통과 시간은 충분하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
int x = __gcd(a, b);
vector<int> v;
for(int i=1; i*i<=x; i++) {
if(x % i == 0) {
if(i*i == x) v.push_back(i);
else {
v.push_back(i);
v.push_back(x/i);
}
}
}
sort(v.begin(), v.end());
for(int i=0; i<v.size(); i++)
cout << v[i] << " " << a/v[i] << " " << b/v[i] << "\n";
}
백준 BOJ 23057번 : 도전 숫자왕
문제 난이도 : Silver II
알고리즘 분류 : 브루트포스 알고리즘
N개의 수가 주어질 때 이들 중 일부를 합하여 1 ~ (N개 수들의 합) 중에 만들 수 없는 수의 개수를 구하는 문제이다.
N이 20 이하의 자연수이므로 모든 조합을 확인해봐도 O(2^20)으로 충분하다.
재귀 함수를 이용하여 모든 조합을 벡터에 넣고, 중복을 제거하여 답을 구하는 방식을 이용했다.
다만 이 경우 합이 0인 경우도 포함이 되기 때문에 1을 빼주어야 한다.
해시를 사용한 집합과 맵으로 풀이하는 방법도 있는 것 같은데 딱히 떠오르지는 않는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
vector<int> v, u;
void f(int idx, int sum) {
if(idx == N) {
u.push_back(sum);
return;
}
f(idx+1, sum);
f(idx+1, sum+v[idx]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
f(0, 0);
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
int sum = 0;
for(int i=0; i<N; i++) sum += v[i];
int ans = sum - (u.size() - 1);
cout << ans << "\n";
}
백준 BOJ 15975번 : 화살표 그리기
문제 난이도 : Silver III
알고리즘 분류 : 정렬
점들의 좌표와 색깔이 주어질 때, 같은 색깔이면서 가장 가까운 점들로 이은 화살표들의 길이의 합을 구하는 문제이다.
만약 같은 색의 점이 없으면 화살표는 없는 것으로 간주한다.
간단한 정렬 문제로, 같은 색끼리 같은 벡터에 저장한 뒤 색깔별로 정렬을 해주어 가까운 점들을 연결해주면 된다.
각 색의 양 끝 점의 조건문 설정에 주의하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
v.resize(N+1);
for(int i=0; i<N; i++) {
int a, b; cin >> a >> b;
v[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(v[i].begin(), v[i].end());
int ans = 0;
for(int i=1; i<=N; i++) {
if(v[i].size() < 2) continue;
for(int j=0; j<v[i].size(); j++) {
if(j == 0 && j+1 < v[i].size()) ans += v[i][j+1] - v[i][j];
else if(j == v[i].size()-1 && j-1 >= 0) ans += v[i][j] - v[i][j-1];
else ans += min(v[i][j] - v[i][j-1], v[i][j+1] - v[i][j]);
}
}
cout << ans << "\n";
}
백준 BOJ 17413번 : 단어 뒤집기 2
문제 난이도 : Silver III
알고리즘 분류 : 문자열
< >로 둘러싸인 문자열은 뒤집지 않고, 나머지 문자열은 단어 단위로 뒤집어서 출력하는 문제이다.
< > 내부의 문자열에도 띄어쓰기가 존재하므로 처리가 은근 까다롭다.
나의 경우에는 bool 변수를 이용하여 <가 나온 경우 변수를 활성화시켜 스페이스를 만나도 뒤집는 처리를 하지 않도록 처리했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string str; getline(cin, str);
string temp = "";
bool check = false;
for(int i=0; i<str.length(); i++) {
if(str[i] == '<') {
reverse(temp.begin(), temp.end());
cout << temp;
temp = "<";
check = true;
}
else if(str[i] == '>') {
temp += ">";
cout << temp;
temp = "";
check = false;
}
else if(str[i] == ' ') {
if(!check) reverse(temp.begin(), temp.end());
cout << temp << " ";
temp = "";
}
else temp += str[i];
}
reverse(temp.begin(), temp.end());
cout << temp << "\n";
}
백준 BOJ 12018번 : Yonsei TOTO
문제 난이도 : Silver III
알고리즘 분류 : 정렬, 그리디
과목별 정원 수, 수강신청 인원 수, 각 인원이 넣은 마일리지가 나올 때 주어진 마일리지로 수강할 수 있는 과목의 최대 수를 구하는 문제이다.
우선 각 과목을 듣기 위해 필요한 최소 마일리지를 구하고, 이들을 벡터로 정렬하여 작은 과목부터 수강하여 최대 몇 개를 수강할 수 있는지 확인하면 된다.
다만 조건을 잘 읽어보아야 하는 점은, 수강 신청 인원이 정원보다 적은 경우에는 경쟁자가 없는데 이 경우에도 최소 1의 마일리지를 넣어야 과목을 수강할 수 있다는 것이다.
따라서 이 경우 예외 처리를 따로 해주면 정답 처리를 받을 수 있을 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v;
while(N--) {
int a, b; cin >> a >> b;
vector<int> u(a);
for(int i=0; i<a; i++) cin >> u[i];
if(a < b) {
v.push_back(1);
continue;
}
sort(u.begin(), u.end(), greater<int>());
v.push_back(u[b-1]);
}
sort(v.begin(), v.end());
int ans = 0;
for(int i=0; i<v.size(); i++) {
if(v[i] > M) break;
ans++;
M -= v[i];
}
cout << ans << "\n";
}
백준 BOJ 16945번 : 매직 스퀘어로 변경하기
문제 난이도 : Silver III
알고리즘 분류 : 백트래킹, 브루트포스
주어진 3x3 배열 값을 숫자 몇 개를 바꾸어 3차 마방진을 만든다고 할 때, 특정 위치의 수를 a에서 b로 바꿀 때 비용이 abs(a-b)라고 하면 최소 비용이 얼마인지를 구하는 문제이다.
딱히 좋은 풀이가 기억나지 않아 백트래킹으로 모든 종류의 3차 마방진을 구해준 다음, 각 경우에 대한 비용을 구해 최솟값으로 답을 갱신하면서 구해주는 방식을 사용했다.
백트래킹으로 마방진을 짜는 과정이 있어서 풀이 코드가 생각보다 길어졌다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int v[3][3], u[3][3], ans = INT_MAX;
int vis[9] = {};
void f(int cnt) {
if(cnt == 9) {
bool check = true;
for(int i=0; i<3; i++) {
int sum = 0;
for(int j=0; j<3; j++) sum += u[i][j];
if(sum != 15) check = false;
}
for(int i=0; i<3; i++) {
int sum = 0;
for(int j=0; j<3; j++) sum += u[j][i];
if(sum != 15) check = false;
}
if(u[0][0] + u[1][1] + u[2][2] != 15) check = false;
if(u[0][2] + u[1][1] + u[2][0] != 15) check = false;
if(!check) return;
int temp = 0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) temp += abs(v[i][j] - u[i][j]);
ans = min(ans, temp);
return;
}
int x = cnt / 3;
int y = cnt % 3;
for(int i=0; i<9; i++) {
if(!vis[i]) {
u[x][y] = i+1;
vis[i] = true;
f(cnt+1);
vis[i] = false;
}
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) cin >> v[i][j];
f(0);
cout << ans << "\n";
}
백준 BOJ 19941번 : 햄버거 분배
문제 난이도 : Silver III
알고리즘 분류 : 그리디
길이 N인 배열의 각 위치에 햄버거 또는 사람이 위치하고, 사람은 최대 거리 M 이내에 있는 햄버거를 하나 먹을 수 있다고 할 때 햄버거를 먹을 수 있는 최대 사람 수를 구하는 문제이다.
왼쪽 사람부터 가장 왼쪽(현재 위치 - M번째 위치)부터 오른쪽으로 체크해보면서 먹을 수 있는 햄버거가 있을 때 바로 선택해주면 되는 그리디 문제이다.
햄버거를 하나라도 먹을 수 있다면 바로 반복문을 깨주고 다음 사람으로 넘어간다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
string str; cin >> str;
int ans = 0;
vector<bool> v(N);
for(int i=0; i<str.length(); i++) {
if(str[i] == 'H') continue;
for(int j=i-M; j<=i+M; j++) {
if(j < 0 || j >= N) continue;
if(str[j] != 'H' || v[j]) continue;
ans++;
v[j] = true;
break;
}
}
cout << ans << "\n";
}
백준 BOJ 9322번 : 철벽 보안 알고리즘
문제 난이도 : Silver IV
알고리즘 분류 : 해시를 사용한 집합과 맵
N개의 단어로 이루어진 암호문이 주어질 때, 둘째 줄의 해당 위치의 단어가 첫째 줄에 나오는 위치대로 출력하는 문제이다.
즉, map을 이용하여 둘째 줄의 단어가 첫째 줄의 몇 번째에 나왔는지를 구한 후 암호문을 해당 위치에 맞게 벡터에 넣어주어 출력해주면 된다.
위치가 꼬여있어 두 번 생각해야 하지만, 단어의 위치가 가리키는 곳을 잘 생각해보면 그리 어렵게 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
map<string, int> m;
for(int i=0; i<N; i++) {
string str; cin >> str;
m[str] = i;
}
vector<int> v(N);
for(int i=0; i<N; i++) {
string str; cin >> str;
v[i] = m[str];
}
vector<string> u(N);
for(int i=0; i<N; i++) {
string str; cin >> str;
u[v[i]] = str;
}
for(int i=0; i<N; i++) cout << u[i] << " ";
cout << "\n";
}
}
백준 BOJ 14717번 : 앉았다
문제 난이도 : Silver IV
알고리즘 분류 : 구현
1 ~ 10 카드가 2장씩 있는 상황에서 카드를 2장씩 뽑아 우열을 가리는 게임에서 어떤 카드를 뽑았을 때 이길 확률을 구하는 문제이다.
카드가 20장뿐이기 때문에 상대가 남은 카드 중 2장을 뽑는 경우의 수가 그리 많지 않다.
따라서 브루트포스로 모든 경우를 비교하여 이기는 경우의 수와 전체 경우의 수를 구하여 확률을 구하는 방식을 이용했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
if(a > b) swap(a, b);
vector<int> v;
for(int i=1; i<=10; i++) {
if(i == a && i == b) continue;
else if(i == a || i == b) v.push_back(i);
else {
v.push_back(i);
v.push_back(i);
}
}
int tot = 0, cnt = 0;
for(int i=0; i<v.size(); i++)
for(int j=i+1; j<v.size(); j++) {
if(a == b && v[i] == v[j]) {
if(a > v[i]) cnt++;
}
else if(a == b && v[i] != v[j]) cnt++;
else if(a != b && v[i] != v[j]) {
if((a+b)%10 > (v[i]+v[j])%10) cnt++;
}
tot++;
}
double ans = (double)cnt/tot;
cout << fixed;
cout.precision(3);
cout << ans << "\n";
}
백준 BOJ 13116번 : 30번
문제 난이도 : Silver IV
알고리즘 분류 : 트리, 최소 공통 조상
문제에 이진 트리가 주어지고 왼쪽 자식은 n*2, 오른쪽 자식은 n*2 + 1의 노드를 가지고 있을 때 두 노드의 최소 공통 조상의 노드 번호를 구하는 문제이다.
잘 생각해보면 노드 번호를 2로 나누어 내림 처리하면 그것이 부모 노드의 번호가 되므로, 두 노드를 2로 나누는 과정을 거친 값들을 벡터에 저장한 뒤 두 벡터에 들어있는 값 중 최댓값을 찾아주면 그것이 최소 공통 조상의 노드 번호가 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int a, b; cin >> a >> b;
vector<int> v;
while(a > 0) {
v.push_back(a);
a /= 2;
}
vector<int> u;
while(b > 0) {
u.push_back(b);
b /= 2;
}
sort(v.begin(), v.end());
sort(u.begin(), u.end());
int ans = 0;
for(int i=0; i<v.size(); i++)
for(int j=0; j<u.size(); j++)
if(v[i] == u[j]) ans = max(ans, v[i]);
ans *= 10;
cout << ans << "\n";
}
}
백준 BOJ 14753번 : MultiMax
문제 난이도 : Silver IV
알고리즘 분류 : 정렬
N개의 수가 주어졌을 때 2개 또는 3개의 곱의 최댓값을 구하는 문제이다.
간단히 생각해보면 최댓값이 나올 수 있는 경우는 다음 중 하나이다.
1. 2개를 곱하는 경우, 가장 큰 2개의 값의 곱
2. 2개를 곱하는 경우, 가장 작은 2개의 값의 곱 (음수 곱하기 음수는 양수이므로)
3. 3개를 곱하는 경우, 가장 큰 3개의 값의 곱
4. 3개를 곱하는 경우, 가장 큰 1개의 값과 가장 작은 2개의 값의 곱
따라서 O(N log N) 시간에 정렬을 수행해 주고 위의 4가지 경우를 대입해보면 정답을 구할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
int ans = INT_MIN;
ans = max(ans, v[0]*v[1]);
ans = max(ans, v[N-2]*v[N-1]);
ans = max(ans, v[N-3]*v[N-2]*v[N-1]);
ans = max(ans, v[0]*v[1]*v[N-1]);
cout << ans << "\n";
}
백준 BOJ 15970번 : 화살표 그리기
문제 난이도 : Silver IV
알고리즘 분류 : 정렬
위에서 풀이한 15975번 문제와 동일한 문제이다. (단, 이 문제에서의 N의 범위가 5,000 이하로 더 작다.)
동일한 풀이로 제출하면 정답 처리를 받을 수 있다.
참고로 이 문제는 2018년 정보올림피아드의 초등부 문제이고, 위의 N이 10만 이하로 주어지는 문제는 고등부 문제이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
v.resize(N+1);
for(int i=0; i<N; i++) {
int a, b; cin >> a >> b;
v[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(v[i].begin(), v[i].end());
int ans = 0;
for(int i=1; i<=N; i++) {
if(v[i].size() < 2) continue;
for(int j=0; j<v[i].size(); j++) {
if(j == 0 && j+1 < v[i].size()) ans += v[i][j+1] - v[i][j];
else if(j == v[i].size()-1 && j-1 >= 0) ans += v[i][j] - v[i][j-1];
else ans += min(v[i][j] - v[i][j-1], v[i][j+1] - v[i][j]);
}
}
cout << ans << "\n";
}
백준 BOJ 5883번 : 아이폰 9S
문제 난이도 : Silver IV
알고리즘 분류 : 브루트포스
N개의 수가 주어지고 거기서 한 종류의 수를 제거할 때, 연속으로 나오는 수의 최대 길이를 구하는 문제이다.
딱히 마땅한 풀이가 생각나지 않아 v[0]부터 v[N-1]까지 루프를 돌면서 v[i]와 같은 원소들을 모두 제거하고 옮긴 새로운 벡터에서 최대 동일 정수 길이를 구하는 방법을 사용하였다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int ans = 0;
for(int i=0; i<N; i++) {
vector<int> u;
for(int j=0; j<N; j++)
if(v[j] != v[i]) u.push_back(v[j]);
int cnt = 1, Max = 0;
for(int j=1; j<u.size(); j++) {
if(u[j] == u[j-1]) cnt++;
else {
Max = max(Max, cnt);
cnt = 1;
}
}
Max = max(Max, cnt);
ans = max(ans, Max);
}
cout << ans << "\n";
}
백준 BOJ 11507번 : 카드셋트
문제 난이도 : Silver IV
알고리즘 분류 : 문자열
카드들의 종류와 번호가 매겨진 문자열이 입력으로 들어올 때, 각 카드의 종류별 없는 카드의 개수를 구하는 문제이다.
입력되는 문자열의 양식이 종류 1글자, 숫자 2글자로 맞춰서 들어오므로 문자열의 처리가 그다지 어렵지 않다.
2차원 bool 변수를 이용하여 카드가 들어왔는지 여부를 저장해주고, 만약 중간에 중복 카드가 들어오면 체크를 해줘 예외 처리를 해주면 된다.
단순 구현 문제라서 이외에 설명할 부분은 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
bool v[5][14] = {};
string str; cin >> str;
bool check = true;
for(int i=0; i<str.length(); i+=3) {
int a, b;
if(str[i] == 'P') a = 1;
else if(str[i] == 'K') a = 2;
else if(str[i] == 'H') a = 3;
else if(str[i] == 'T') a = 4;
string temp = "";
temp += str[i+1];
temp += str[i+2];
b = stoi(temp);
if(v[a][b]) check = false;
else v[a][b] = true;
}
if(check) {
for(int i=1; i<=4; i++) {
int cnt = 0;
for(int j=1; j<=13; j++)
if(!v[i][j]) cnt++;
cout << cnt << " ";
}
cout << "\n";
}
else cout << "GRESKA\n";
}
백준 BOJ 2238번 : 경매
문제 난이도 : Silver V
알고리즘 분류 : 구현 (+ 정렬 ?)
다음의 규칙에 따라 낙찰이 되는 경매에서 낙찰이 되는 사람의 이름과 가격을 구하는 문제이다.
1. 같은 가격을 부른 사람이 가장 적은 가격을 부른 사람이 낙찰된다.
2. 해당 가격을 부른 사람이 둘 이상일 경우 먼저 부른 사람이 낙찰된다.
위의 조건에 따라 compare 함수를 구현하여 정렬해주고 v[0] 값을 출력해주기만 하면 된다. (물론 이 경우 O(N)에 해결할 수 있는 문제를 O(N log N) 시간에 해결하게 된다.)
정렬을 사용하지 않으면 변수가 많아져서 코드가 난잡해질 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, int> m;
struct s { string a; int b, c; };
bool cmp(s x, s y) {
if(m[x.b] != m[y.b]) return m[x.b] < m[y.b];
else if(x.b != y.b) return x.b < y.b;
else return x.c < y.c;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> v(M);
for(int i=0; i<M; i++) {
cin >> v[i].a >> v[i].b;
v[i].c = i;
m[v[i].b]++;
}
sort(v.begin(), v.end(), cmp);
cout << v[0].a << " " << v[0].b << "\n";
}
백준 BOJ 14729번 : 칠무해
문제 난이도 : Silver V
알고리즘 분류 : 정렬
N개의 데이터가 주어졌을 때 낮은 순으로 7개의 데이터를 출력하는 문제이다.
이 문제를 왜 지금까지 안 풀었나 싶을 정도로 쉬운 문제이다. (아마 제목이 별로 안 끌려서 그런 듯하다.)
아무튼 sort 함수로 정렬을 해서 O(N log N) 시간에 해결해주면 된다.
참고로 데이터의 수가 최대 1,000만개라서 제한 시간이 10초로 넉넉한 편이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<double> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
cout << fixed;
cout.precision(3);
for(int i=0; i<7; i++) cout << v[i] << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 220719 백준 풀이 : BOJ 18977, BOJ 25369, BOJ 25370 등 (0) | 2022.07.19 |
|---|---|
| 220718 백준 BOJ 풀이 : 그래프 탐색 문제들 (너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)) (4) | 2022.07.18 |
| 220716 PS 일기 : 조합론(DP), 카탈란 수 문제들 위주 풀이 (0) | 2022.07.16 |
| 220715 PS 일기 : 탐색(DFS, BFS, 백트래킹), 그리디 쉬운 문제들 (실버 ~ 골드) (0) | 2022.07.15 |
| 220714 PS 일기 : DP 알고리즘, 포함-배제 원리, 분리 집합(union find) 등 (0) | 2022.07.14 |