Little Jay

오랜만에 도전해본 골드문제이다 앞서서 포스팅한 백준 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..

다익스트라 문제 기록용 #include #define endl '\n' #define INF 987654321 #define pii pair using namespace std; int V, E, start; vector graph[20010]; int dist[20010] = { 0, }; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> V >> E; cin >> start; for (int i = 0; i > u >> v >> w; graph[u].push_back({ w, v }); } for (int i = 1; i < V + ..

파티션을 활용한 브루트포스 문제 #include #define endl '\n' using namespace std; int n; int arr[11]; int calc(int start, int end) { int x = 1; for (int i = start; i > n; for (int i = 1; i > arr[i]; } int temp, ans = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { temp = calc(1, i) + calc(i + 1, j) + calc(j + 1, k) + calc(k + 1, n); ans = max(ans, temp); } } ..

인접행렬로 문제를 푸는 것을 선호하는데, 이렇게 인접 리스트로 푸는게 오랜만이라 시간이 좀 걸렸다. 항상 느끼는 거지만 인접행렬이 더 편한 것 같다. #include #define endl '\n' #define MAX 100005 using namespace std; int n, m, init; vector v[MAX]; bool visited[MAX]; int solve() { int cnt = 0; queue q; q.push(init); visited[init] = true; while (!q.empty()) { auto current = q.front(); q.pop(); if (!v[current].size()) { return cnt; } if (visited[v[current][0]]) b..

입력받는것을 계속 int로 받다가 실패했다. 띄어쓰기가 없는 것은 char이나 string으로 받아야 하는 것에 유의하자. n-1일때 return true 해야하는데 m-1로 계속 써서 실패했다. 항상 조건을 잘 보도록 하자. #include #define endl '\n' using namespace std; int n, m; int board[1005][1005]; bool visited[1005][1005]; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; bool bfs(int y, int x) { visited[y][x] = true; queue q; q.push({ y, x }); while (!q.empty()) {..

greedy한 문제였다 단순히 닭이 소의 시간 안에 들어있는지 아닌지를 파악해주면 되는 문제라 쉬워보였지만, 소를 priority queue로 정렬하는데에 있어서 시작시간만을 기준으로 정렬하면 틀리는 문제였다. priority queue의 정렬 함수를 구현하는 것이 결국 관건이었던 문제이다 #include #define endl '\n' using namespace std; int c, n; struct comp { bool operator()(pair a, pair b) { if (a.second != b.second) return a.second > b.second; return a.first > b.first; } }; vector chicken; priority_queue cow; int main..