Doby's Lab

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 저번에 풀었던 이 문제와 솔루션의 측면에서 비슷하다고 느꼈다.(https://draw-code-boy.tistory.com/191) 1) 모든 정점간의 최단 거리를 구한다. 2) 어떠한 거리를 구하는지 식을 완성하여 도출해낸다. [솔루션] 1) 데이터를 입력받고, 플로이드 와샬을 돌린다. 2) 두 정점을 선택하므로 완전 탐색(브루트 포스)으로 정점 두 개를 택하는 경..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 갑자기 프로그래머스 생각나서 오랜만에 들어가 봤다가 확실히 프로그래머스 문제는 문자..

https://www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net 이번 문제의 포인트는 플로이드 와샬과 문자열을 변환시키는 일이었다. n단 논법에 따라 a가 b라고 해서 b는 a가 되는 것은 아님을 알고 단방향 그래프로 표현해준다. 문자열은 getline을 썼고, n이나 m을 입력받고서는 버퍼에 '\n'가 남아있기 때문에 cin.ignore()을 해준다. #include #include #define MAX (26 + 1) #define INF 987654321 using name..

https://www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net 1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다. 2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다. 3) 플로이드 와샬을 돌린다. 1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다. >> 이 부분이 제일 까다로웠다. 2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다. 선분 구조체를 선언하여 한 노드의 왼쪽 점과 오른쪽 점을 담아주었다. typedef struct { int left, ..

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 자기 자신보다 구슬이 무거운 것이 몇 개 있는지 혹은 가벼운 것이 몇 개 있는지 파악하여 둘 중에 하나가 (n + 2) + 1보다 크거나 같으면 절대 전체의 중간에 있지 않다는 것을 알 수 있다. 그렇다면 어떻게 파악하는가? 플로이드 와샬을 쓰면 된다. 무거운 구슬 가벼운 구슬 순서대로 m개 주어졌을 때 가벼운 구슬에서 무거운 구슬로 가는 경로를 1이라고 설정해주고 나서 플로이드..

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 다익스트라로 하기엔 여러 번 함수 콜이 귀찮아서 플로이드로 한 번에 모든 최소 비용 경로를 구했다. (얼마나 귀찮았으면 플로이드도 짜놓고 콜 안 해서 틀렸을까^^) 1) 모든 최소 비용 경로를 구한다. 2) 1~n까지 돌며 방에 있는 사람들로부터 각 노드로 가는 최소 비용을 다 더 했을 때, 제일 작은 방을 출력한다. #include #include #include #define MAX 100 +..

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이번 문제의 어려운 점은 아마 "i에서 j로 갈 때의 최단 경로에 속한 노드들"을 구하는 것이었다. [시도 #1] 다익스트라에서 경로 역추적했던 것을 영감 삼아 해결해보려 했었다. 3차원 동적배열을 선언하여 i와 j에 k가 들어가면서 최단 경로가 갱신될 때마다 k를 push 했다. if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = gr..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 판단 실수로 플로이드 와샬 안에서도 최단 경로를 갱신할 때 m(수색 범위) 이내에 있는 것만 갱신해줬었다. 어쨌거나 최단 경로들은 모두 갱신한 후에 m(수색 범위) 안에서 갈 수 있는 길을 찾아야 하는 것이 포인트다. #include #include #define MAX 100 + 1 #define INF 987654321 using namespace std; int graph[MAX][MAX]; in..