목록전체 글 (591)
어흥
문제 링크: www.acmicpc.net/problem/6059 6059번: Pasture Walking The N cows (2 b>>val; arr[a][b]=val; arr[b][a]=val; } floyd(); for(int i=0;i>a>>b; cout
문제 링크: www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘 + 경로 찾기 알고리즘에 대해 알고 있어야 한다 2. 구현 - 코드를 li 리스트에 담는다 - calHamilton() 함수를 통해 각 코드 사이의 해밀턴 거리를 Arr[][]에 저장한다 - Dijkstra() 함수를 통해 시작점부터 목표지점까지의 최단거리를 구한다. 이때, 두 코드간의 최단거리가 갱신된다면 Pre[]함수를 통해 이전 경로를 저장한다. 만약..
문제 링크: www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 1. 주의할 점 - 출력에 있어 3가지의 경우가 있다 - 정답이 여러개인 경우, 사전순으로 앞선 경우를 출력한다 2. 구현 - BFS를 통해 정답을 도출한다 - 최대 범위가 10^9이므로 곱셈 혹은 덧셈의 결과가 10^9를 넘기지 않도록 한다 - 사전순으로 빠른 순서대로 BFS 탐색을 시작하며, 연산 결과의 숫자가 존재하지 않는 경우, Set과 큐에 추가한다 - 큐에서 꺼낸 원소가 Targe..
문제 링크: www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 주의할 점 - 모든 TC가 진행되기 전, 변수를 초기화한다 - 트리가 이뤄지지 않은 Node는 무시한다 → 무조건 Tree가 없다고 하면 WA 2. 구현 - 트리의 특징인 노드 N개 → 간선 N-1개를 통해 MST를 떠올린다(MST도 똑같이 노드 N개, 간선 N-1개) - 트리가 많을 수 있기 때문에 MST의 방법중 하나인 유니온 파인드를 사용한다 - Par[] 함수를 통해 ..
문제 링크: www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 주의할 점 - LCA 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 수행되는 알고리즘을 이해하도록 한다 2. 구현 - 모든 변에 대해 입력받은 후, havePar[] 배열을 통해 트리의 Root를 찾는다 - DFS() 함수를 통해 각 Node의 트리에서 높이를 구한다 - Make_tree() 함수를 통해 N번째 Node의 2^i번째 높..
문제 링크: www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 1. 주의할 점 - A와 B의 범위가 10만개 + 짝을 이루기 때문에 Set혹은 Map을 사용한다 2. 구현 - sInfo 구조체를 통해 A와 B 물통에 남은 물의 짝을 저장한다 - Info 구조체를 통해 A, B, 수행한 명령 수를 저장하고 우선순위큐는 수행한 명령 수의 오름차순으로 정렬한다 - 현재 시점으로 3가지의 과정을 수행해보고 Set에 없다면..
1. Class 설정 public static class Info{ int num; String name; public Info(int num, String name){ this.num = num; this.name = name; } }; 2. HashSet 설정 + 클래스의 값 비교 public static void main (String[] args){ HashSet hs = new HashSet(); hs.add(new Info(1,"Eric")); System.out.println(hs.contains(new Info(1,"Eric")));//false Info ii = new Info(2,"Andrew"); hs.add(ii); System.out.println(hs.contains(ii));/..
문제 링크: www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 끝내도록 한다 2. 구현 - 같은 통로에 있을때까지 이동한다 → A에서 B까지 이동한다 - 1개의 변을 뺀다 → 빼는 1개의 변이 최단경로중 가장 값이 크면 움직인 거리가 최소가 된다 → 다익스트라 알고리즘 + 변의 최장 길이 저장 - Dist[] 배열을 통해 시작지점에서 각 지점까지의 최단거..