트리

알고리즘 문제) BOJ 14725. 개미굴 링크 : https://www.acmicpc.net/problem/14725문제 요약로봇 개미로부터 얻은 개미굴 저장소를 바탕으로, 개미굴 구조를 출력해라예를들어, 아래와 같은 정보를 받았다면KIWI BANANAKIWI APPLEAPPLE APPLEAPPLE BANANA KIWI아래처럼 출력해라 APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA개미굴의 각 층은 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다시간 제한1초입력첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개두 번째 줄부터 N+1 번째 ..

알고리즘 문제) BOJ 16934. 게임 닉네임 링크 : https://www.acmicpc.net/problem/16934문제 요약각 유저는 가입할 때, 자신의 닉네임을 정해야 하며, 중복이 가능하다이때, 유저 닉네임의 접두사 중 가장 길이가 짧은 것을 별칭으로 하려고 한다이때, 접두사는 이전에 가입한 닉네임의 접두사가 아니어야 한다가능한 별칭이 없는 경우에는 유저가 가입한 시점까지 같은 닉네임으로 가입한 사람의 수 x를 계산해야 한다.x가 1인 경우에는 닉네임을 별칭으로 사용하고, x가 2 이상인 경우에는 닉네임의 뒤에 x를 붙여서 별칭으로 사용유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구해보자시간 제한2초입력첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)둘째 줄부..

알고리즘 문제) BOJ 5052. 전화번호 목록 링크 : https://www.acmicpc.net/problem/5052문제 요약전화번호 목록이 주어질 때, 일관성 여부를 확인해라일관성을 유지한다는 것은한 번호가 다른 번호의 접두어인 경우가 없어야 한다예를들어, 아래와 같이 존재한다면91191123911을 치자마자 바로 첫번째 전화로 걸려버리기 때문에 일관성이 없다시간 제한1초입력테스트 케이스 개수 t1 ≤ t ≤50각 테케의 첫째줄에는 전화번호 수 n이 주어진다1 ≤ n ≤ 10000다음 n개의 줄에는 목록에 포함된 전화번호가 한 줄씩 주어진다최대 10자리이며, 중복된 경우 X출력각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력접근법일관성이 없다즉, 특정 전..

트라이 정의문자열을 저장하고 검색하는 효과적인 트리 구조의 자료구조각 노드가 문자를 가지며, 루트 노드부터 자식 노드를 따라가며 문자열을 구성루트 노드루트 노드는 비어 있다루트 노드의 자식 노드는 각 단어들의 첫 글자를 나타낸다.사용하는 이유?좀 더 빠르게 문자열을 탐색할 수 있다그러나 각 노드마다 문자, 자식 노드 객체를 저장한다는 점에서 메모리가 많이 필요하다는 단점이 존재 구현노드 클래스와 트리 클래스 2개를 갖는다.노드 클래스각 노드는 child라는 자식 노드의 맵을 가짐Map단어의 끝인지를 표시 하는 boolean 타입 변수 필요트리 클래스트라이의 자료구조를 구현한 클래스insert 메서드 : 단어를 트라이에 삽입search 메서드 : 단어가 트라이에 존재하는지 확인static class Nod..

알고리즘 문제) BOJ 1595. 북쪽나라의 도로 링크 : https://www.acmicpc.net/problem/1595문제 요약두 도시 사이마다 유일한 도로가 설계되어 있다모든 도시는 다른 모든 도시로 이동이 가능 할 때, 거리가 가장 먼 두 도시 사이의 거리를 출력해라최대 10,000개의 도시가 있을 수 있고, 도시는 1 부터 숫자로 이름이 매겨져 있다시간 제한1초입력각 줄은 세 개의 양의 정수로 구성되며, 각각은 서로 다른 두 도시 번호와 두 도시를 연결하는 도로의 길이를 의미한다출력가장 리가 먼 두 도시간의 거리를 나타내는 정수 하나를 출력해라접근법입력이 언제까지 주어지는지 문제에 안 나와 있어서, 최대 10000개의 도시로 가정하고 풀었다.입력을 받는 입력이 더이상 주어지지 않아 Error가..

트리의 정의트리란?임의의 두 노드를 연결하는 단순 경로가 정확히 하나 존재하는 그래프단순 경로 : 같은 노드를 2번 이상 지나지 않는 것.다음과 같은 조건을 만족하면 트리🌲① 모든 노드가 하나의 연결 요소 ② 사이클이 없어야 한다.③ 노드의 개수가 간선의 개수보다 하나 많다.ex) 노드가 3개면 간선은 2개1번, 2번 조건을 만족하면 3번 조건도 만족할 수밖에 없다. (간선이 N개가 되면 무조건 사이클이 생길 수 밖에 없음)2번, 3번 조건을 만족하면 1번 조건도 만족하고, 1번, 3번 조건을 만족하면 2번 조건도 만족한다.즉, 위 조건 중 2개가 문제에 나오면 트리라고 생각하면 된다.ex) 두 도시를 지나는 경로는 정확히 하나 존재 ⇒ 트리ex) 어떤 두 도시를 잡을 때 그 경로가 무조건 존재하고, ..

알고리즘 문제) BOJ 14676. 영우는 사기꾼? 링크 : https://www.acmicpc.net/problem/14676문제 요약우주 전쟁건물을 짓는 순서가 정해져있음ex) 1번 건물을 지어야 2번, 3번 건설 가능 = 1번 건물이, 2,3,번에 영향을 미친다한 건물은 최대 3개 건물에게만 영향을 미칠 수 있으며, 중복 건설이 가능하다.치트키 ⇒ 원하는 건물을 마음대로 지을 수 있음주어진 정보를 보고 영우가 치트키를 사용했는지 안헀는지 파악하기시간 제한1초입력첫째 줄 : 건물 종류 개수 N, 건물 사이 관계 수 M, 영우의 게임 정보 개수 K1 ≤ N,M,K ≤ 10만다음 M개의 줄에 걸쳐 건물 관계인 X, Y가 차례대로 중복 없이 주어짐X를 건설해야 Y건설 가능1 ≤ X, Y ≤ N다음 줄부터 ..

알고리즘 문제) BOJ 14950. 정복자 14950번: 정복자서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재www.acmicpc.net문제 요약N개의 도시(1~N)와 M개의 도로(양방향)로 구성모든 도시 쌍에는 도로로 이어져 있음각 도로는 비용이 존재모든 도시를 정복하려고 함처음 점거 중인 도시는 1번 도시만약 B도시를 점거하고 싶다면, B와 연결된 도시 중 최소 하나 정복해야 함만약 A선택하면 B정복과정에서 A와 B를 연결하는 도로 비용도 소모한 번 도시가 정복 되면 모든 도로의 비용이 t만큼 증가이미 정복한 도시는 또 정복 X모든 도시 정복하는 데 드는 최소..

알고리즘 문제) BOJ 1240. 노드사이의 거리 링크 : https://www.acmicpc.net/problem/1240문제 요약N개의 노드와 M개의 두 노드 쌍이 주어질 때, 두 노드 사이 거리 출력하기시간 제한2초입력노드 개수 N, 거리를 알고 싶은 노드 쌍의 개수 M2≤N≤10001≤M≤1000N-1개줄에 두 점과 거리를 입력 받음거리는 1만 이하 자연수마지막에 거리를 알고 싶은 M개의 노드 쌍이 한 쌍씩 입력 됨출력M개의 줄에 차례대로 입력받은 두 노드 사이 거리 출력코드import java.io.*;import java.util.*;public class Main { static int N, M; static ArrayList[] list; static int from, to..

알고리즘 문제) BOJ 9985. Claws 링크 : https://www.acmicpc.net/problem/9885문제 요약이진 트리가 주어짐힌지 등급 = 해당 노드에서 루트 노드까지 경로 상에 있는 간선 가중치 합이때 서브트리의 힌지 등급을 누적해서 더해줌unladen load : 힌지가 견딜 수 있는 최대 무게즉 노드 1의 unladen load = 노드 1의 힌지등급(50) + 부모 노드 4의 힌지등급(60) + 부모 노드 5의 힌지등급(110) = 220 이된다.이때 최대 unladen load를 출력하기시간 제한2초입력노드 개수 N1≤N≤12000자식 노드, 부모노드, 가중치가 N-1개 주어짐가중치는 100이하출력최대 unladen load를 출력하기접근법각 노드별 unladen load 구..