Little Jay

이차원 배열을 사용해야하는 dp문제 #include #define endl '\n' using namespace std; int n, a, b; int minMul[501][501]; vector v; int matOrder(vector& v, int n) { for (int i = 1; i > a >> b; if (i == n - 1) { v.push_back(a); v.push_back(b); } else { v.push_back(a); } } cout

강연결요소는 DFS를 두번 실행해서 연결된 요소를 찾을 수 있다. stack에 방문한 순서가 아닌 finished 되는 순서로 넣어야하기 때문에 이 점을 주의해서 풀면 될 것이다. 정렬을 빡세게 수행했는데 이렇게까지는 안해도 될 것 같다. #include #include #include #include using namespace std; #define endl '\n' #define vvi vector #define vi vector #define vb vector int n, m; int follower[50001]; void first_dfs(int start, vb& visited, vvi& adj, stack& st) { visited[start] = true; for (auto next : a..

이름에서도 유추할 수 있듯이 플로이드 와샬 알고리즘을 쓰면 된다 #include #define endl '\n' #define INF 987654321 using namespace std; int table[101][101]; int n, m; int a, b, c; void FloydFunction(int n) { for (int k = 1; k > m; for (int i = 1; i a >> b >> c; table[a][b] = min(table[a][b], c); } FloydFunction(n); for (int i = 1; i

시험기간에 너무 공부가 안되서 푼 문제 KMP, Boyer-Moore, NP-Hard, NP-Complete 등등 너무 어렵다 정말 학교에서 알고리즘 과제하는데 string pattern matching 알고리즘이 너무 어려워서 string 관련 문제 하나 풀었다. 어렵지는 않은데 입력을 받을때 cin >> str을 하면 틀리고, getline(cin, str)을 해주면 맞았다 이건 또 왜 그런지 잘 모르겠다 백분율 구하는 문제라서 크게 어렵지는 않았던 문제 #include using namespace std; map m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str; float cnt = ..

1, 2가 입력되었을때를 생각안했다가 틀렸던 문제 base case에 대해서도 항상 생각하자 #include #define endl '\n' using namespace std; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int left = 1; int right = 2; int total = 1; int ans = 0; if (n == 1 || n == 2) { cout

오랜만에 도전해본 골드문제이다 앞서서 포스팅한 백준 1753번 - 최단경로를 활용하면 풀 수 있는 문제이다. 재사용을 위해 다익스트라 최단경로 알고리즘을 함수로 만들었고, 문제에서 구하자고 하는 것이 무엇인지 파악하면 풀 수 있는 문제였던 것 같다. 특이했던 점은 a가 b컴퓨터를 의존하기 때문에 b가 감염되면 a도 감염된다는 점이다. 입력은 a >> b로 받지만, 그래프에 넣을때는 graph[b].push_back({ s, a }); 이런식으로 넣어주어야한다. 이 부분때문에 다익스트라 알고리즘을 잘못짰는지 맞왜틀하고 있었다. 그리고 마지막에 초기화해주는 부분을 잊지 말자. #include #define endl '\n' #define pii pair #define INF 987654321 using na..

처음으로 다익스트라 문제를 풀어보았다. 학교에서 이제 막 다익스트라의 수도코드를 공부했는데, 실제로 구현해보니 너무 어려웠다. 특이하게 다익스트라는 1:1의 경로를 알기 위해서 1:N의 경로를 전부 구해야 문제를 해결할 수 있다는 점이었다. 어째뜬 문제에서 요구하는 것이 1:N의 경로를 요구하는 것이었기때문에 크게 문제가 되지는 않았다. 동아리에서 다익스트라에서 배울때는 변수 이름들을 u, v 등 vertex를 만들때 기본적으로 활용되는 이름들을 썼었는데, 이렇게 코드를 작성하다보니까 직관적으로 다가오지 않아서 변수 이름들을 좀 명확하게 써놓았다. 다익스트라에 좀 익숙해지면 변수명도 교체해야하지 않을까 싶다. #include #define endl '\n' #define INF 987654321 #def..

발냄새라는 단어를 듣고 기계공학과를 떠올린 나...... 최단경로를 찾는 문제이다. 주어진 간선의 weight 정보가 없고, 단순히 출발점으로부터 얼마나 떨어져있는지 물어보는 문제이기 때문에 충분히 BFS으로 풀 수 있다고 판단을 했다. 조심해야 할 점은 그래프가 무향그래프라는 점이다. 그렇기 때문에 입력을 받고, 그래프에 넣을 때 양쪽의 정보를 넣어주어야 문제를 편하게 풀 수 있다. 이런 결의 문제의 경우 인접행렬로 처음에 배열을 int adj[20010][20010]이라고 정의를 하게되면 배열의 사이즈가 4 * 20010 * 20010으로 초기에 너무 커질 것 같아 인접리스트로 푸는것이 더 나은것 같다고 판단했다. #include #define endl '\n' #define INF 987654321..

조금은 까다로웠던 구현 문제였다. 함수 이름을 BFS라고 써놨는데 그냥 check정도가 적당할 것 같다. 입력으로 X가 들어올때 vector에 집어 넣고, 이 vector 컨테이너 안에 있는 시작점들을 바탕으로 탐색을 시작하면 되는 문제였다. 오목이기 때문에 상하좌우 뿐만이 아니라 대각선으로도 이동할 수 있다는 것까지 고려해야 한다. 특이한점은 X가 5개로 연결되는 경우가 정답이 아니라 X가 4개 있고, 하나의 바둑돌을 놓을 수 있어야 정답이 된다. #include #define endl '\n' #define pii pair using namespace std; const int m = 10; char arr[m][m]; vector v; const int dx[8] = { 1, 1, 1, 0, 0, ..

문자열 문제 중 대표적인 문제인 팰린드롬 문제이다. 단순히 문자열이 팰린드롬인지 확인하는 것이 아니라, 재귀적으로 left와 right로 나누어서 팰린드롬을 확인해줘야 했던 문제이다. 종료조건은 문자열의 size가 1일때 return해주면 된다. 여타 팰린드롬 문제가 그러하듯 항상 문자열의 size가 홀수일때와 짝수일때를 구분해주면 된다. #include #define endl '\n' using namespace std; string s; bool palindrome(string a) { if (a.size() == 1) return true; string left, right; int size = a.size() / 2; for (int i = 0; i < size; i++) { left += a[i..