Softeer

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 using namespace std; int main(int argc, char** argv) { int N; int workTimeA, workTimeB, moveTimeAtoB, moveTimeBtoA; vector work, move; cin >> N; for (int i = 0; i > workTimeA >> workTimeB >> moveTimeAtoB >> moveTimeBtoA; work.push_back(make_pair(workTimeA, workTimeB)); move.push_back(make_pair(moveTimeAtoB, moveTimeBtoA)); } int A = 0; // A의 최소 시간 기록 int B = 0; ..

#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는 ..

문제 루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다. 코드 #include #include #include using namespace std; int main(int argc, char** argv) { int M,N; int answer = 0; vector arr; cin >> M >> N; for (int i = 0; i > volume >> p..