Algorithm283 [BOJ]11085번: 군사 이동 문제: https://www.acmicpc.net/problem/11085 스패닝 트리문제입니다. 크루스칼로 해결할 수 있습니다. 두 정점을 연결하는 간선들 중 최소비용이 최대가 되게 하려면 가장 큰 간선부터 PQ에서 뽑아 그래프를 연결합니다. 그리고 두 정점이 연결되는지 계속 체크합니다. 특정 간선이 뽑히고 두 정점이 처음으로 연결된다면 그 간선이 최소비용이 최대가 되게 하는 정답입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ11085.cc 2020. 5. 29. [BOJ]17490번: 일감호에 다리 놓기 문제: https://www.acmicpc.net/problem/17490 UNION & FIND 문제입니다. M개의 공사구간이 있으면 강의동은 M개의 컴포넌트로 나뉘게 됩니다. 1. M개의 컴포넌트로 나누기 (O(N)) 2. 각 컴포넌트마다 다리를 놓는데 최소비용인 강의동 구하기(O(N)) 3-1. M개의 컴포넌트의 각 최솟값들의 합 K 이면, NO 연결상태는 graph[N][2]를 통해 표현하였습니다. graph[idx][0] = 1이면, idx번째 강의동이 idx-1 강의동과 끊어져 있음. graph[idx][1] = 1이면, idx번째 강의동이 idx+1 강의동과 끊어져 있음. (단, 원형이므로 0번째 강의동과 N-1번째 강의동의 연결관계는 반대로 처리해줘야 합니다) 끝으로 예외 처리해줄 것은 M 2020. 5. 28. [BOJ]15809번: 전국시대 문제: https://www.acmicpc.net/problem/15809 UNION & FIND 문제입니다. FIND를 수행할 때 약 O(logN)에 처리하면 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ15809.cc 2020. 5. 28. [BOJ]1484번: 다이어트 문제: https://www.acmicpc.net/problem/1484 투 포인터로 해결가능한 문제입니다. G = Y^2 - X^2을 만족하는 모든 Y를 구하는 문제입니다. G는 자연수이므로 X 2020. 5. 26. 이전 1 ··· 54 55 56 57 58 59 60 ··· 71 다음
