분류 전체보기 (21) 썸네일형 리스트형 백준 1202번 보석 도둑 https://www.acmicpc.net/problem/1202 두가지 접근 방법이 떠올랐는데- 보석이 들어갈 수 있는 가장 작은 가방을 찾기- 가방에 넣을 수 있는 최대 보석을 찾기첫번째 방법은 시간초과가 발생하여서 두번째 방법으로 풀었다. #include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // 변수 선언 및 초기화 int n, k, m, v, c, idx = 0; long long sum = 0; cin >> n >> k; vector> gems(n); vector bags(k); priority_queue pq; // 입력, 무.. 백준 11404 플로이드 https://www.acmicpc.net/problem/11404플로이드-워셜 알고리즘을 사용하는 기본문제#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, a, b, c; cin >> n >> m; int maxDist = 100000*(n-1)+1; vector> dist(n+1, vector(n+1, maxDist)); for(int i=1; i> a >> b >> c; if(dist[a][b] > c) dist[a][b]=c; } // 플로이드-워셜.. 백준 1167번 트리의 지름 https://www.acmicpc.net/problem/1167 해당 문제는 백준 1967번 트리의 지름 문제와 거의 같다.https://tj1023.tistory.com/20 백준 1967번 트리의 지름https://www.acmicpc.net/problem/1967 입력으로 트리가 주어지면 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것)을 구하는 문제다.트리의 지름을 구하는 방법은 다음과 같다. 1. 임의의tj1023.tistory.com 문제 설명이나 입력 방식에 차이가 있지만 같은 함수를 사용하여 풀 수 있다.마찬가지로 인접행렬을 만든 후 bfs를 두번 돌려 문제를 풀 수 있다. #include #include #include using namespace std;pair bfs.. 백준 1967번 트리의 지름 https://www.acmicpc.net/problem/1967 입력으로 트리가 주어지면 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것)을 구하는 문제다.트리의 지름을 구하는 방법은 다음과 같다. 1. 임의의 노드 u에서 가장 먼 노드 v를 찾는다.2. 노드 v에서 다시 가장 먼 노드 w를 찾는다.3. v와 w 사이의 거리가 트리의 지름이 된다. 위 방법을 바탕으로 BFS를 사용하여 트리의 지름을 구한다. #include #include #include using namespace std;pair bfs(int n, vector>> adj){ pair distant; queue> q; bool visited[adj.size()]={0}; q.emplace(n,0).. 백준 30804번 과일 탕후루 https://www.acmicpc.net/problem/30804 백준의 알고리즘 분류는 브루트포스, 투포인터로 돼있지만구현을 생각해봤을때 큐로 푸는 게 효율적일 거 같았다. #include #include using namespace std;int fruits[10]={0};bool check(){ int c=0; for(int i=1; i0) c++; return c>2;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, fruit, count=0, max=1; queue skewer; cin >> n; for(int i=0; i> fruit; fruits.. 백준 16928번 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 해당칸에 도착하는 최소 횟수를 dp값으로 하였을때사다리는 이전 dp값을 가져오면 돼서 문제가 없지만뱀은 dp 진행 방향을 역행하기 때문에 문제가 발생한다.이를 위해 뱀을 타고 내려가서 다시 최적화 하는 방법이 있다.해당 부분을 고려하여 뱀을 타서 최소값이 갱신된다면 해당 지점에서 다시 진행하도록 했다. #include #include #include #include using namespace std;int n, m;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int x, y; int dp[101]; unordered_map ledde.. 백준 1197번 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 기본적인 최소 스패닝 트리 문제다. 크루스칼 알고리즘과 프림 알고리즘 두가지 방법이 있는데 후자의 방법으로 풀이 하였다. #include #include #include using namespace std;struct edge{ int d, w; // for priority_queue bool operator other.w; }};int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int v, e, a, b, c, cnt=1, sum=0; cin >> v >> e; bool visited[v+1] = {fal.. 백준 2467번 용액 https://www.acmicpc.net/problem/2467 용액들의 특성값이 주어지면 합이 0에 가까운 두 용액의 특성값을 구하는 문제이다. #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, num, sum; vector v; cin >> n; for(int i=0; i> num; v.push_back(num); } int left = 0; int right = n-1; int minleft = 0; int minright = n-1; int minsum = abs.. 이전 1 2 3 다음