Little Jay

long long을 사용하는 lcm문제 간단하게 재귀로 작성해도 맞았다 #include using namespace std; long long gcd(long long a, long long b) { if (a % b == 0) return b; return gcd(b, a % b); } long long lcm(long long a, long long b) { return a * b / gcd(a, b); } int main() { long long x, y; cin >> x >> y; cout

정렬을 잘 생각해보면 되는 문제 3개씩 묶고 제일 작은 것을 제외한 숫자를 제외하고 total에 더해주면 된다 #include #include #include #include using namespace std; vector v(100001); int main() { int n; cin >> n; for (int i = 0; i > v[i]; } sort(v.begin(), v.end(), greater()); int total = 0; for (int i = 0; i < n; i++) { total += v[i] + v[i + 1]; i += 2; } cout

간단한 gcd, lcm 문제 #include using namespace std; int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); } int main() { int n; cin >> n; for (int i = 0; i > x >> y; cout

DP를 사용하는 문제 DP의 합과 입력받은 arr의 숫자를 잘 비교하면 되는 것 같다. #include #include using namespace std; int arr[100001]{ 0, }; int dp[100001]{ 0, }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i > arr[i]; } dp[1] = arr[1]; int result = dp[1]; for (int i = 2; i

문제파악을 잘 해야하는 문제이다. 일반적인 GCD 알고리즘을 사용하면 되는데, 최대 공약수만큼 1을 출력해주면 된다. #include using namespace std; long long GCD(long long a, long long b) { if (a % b == 0) return b; return GCD(b, a%b); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); long long a, b; cin >> a >> b; long long result = GCD(a, b); for (int i = 0; i < result; i++) cout

string을 잘 split하고 reverse 하면 풀 수 있는 문제 #include #include #include #include #include using namespace std; vector split(string input, char delimiter) { vector answer; stringstream ss(input); string temp; while (getline(ss, temp, delimiter)) { answer.push_back(temp); } return answer; } int main() { int n; cin >> n; cin.ignore(); for (int i = 0; i < n; i++) { string s; getline(cin, s); vector v = sp..

dfs로 간단하게 풀 수 있는 문제이다. 1번 컴퓨터를 통해 감염되는 컴퓨터의 개수를 출력하면 되기 때문에, 탐색을 할 노드를 1번 노드로 고정을 해놓고, 1번 노드를 통해 다시 재귀로 탐색을 할 때마다 감염된 컴퓨터의 수를 하나씩 증가시켜주면 된다. #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; int infected = 0; void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { infe..

dfs 혹은 bfs로 풀 수 있는 문제이다 이 문제를 재귀를 활용한 dfs로 풀었는데 graph를 먼저 채운 다음 탐색을 시작한다 문제의 1번 예제를 살펴보면 1, 2, 5가 연결되어 있는데 탐색을 할 때 1, 2, 5의 탐색이 종료되면 main 함수에 있는 for문에서 dfs를 시작할 숫자는 3이 된다 이때 연결 요소의 개수를 증가시켜주면 된다. #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node]..

기본적인 그래프문제 #include #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; printf("%d ", node); for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { dfs(next); } } } void bfs(int start) { queue q; memset(check, false, sizeof(check)); check[start] = true; q.push(start); w..

간단한 이진탐색 문제 참 메모리라는게 아속하다 문제의 태그에는 set 혹은 map이 달려있어서 처음에는 당연히 set으로 풀었는데 시간초과가 발생해버렸다. 아무래도 set이나 map이나 기능적으로 이진트리의 모습을 만들어야하기 때문에 계속해서 sort해주는 부분에서 메모리를 많이 잡아먹은 것 같다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; for (int i = 0; i > n; vector v; for (int j = 0; j > temp; v..