priority_queue의 디폴트는 max heap이므로 min heap으로 바꾸려면 priority_queue minH; 선언해주기 #include #include #include #define MOD 20171109 using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test_case; int T; cin >> T; for (test_case = 1; test_case > N >> A; maxH.push(A); for (int i = 0; i > a >> b; int num = maxH.top(); maxH.pop(); i..
Algorithm/SWEA
https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Comm..
막혔던 점 -처음에는 dfs로 모든 core마다 방향을 정하고 bfs로 하려고 했으나 시간 초과 해결책 -dfs로 모든 core마다 4방향마다 연결가능할 때->전선표시->dfs(idx+1,coreDone+1)->전선초기화 연결 불가능할 때->dfs(idx+1,coreDone) 주의할 점 -무조건 answer을 최소값으로 갱신하는 것이 아니다. maxDone을 갱신할 때 기존의 answer이 temp보다 더 작을 수 있다. 그래서 maxDone이 같을 때만 최소값으로 갱신한다. #include #include using namespace std; int T, N; int coreNum; int maxDone; int cell[13][13]; int answer; void dfs(int count, int ..
그래프 탐색 -BFS #include #include #include using namespace std; char map[301][301]; bool visited[301][301]; int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1} }; int N; int answer; bool check(int x, int y) { for (int i = 0; i input; for (int j = 0; j < N; j++) { map[i][j] = input[j]; } } play(); for (int j = 0; ..
#include #include #include #include using namespace std; struct tunnel { int a, b; long long cost; }; bool cmp(tunnel a, tunnel b) { return a.cost < b.cost; } int getParent(int a, vector& parent) { if (parent[a] == a) return a; return parent[a] = getParent(parent[a], parent); } bool find(int a, int b, vector& parent) { a = getParent(a,parent); b = getParent(b, parent); if (a == b) return true; r..
알고리즘 : 다익스트라 #include #include using namespace std; int map[101][101]; bool visited[101][101]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int dijktra(int size){ priority_queue pq; pq.push({{0,0},0}); visited[0][0]=1; while(!pq.empty()){ int curTime=-pq.top().first.first; int curRow=-pq.top().first.second; int curCol=pq.top().second; pq.pop(); if(curRow==size-1 && curCol==size-1)return curTime; f..
#include #include #include using namespace std; int main(int argc, char** argv) { int test_case; int T; cin>>T; for(test_case = 1; test_case > str >> K; q.push(str); for (int i = 0; i < K; i++) { set s; int qSize = q.size(); for (int j = 0; j < qSize; j++) { str = q.front(); q.pop(); if (s.count(str) == 1) continue; s.insert(str); for (int k = 0; k < str.size() - 1; k++) { for (int l = k + 1; l ..
완탐 문제에는 나와있지 않지만 고려해야할 조건 1. 수나사끼리 중복 불가능하다. 그리고 암나사끼리 중복 불가능하다. 2. 연결해서 최대 길이를 구할때, 남는 나사가 없다. #include #include using namespace std; int main(int argc, char** argv) { int test_case; int T; cin>>T; for(test_case = 1; test_case > n; vector inputs; vector visited; for (int i = 0; i > a >> b; inputs.push_back({ a,b }); } for (int i = 0; i < n; i++) { string str = to_stri..
