플로이드 와샬 알고리즘을 이용해서 풀었다. 자세한 방법은 아래의 블로그에서 공부해보면 좋을 것 같다. [알고리즘] 플로이드 와샬 (Floyd Warshall) 목차 플로이드 와샬이란? 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다. 하지만 플로이드 와샬 알고리즘은 모든 노드에서 모든 노 propercoding.tistory.com 플로이드 와샬 알고리즘은 A 노드에서 B 노드로 가는 가장 최소한의 길이를 구하는 방법에 사용되는데 거쳐가는 노드를 이용해서 최소한의 길이를 구하는 방법이다. 이 플로이드 와샬 알고리즘의 개념은 어떤 식으로 문제에 대입해서 결과를 도출해내는 것일까? 만약에 A와 B의 관계를 알고 싶다. 하지만 A,C의 관계 정보 C, B의..
코딩테스트
#include #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map collector; for (vector cloth : clothes) { collector[cloth[1]]++; } for (auto &value : collector){ answer *= value.second + 1; } return answer - 1; } 사실 쉬운 문제인데, 어떻게 풀어야할지 헷갈렸었다. 그런 문제는 보면 조합으로 모든 경우의 수를 찾아봐야하나? 이런 생각도 들고 그랬지만 특정 케이스를 찾는 것이 아닌, 경우의 수만 구하면 되기 때문에 의상 수에 +1을 해서 다 곱하고 -1을 하면 아무..
#include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector graph(20001); vector visited(20001, 0); queue queue; vector counts(20001, 0); for (vector line : edge){ graph[line[0]].push_back(line[1]); graph[line[1]].push_back(line[0]); } queue.push(1); visited[1] = 1; int prev = 1; int next = 0; while (queue.size() != 0){ int num = qu..
Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 출퇴근길 문제는 DFS로 풀어야하는 걸 알겠지만 DFS의 탈출 조건에 대해서 이해하고 생각하는데 어려움을 느꼈다. // DFS 레츠고 #include #include using namespace std; int visitedStoT[100001]; int visitedTtoS[100001]; vector dir[100001]; int N, M; int S, T; bool go(int cur, int end, int visited[]){ vector &tmp = dir[cur]; bool pass = false; for (int i = 0; i < tmp.size(); i++){ if (tmp[i] == end){ // 목적지에 도착하면..
Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제는 위 링크에서 확인바란다. 일단 이 문제는 패턴을 파악해서 수식화하는 능력을 요구한다. 첫번째 네모의 한 변에 있는 점의 개수는 2개, 다음은 3개, 다음은 5, 9, 17 ... 이렇게 늘어나는데 패턴은 #include #include using namespace std; int main(int argc, char** argv) { int N; cin >> N; long long lineCount = 2; for (int i = 0; i
이 문제는 딱봐도 DFS느낌이 바로 왔다. 맵에서 1을 만나는 경우 DFS를 이용해서 개수를 찾으면 될 것 같은 느낌이 왔다. 이 아이디어만 있으면 구현부분에서 잘하면 쉽게 풀 수 있는 문제이다. // 딱봐도 DFS #include #include #include #include using namespace std; vector arr; vector collect; vector dx = {1,0,-1,0}; vector dy = {0,1,0,-1}; int howMany = 0; int N; vector split(string &str){ vector line; for (char c : str){ line.push_back(stoi(string(1, c))); } return line; } void df..
#include #include #define ALWAYS_WIN 1 #define HAVE_EVER_LOSE -1 #define NO_FRIEND 0 using namespace std; int main(int argc, char** argv) { int N, M, W; cin >> N >> M; vector iambest(N, 0); vector weight; for (int i = 0; i > W; weight.push_back(W); } int left, right; for (int i = 0; i > left >> right; int prevLeft = iambest[left - 1]; int prevRight = iambest[right..
문제를 풀기 전에 분할 정복에 대해서 알아보자. 분할 정복이란, 문제를 풀 때, 비슷한 부분의 작은 부분으로 쪼개서 계산하고 그 결과들을 통해서 답을 도출하는 방법이다. 총 3가지 단계로 나눠서 문제를 풀게 되는데, 1. Divide : 기존 문제를 작은 부분 문제들로 나눈다. 2. Conquer : 각 부분 문제들을 해결 3. Combine : 부분 문제들의 솔루션을 통해서 기존 문제를 해결 이런 식으로 문제를 푼다. 분할정복의 대표적인 예로는 병합 정렬이 있다. 수퍼 바이러스 문제는 계산하면서 수가 너무 커지기 때문에 미리 계산을 해서 그나마 작은 수들로 계산을 해나가야 하기 때문에 분할 정복을 사용해야한다. 여기서 1000000007의 정체를 궁금해 하는 사람이 있을 것이다. 1000000007는 ..
