0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 플로이드 워셜 알고리즘을 사용하는 문제이다! 다익스트라와 플로이드-워셜의 차이는 아래와 같다. 다익스트라 : 하나의 정점에서 다른 모든 정점의 최단거리 플로이드 : 모든 노드간 최단거리 플로이드 알고리즘의 프로세스는 아래와 같다. 인접 배열을 구한다. 1번노드를 중간 노드(거쳐가는 노드)로 설정해, 거쳐가는 경우의 비용이 더 작으면 배열을 갱신한다. n번노드까지 반복한..

문제 출처 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 이 문제는 불과 지훈이의 이동경로를 비교를 해야한다. 따라서 먼저 불의 시간 별 이동경로를 저장하는 배열을 만들어 계산한 뒤, 지훈이가 이동 가능한지 비교한다. 불 이동 경로 초기 입력 시 fire 배열은 INF로 초기화하고, 처음 불이 있던 자리만 0으로 저장한다. bfs로 기존 배열 값보다 값이 작으면 갱신하고 큐에 푸시해준다. int fire[1000][10..

문제 출처 :https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 불쌍한 준석이,,, 우선 완전탐색으로 생각했으나 유니온 파인드로 해결해야하는 문제임을 깨달았다. 유니온 파인드는 아래 패턴을 기억해야 할 것 같다. 1. 같은 집합으로 묶어주는 함수(unionParent) root를 찾아주는 함수(getParent)로 가져온 후 서로의 부모를 지정해준다. void unionPar..

문제 출처 : https://www.acmicpc.net/problem/2195 2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 풀이 최소한의 copy를 사용해 s를 p로 만들 때, 사용 횟수를 출력하는 문제이다. p를 반복문을 돌며 s에서 같은 부분을 찾은 후, 만약 같다면 그 뒤에도 같은지 계속 검사한다. 가장 길게 검사한 부분을 저장해 idx에 더해준다. 코드 #include using namespace std; string s, p; int main(void) { ios::s..

문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 문제가 길고 영어 번역본이라 거부감이 들 수 있겠으나.. 결론은 연결되어 있는 그래프를 탐색하는 대표적인 그래프 탐색 문제이다. 이런 그래프 문제는 보통 아래와 같은 방법으로 처리한다. vector를 배열로 선언한다. a b가 연결되어 있을 경우 서로 푸시한다. v[a].push_back(값), v[b].push_back(값)..

문제 출처 : https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 브루스포스로 해결하면 시간 초과가 발생한다. map을 이용해서 듣도 못한 사람을 저장하고, 보도 못한 사람을 해당 map에서 찾아 있는 경우 vector에 추가 해주었다. sort 함수를 사용해 사전순으로 출력하였다. (sort를 사용하려면 algorithm 헤더 파일을 선언해주어야 한다!) 이분탐색(binary_search)을 활용해 겹치는 사람을 찾는 방법도 있다. 아래 ..