✔ 트리의 기둥과 가지[백준 20924]코드 구현하기/* * 문제 분석하기 * : DFS 탐색을 통해 루트 노드부터 기가 노드까지의 길이와 기가 노드부터 리프 노드의 길이들을 구하도록 함 *//* * 손으로 풀어보기 * 1. 루트 노드부터 시작해서 탐색하면서 * 처음 자식 노드가 2개 이상인 노드(기가 노드)를 만나거나 * 리프 노드가 단 1개인 노드를 만나거나 * 루트 노드가 동시에 기가 노드인 경우라면 간선 길이를 구하도록 함 * 2. 이후 기가 노드부터 시작해 리프 노드까지 탐색하며 가장 긴 간선 길이의 합을 구하도록 함 * 3. 구한 트리의 기둥과 가장 긴 가지의 길이를 출력함 *//* * 20924) 트리의_기둥과_가지 */public class Main { stati..
✔ 부품 대여장[백준 21942]코드 구현하기/* * 문제 분석하기 * : 회원 닉네임과 부품 이름에 따른 대여 시간을 저장한 후, * 같은 회원 닉네임과 부품 이름을 가진 정보가 또 다시 들어온다면 두 시각을 계산해 벌금을 계산하도록 함 *//* * 손으로 풀어보기 * 1. 회원 닉네임과 부품 이름에 따른 대여 시간을 저장 * 2. 같은 회원 닉네임과 부품 이름을 가진 정보가 또 다시 들어온다면 두 시각을 계산해 벌금을 계산 * 3. 벌금을 내야하는 사람들을 사전순으로 정렬하여 출력 * 만약 벌금을 내야하는 사람들이 없을 경우는 -1을 출력 *//* * 21942) 부품_대여장 */public class Main { static BufferedReader br = new Buffer..
✔ 후위 표기식[백준 1918]코드 구현하기/* * 문제 분석하기 * : 연산자 우선 순위에 맞춰 후위 표기식으로 변환하도록 조건식을 세우도록 함 *//* * 손으로 풀어보기 * 1. 연산자 우선 순위에 맞춰 후위 표기식으로 변환하도록 조건식으로 세우도록 함 * 피연산자일 경우, 바뀐 식에 추가하도록 함 * 연산자일 경우, '('라면 스택에 추가 * '*, /'라면 자신과 우선순위가 같으며 앞에 있는 연산자를 꺼내 바뀐 식에 추가하도록 함 * '+, -'라면 자신과 우선순위가 크거나 같으며 괄호 사이에 있는 연산자를 꺼내 바뀐 식에 추가하도록 함 * ')'라면 괄호 사이에 있는 연산자를 꺼내 바뀐 식에 추가하..
✔ 우수 마을[백준 1949]코드 구현하기/* * 문제 분석하기 * : 우수 마을을 선정할 때, 인접한 마을에 우수 마을이 있다면 이번 마을을 우수 마을로 선정할 수 없으므로 * 선정 조건에 맞춰 인접한 마을을 탐색하면서 우수 마을의 조합에 따른 마을의 주민 수의 총 합을 구하도록 함 *//* * 손으로 풀어보기 * 1. 인접한 마을 정보를 저장 * 2. 인접한 마을 정보에 따라 첫 번째 마을이 우수 마을일 때와 우수 마을이 아닐 때로 시작하여 우수 마을의 조합을 탐색 * 3. 이전 마을이 우수 마을일 경우, 이번 마을은 우수 마을이 될 수 없음 * 이전 마을이 우수 마을이 아닐 경우에는, 이번 마을은 우수 마을이 될 수도 있고 안 될 수도 있음 * 이때 우수 마을로 선정되지 못한 ..
✔ 개미굴[백준 14725]코드 구현하기/* * 문제 분석하기 * : 단어 정보에 따라 트라이를 구한 후, 개미굴 입구인 루트 노드를 제외하고 트리를 탐색하여 개미굴의 구조를 출력하도록 함 * 예) APPLE, KIWI 중 APPLE → APPLE, BANANA 중 APPLE, BANANA 순 → KIWI * KIWI → APPLE, BANANA 중 APPLE, BANANA 순 * 그러므로 * APPLE * --APPLE * --BANANA * ----KIWI * KIWI * --APPLE * --BANANA *//* * 손으로 풀어보기 * 1. 단어 정보에 따라 트라이 자료구조에 모든 먹이 정보 저장 * 2. 저장해둔..
✔ 도시 분할 계획[백준 1647]코드 구현하기/* * 문제 분석하기 * : 크루스칼 알고리즘을 이용해 각 집들을 연결하는 최소 신장 트리를 찾고 두 마을로 분리하여 최소 유지비의 합을 찾도록 함 * 이 집들을 두 개의 마을로 분리할 때, 마지막 집을 기준으로 두 개의 마을로 분리하여 가장 큰 유지비를 제외하도록 함 *//* * 손으로 풀어보기 * 1. 크루스칼 알고리즘을 이용해 사용하지 않은 엣지 중 가중치가 가장 적은 간선을 선택 * 2. 선택한 간선을 연결했을 때 사이클이 발생하는지 판단 * 3. 간선을 더한 횟수가 정점의 개수 -1이 될 때까지 반복 * 4. 마지막 유지비의 경우, 두 마을로 분리하면 사라지게 되므로 이는 합산하지 않음 * 4. 두 마을로 분리하며 집들을 연결하는 길의 최소 ..
✔ 친구비[백준 16562]코드 구현하기/* * 문제 분석하기 * : 친구의 친구들을 모두 모아 같은 집합으로 합치도록 한 후, 집합의 대표 노드에 해당하는 친구와 친구를 하도록 함 *//* * 손으로 풀어보기 * 1. 친구 관계에 따라 친구비가 더 적은 친구를 대표 노드로 하여 집합으로 묶도록 함 * 2. 집합의 대표 노드에 해당하는 친구와 친구를 하도록 하여 비용을 증가 * 3. 가지고 있는 돈으로 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력 * 4. 만약 친구를 다 사귈 수 없다면 Oh no를 출력 *//* * 16562) 친구비 */public class Main { static BufferedReader br = new BufferedReader(new I..
✔ 줄 세우기[백준 2252]코드 구현하기/* * 문제 분석하기 * : 각 키를 비교한 학생들을 저장한 후, 진입 차수의 개수가 0개인 학생부터 위상정렬하도록 함 *//* * 손으로 풀어보기 * 1. 인접 리스트에 학생 데이터와 진입 차수를 저장 * 2. 진입 차수의 개수가 0인 학생을 큐에 저장 * 3. 위상 정렬 알고리즘을 수행 * 4. 위상 정렬한 결과를 출력 *//* * 2252) 줄_세우기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, M; static ArrayList> arr = new ArrayList>();..
