Little Jay

Naive한 다익스트라 문제 #include #define endl '\n' using namespace std; #define INF 987654321 #define pii pair priority_queue pq; int graph[1005][1005]; int dist[1005]; int n, m; int u, v, w; int start, last; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i > v >> w; if (graph[u][v] > w) graph[u][v] = w; } cin >> start >> last; dist[start] = 0; pq.push(..

처리해야하는 항목은 다음과 같다 문장의 맨 앞에 '_' 가 오는 경우 문장의 맨 뒤에 '_' 가 오는 경우 문장의 만 앞이 대문자인 경우 '__' 같이 언더스코어가 연속적으로 나오는 경우 대문자와 '_'가 복합적으로 나오는 경우 정도를 에러처리 해주면 나머지 구현은 쉽다. Python으로 풀면 더 간단할텐데 C++이라 코드도 길어지고 시간도 오래 걸렸다. toJava 함수에서 위험한 구간이 있는데 s[i + 1] == '_'인 경우를 체크해주는건데 메모리를 잘못 건드려서 seg fault가 날 수 있지 않을까를 생각해봤는데 그 경우의 수는 문장의 마지막에 '_'가 오는 경우이기 때문에 이미 체크를 해서 안전하게 넘어갈 수 있는 것 같다. #include #define endl '\n' using name..

이차원 배열을 사용해야하는 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

어렵지는 않지만 채점하는데 시간이 너무 오래 걸렸던 문제 #include #define endl '\n' using namespace std; char a[100001]; char b[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> a >> b; for (int i = 0; i < strlen(a); i++) { if (a[i] == '1' && b[i] == '1') 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..