[백준 5052] 전화번호 목록 (자바)
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 난이도 : 골드 4 트라이를 이용했습니다. 2021/01/07 - [문제풀이/자바] - [백준 14725] 개미굴 (자바) [백준 14725] 개미굴 (자바) https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 ..
[백준 14725] 개미굴 (자바)
https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 난이도 : 골드 2 트라이를 이용하여 풀었습니다. 트라이는 문제에서 주어진 그림처럼 문자열 트리라고 생각할 수 있습니다. 전역 변수 StringBuilder sb = 트라이 구조를 그려서 저장할 변수 함수 void main 입력을 받고 트라이를 구현합니다. 19번째 줄에서는 n개의 입력을 받고 24번째 줄에서는 한 줄의 입력에서 k개의 입력을 트라이에 넣습니다. 노드는 트라이를 탐색..
[백준 1937] 욕심쟁이 판다 (자바)
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 난이도 : 골드 3 DFS와 메모이제이션을 이용했습니다. 메모이제이션은 다이나믹 프로그래밍처럼 이전에 계산해 둔 값을 나중에 계속 이용하여 불필요한 계산을 줄일 수 있습니다. 이 문제에서 숲의 최대 크기는 500x500입니다. 메모이제이션을 이용하여 계산의 중복을 막아 시간 초과를 예방했습니다. 판다가 이동할 4방향의 칸을 DFS를 통해 계산해줬습니다. 그리고 4방향 중 최댓값에서 1을 ..
[백준 1865] 웜홀 (자바)
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 난이도 : 골드 4 음의 가중치가 있는 그래프의 최단 거리를 구할 수 있는 벨만-포드 알고리즘을 이용했습니다. 다익스트라 알고리즘은 음의 가중치를 가지는 그래프의 최단 경로를 구하지 못하고 무한 루프에 빠지게 됩니다. 하지만 벨만-포드 알고리즘은 최단 경로를 구할 수 있고 엄청난 시간 복잡도를 자랑합니다. 또, 음의 가중치들이 만드는 사이클을 탐지할 수 있습니다. 벨만-포드 알고리즘은..
[백준 1967] 트리의 지름 (자바) && [백준 1167] 트리의 지름 (자바)
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 난이도 : 골드 4 가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2 일 것입니다. 여기서 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있습니다. 가장 먼 노드는 dfs로 구했습니다. https://www.acmicpc.net/p..
[백준 1944] 복제 로봇 (자바)
https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 난이도 : 골드 2 문제가 복잡하지만 크루스칼 알고리즘으로 풀 수 있습니다. S, K(포인트라 하겠음) 상관없이 모든 포인트끼리의 거리를 구해 우선순위 큐에 넣으면 됩니다. BFS를 통해 각 포인트를 출발점으로 해서 도달 가능한 모든 포인트까지의 거리를 구합니다. 크루스칼 알고리즘을 돌리고 parent 값(find)은 모두 0이어야 합니다. 만약 0이 아니라면 어느 ..
[백준 1197] 최소 스패닝 트리 (자바)
난이도 : 골드 4 크루스칼 알고리즘을 이용하여 풀었습니다. 크루스칼 알고리즘은 모든 간선을 오름차순으로 정렬하여 가장 작은 값부터 골라 MST(Minimum Spanning Tree)를 구성합니다. 단, 이때 사이클이 생기는 간선은 추가할 수 없습니다. 간선을 오름차순 정렬하여 하나씩 뽑는 것은 우선순위 큐, 사이클 검사는 Union-Find를 이용했습니다. 2020/11/06 - [정보/CS] - Union-Find 유니온 파인드 Union-Find 유니온 파인드 2020/11/06 - [문제풀이/자바] - [백준 1976] 여행 가자 (자바) [백준 1976] 여행 가자 (자바) 난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제 jellyin..
[백준 4386] 별자리 만들기 (자바)
난이도 : 골드 4 크루스칼 알고리즘을 이용하여 풀었습니다. 별의 거리는 Math.sqrt(Math.pow(star[i].x - star[j].x, 2) + Math.pow(star[i].y - star[j].y, 2))입니다. 모든 별의 거리를 우선순위 큐에 넣고 크루스칼 알고리즘을 돌렸습니다. 정답 출력은 round를 이용했습니다. 전역 변수 int parent[] = 그룹의 대표를 나타내는 배열 함수 void main 입력을 받고 star, pq를 세팅합니다. 크루스칼을 돌리고 정답을 출력할 때 round를 이용했습니다. 0.666666이라는 수를 둘째 자리까지 출력해야 할 때를 예로 들면 0.666666*100 = 66.6666 여기서 반올림하면 67 그리고 다시 100으로 나누면 0.67이 됩니..