10 Sep 2021
// Samsung SW 기출문제
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
int N, M;
int lab[9][9] = {-1};
int visited[9][9] = {-1};
int dfs(int i, int j) {
}
int main() {
cin >> N >> M;
stack<pair<int,int>> list;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> lab[i][j];
visited[i][j] = 0;
if (lab[i][j] == 2) {
pair<int,int> virus = make_pair(i,j);
list.push_back(virus);
}
}
}
int size = list.size();
for (int i=0; i<size; i++) {
dfs(list.top().first, list.top().second());
list.pop();
}
}
09 Sep 2021
지난번에 틀렸던 LCS 문제를 다시 풀어봤다… 데이터 규모가 커지면 저장되는 메모리 위치도 중요하다는 점을 깨달았다. 이 부분을 정리해두면 좋을 것 같다
#include <bits/stdc++.h>
using namespace std;
char st1[1001], st2[1001];
int sub[1001][1001];
int max(int a, int b) {
return (a>b) ? a : b;
}
int lcs(char* st1, char* st2, int st1Len, int st2Len) {
for (int i=0; i<=st1Len; i++) {
for (int j=0; j<=st2Len; j++) {
if (i == 0 || j == 0)
sub[i][j] = 0;
else if (st1[i-1] == st2[j-1])
sub[i][j] = sub[i-1][j-1] + 1;
else
sub[i][j] = max(sub[i-1][j], sub[i][j-1]);
}
}
return sub[st1Len][st2Len];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> st1 >> st2;
cout << lcs(st1, st2, strlen(st1), strlen(st2)); // string은 str.length() / char[]는 strlen(str)
return 0;
}
// 전역변수는 메모리 힙 영역에, 지역변수는 스택 영역에 저장되기 때문입니다 int 100만개짜리 배열이면 4MB인데 보통 스택의 크기를 초과하게 됩니다
07 Sep 2021
class를 이용한 그래프 BFS DFS 큐 스택 리스트 back iterate 소트 정신 없다…😵🤯 조만간 BFS DFS 마스터 하는 걸로 목표!! 💪🏼
#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int s);
void BFS(int s);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V+1];
}
void Graph::addEdge(int v, int w) {
// adj[v].push_back(w);
adj[v].push_front(w);
adj[w].push_front(v);
adj[v].sort(std::greater<int>()); // descending sort
adj[w].sort(std::greater<int>());
}
void Graph::DFS(int s) {
vector<bool> visited(V+1, false);
stack<int> stack;
stack.push(s);
while (!stack.empty()) {
int top = stack.top(); // TOP == S
stack.pop();
if (!visited[top]) {
cout << top << " ";
visited[top] = true;
}
for (auto i = adj[top].begin(); i != adj[top].end(); ++i) {
if (!visited[*i])
stack.push(*i);
}
}
}
void Graph::BFS(int s) {
vector<bool> visited(V+1, false);
queue<int> queue;
visited[s] = true;
queue.push(s);
while (!queue.empty()) {
int front = queue.front(); // FRONT == S
cout << front << " ";
queue.pop();
for (auto i = adj[front].end(); i-- != adj[front].begin();) { // reverse iterator
if (!visited[*i]) {
visited[*i] = true;
queue.push(*i);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, M, V; // N : 정점, Vertex M: 간선, Edge
cin >> N >> M >> V;
Graph graph(N);
int a, b;
for (int i=0; i<M; i++) {
cin >> a >> b;
graph.addEdge(a, b);
}
graph.DFS(V);
cout << "\n";
graph.BFS(V);
}
06 Sep 2021
멍청하게 값 범위가 500인데 팩토리얼 일일이 다 구해서 풀려고 했던 나… 조금 더 수학적으로 접근해야했다…(인터넷 참고 ㅎㅎ)
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
int ans = 0;
int arr[501];
cin >> N;
for (int i=1; i<=N; i++) {
int count = 0;
int temp = i;
while(true) {
if (temp % 5 == 0) {
count++;
temp = temp / 5;
}
else break;
}
arr[i] = count;
}
for (int i=1; i<=N; i++) ans = ans + arr[i];
cout << ans << endl;
}
03 Sep 2021
#include <iostream>
using namespace std;
int arr[9] = {0,};
bool visited[9] = {0,};
void dfs(int a, int b, int n, int m) {
if (b == m) {
for(int i = 0; i < m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
for (int i = a; i <= n; i++) {
visited[i] = true;
arr[b] = i;
dfs(i,b+1);
visited[i] = false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
dfs(1,0,n,m);
}
