[ 백준 17298 ] 오큰수 : C++ 풀이
나의 접근
이분탐색도 생각해보고, 뒤에서부터 진행도 생각해봤는데 도저히 감이 잡히질 않아서 주제를 봤더니 스택문제였습니다…
스택의 특징을 아직 잘 몰라서 실수를 했는데, 스택이 사용될 수 있는 상황은 다음과 같습니다.
[ 백준 13330 ] 유사 팰린드롬 : C++ 풀이
소스 코드
#include<iostream>
using namespace std;
int n, k, l;
string input;
int u[10001][10001];
int dp[10001]; // 유사 펠린드롬의 여부 = 1 이상이면 해당, 또 1 이상인 값이 여러개 일 경우 가장 적은 값 입니다.
int getU(int s, int e) {
if (s >= e) return 0;
if (u[s][e]) return u[s][e];
if (input[s] != input[e]) return 0;
return u[s][e] = 1 + getU(s + 1, e - 1);
}
bool is_theta(int s, int e) {
if (s == e) return false;
int len = e - s + 1;
int v_len = getU(s, e);
if (k*len <= 2 * v_len * l) return true;
return false;
}
int main() {
cin >> n >> k >> l >> input;
for (int i = 0; i < n; ++i) {
dp[i] = -1;
if (is_theta(0, i)) dp[i] = 1;
for (int j = 1; j < i; ++j) {
// 끝점이 i인 경우를 모두 검색하다보면 dp 값을 한번만 방문할 수 있을 것이다.
// 1 ~ j / j + 1 ~ i 이렇게 두개로 나눔.
// 더 작은 segment로 나뉠 수 있는 것 아닌가? -> 그 경우는 이미 dp[a][b] : b가 i보다 작은 경우에서 모두 구했음.
if (is_theta(j, i) && dp[j - 1] > 0) {
if (dp[i] > 1 + dp[j - 1] || dp[i] == -1) {
dp[i] = dp[j - 1] + 1;
}
}
}
}
cout << ((dp[n - 1] == -1) ? 0 : dp[n - 1]);
}[ 백준 3697 ] 정상 : C++ 풀이
접근
처음 접근은 이랬습니다. 사실 제일 처음에 어려웠던 부분은 d-정상이 무엇인지 이해를 하는 것이였습니다.
d만큼의 높이차가 존재하는 정상들은 모두 정상이다라고 생각을 해서 땅에서부터 그냥 bfs하면 되는것 아닌가 싶은데, 잘못된 방법이였습니다.
[ C++ ] 조합, 순열 을 next_permutation() 으로 순회하기
next_permutation() 이란?
알고리즘을 하다보면 저희가 모든 경우의 수를 뽑아서 봐야할 때가 있습니다. 물론 이런 경우는 사실 대부분 재귀함수를 사용하다보면 해결이 되는 경우가 많습니다.
[ 백준 18809 ] Gaaaaarden : C++ 풀이
소스코드
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n, m;
int r, g;
int board[52][52]; // 맵
vector<pair<int, int>> able_list; // 배양액 뿌릴 수 있는 땅 정보
int dir[4][2] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};
int flowers; // 꽃의 개수
void bfs(vector<pair<int, int>>& gv, vector<pair<int, int>>& rv) {
int visit[52][52] = { 0, }; // 빨간색 -t 값. 초록색 t 값으로 시간을 표현. 1초부터 시작. 0이면 닿지않은 경우임.
int f = 0; // 현재 꽃
queue<pair<int, pair<int, int>>> q; // bfs q
for (auto t : gv) {
visit[t.first][t.second] = -1;
q.push({ -1, t });
}
for (auto t : rv) {
visit[t.first][t.second] = 1;
q.push({ 1, t });
}
while (!q.empty()) {
int time = q.front().first;
pair<int, int> node = q.front().second; q.pop();
int y = node.first;
int x = node.second;
if (visit[y][x] == 9999) continue; // 꽃은 퍼지지 않음.
visit[y][x] = time;
if (time > 0) time++;
else time--;
for (int i = 0; i < 4; ++i) {
int dy = y + dir[i][0];
int dx = x + dir[i][1];
if (visit[dy][dx] + time == 0) {
visit[dy][dx] = 9999;
f++;
continue;
}
if (board[dy][dx] && visit[dy][dx] == 0) {
q.push({ time, {dy, dx} });
visit[dy][dx] = time;
}
}
}
flowers = flowers < f ? f : flowers;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> r >> g;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> board[i][j];
if (board[i][j] == 2) {
able_list.push_back({ i, j });
}
}
}
vector<int> p;
for (int i = 0; i < able_list.size() - r - g; ++i) p.push_back(0);
for (int i = 0; i < r; ++i) p.push_back(1);
for (int i = 0; i < g; ++i) p.push_back(2);
do {
vector<pair<int, int>> r_list;
vector<pair<int, int>> g_list;
for (int i = 0; i < p.size(); ++i) {
if (p[i] == 1) r_list.push_back(able_list[i]);
if (p[i] == 2) g_list.push_back(able_list[i]);
}
bfs(g_list, r_list);
} while (next_permutation(p.begin(), p.end()));
cout << flowers;
}LIS 알고리즘 개념
풀이
풀이는 제 이전 블로그에서 확인 가능합니다.
소스코드 : LIS 3
#include<iostream>
using namespace std;
int n, len;
int arr[1000000];
int lis[1000000];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
len = 1;
lis[0] = arr[0];
for (int i = 1; i < n; ++i) {
int l = 0;
int h = len;
int upper_bound = h;
while (l <= h) {
int mid = (l + h) / 2;
if (lis[mid] < arr[i]) {
l = mid + 1;
}
else if (lis[mid] >= arr[i]) {
upper_bound = mid;
h = mid - 1;
}
}
lis[upper_bound] = arr[i];
if (len == upper_bound) {
len += 1;
}
}
cout << len;
}주의점
upper bound를 확실히 구할 것!
해당 값을 제대로 구했는지 확인할 요소