코딩 테스트/백준 (18) 썸네일형 리스트형 백준 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; } // 플로이드-워셜.. 백준 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.. 백준 2166번 다각형의 면적 https://www.acmicpc.net/problem/2166 N각형의 점의 x, y 좌표가 순서대로 주어질때 면적을 구하는 문제다. 위와 같은 신발끈 공식을 사용하여 문제를 풀 수 있다. #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; double sum=0; cin >> n; long long x[n]; long long y[n]; for(int i=0; i> x[i] >> y[i]; for(int i=0; i 포인트는 다음과 같다 1. 값의 범위에 따른 자료형에 주의하여 double과 long l.. 백준 2580번 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루www.acmicpc.net스도쿠를 입력받고 0에 해당하는 빈칸을 채우는 문제다. 백트래킹을 통해서 풀어보았다.# 스도쿠 채우기def sudoku(n): if n == len(blank): # 빈칸을 모두 채우면 for i in range(9): for j in range(9): print(arr[i][j], end=' ') # 완성된 스도쿠 출력 .. 이전 1 2 3 다음
