노드가 17개이기 때문에 완전 탐색을 한다. 비트마스킹을 이용해서 방문한 노드들을 표현했다. https://programmers.co.kr/learn/courses/30/lessons/92343?language=cpp 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 참고 : https://blog.encrypted.gg/1029 https://wadekang.t..
Algorithm
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..
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..
해시(Hash)란? 데이터를 다루는 기법 중 하나이며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing)이라고 한다. 해싱이 왜 필요할까? 선형 탐색 또는 이진 탐색은 찾는 키가 자료구조에 들어있는지 반복적 비교가 필요 -> 아무리 빨라도 O(logn) ->더 빠른 알고리즘 필요 ->O(1)을 보장하는 탐색 예로는 키를 그대로 1차원 배열의 인덱스로 사용 ->하지만 단순히 키를 배열의 인덱스로 그대로 사용하면 메모리 낭비가 심해질 수 있음. ∴ O(1) 시간 안에 탐색을 끝내면서 키를 변환하여 배열의 인덱스로 사용하는 방법인 "해싱" 키(key) 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 ..
