[백준/BOJ] 1967 트리의 지름 - JAVA문제https://testcase.ac/problems/1967 문제 분석조건트리는 사이클이 없는 연결 그래프이며, 각 간선에는 가중치(거리)가 존재한다.이때 트리에서 가장 긴 경로의 길이(지름) 를 구하는 문제이다.트리의 지름은 두 노드 사이의 가장 긴 거리이다.풀이방법트리는 사이클이 없는 구조이기 때문에, 임의의 노드에서 가장 멀리 있는 노드는 지름의 끝점 중 하나가 된다.즉, 지름의 한 쪽 끝에서 다시 가장 먼 노드를 찾으면 그 길이는 항상 트리의 지름이 된다.DFS를 돌려 끝점을 하나 구한 뒤, 그 점을 기준으로 다시 DFS를 돌려 지름을 구했다.코드import java.io.BufferedReader;import java.io.IOException..

[프로그래머스] 49189 가장 긴 증가하는 부분 수열 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/49189 문제 분석조건1번 노드에서 출발하여 가장 멀리 떨어진 노드가 몇 개인지 구하는 문제풀이방법인접리스트로 그래프를 구성하고 1번 노드부터 탐색한다.방문한 노드마다 거리를 저장하고 카운트 한 뒤, 가장 먼 거리의 카운트를 출력한다.코드import java.util.*;class Solution { public int solution(int n, int[][] edge) { int answer = 0; List[] graph = new List[n + 1]; for (int i = 0; ..

[백준/BOJ] 1931 회의실 배정 - JAVA문제https://www.acmicpc.net/problem/1931문제 분석조건한 개의 회의실이 있고, 회의실에서 사용할 수 있는 회의 N개가 주어진다.각 회의는 시작 시간과 끝나는 시간이 주어진다.겹치지 않게 최대한 많은 회의를 배정할 수 있는 경우의 회의 수를 구하라.풀이방법정렬하여 문제를 풀었다.회의를 빨리 마치는 순으로 정렬한 뒤, 같은 시간에 마친다면 시작시간이 빠른 순으로 정렬하였다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;class Meeting implements Comparable {..

[백준/BOJ] 12865 평범한 배낭 - JAVA 문제https://www.acmicpc.net/problem/12865문제 분석조건N개의 물건이 있다.각 물건은 무게 W와 가치 V를 가지며, 최대 무게가 K인 배낭에 넣을 수 있다면, 가치의 총합이 최대가 되도록 물건을 담는 방법을 구하는 문제풀이방법전형적인 배당문제이다. DP를 이용하여 물건을 선택하거나, 선택하지 말거나를 고르며 최대값을 찾는다.무게가 W인 가방에 i번째 물건을 넣지 않았을 때의 최댓값과 넣었을 때의 최대 가치를 계산하여 식으로 나타내면 `dp[i][W] = max(dp[i-1][W], dp[i-1][W-Wi]+Vi)` 예를 들어 20키로까지 들어갈 수 있는 가방에 4번째 물건이 4키로, 가치가 6이라 했을 때 선택할 수 있는 선택..

[프로그래머스] 42892 길 찾기 게임 - JAVA 문제https://school.programmers.co.kr/learn/courses/30/lessons/42892 문제 분석조건각 노드는 (x, y) 좌표로 주어짐y좌표가 클수록 루트에 가까움x좌표를 기준으로 왼쪽/오른쪽 자식이 결정됨전위 순회, 후위 순회를 한 결과를 배열로 반환해야 함풀이방법노드를 y좌표 기준 내림차순 정렬하면 루트부터 정렬된다. y가 같다면 x 오름차순으로 정렬가장 위에 있는 노드를 루트로 설정나머지 노드들을 이진 트리 규칙(x좌표 기준)에 따라 루트에 삽입왼쪽이면 x 부모.x전위 순회(preorder)와 후위 순회(postorder)를 각각 수행하여 결과 저장코드import java.util.*;class Node impl..

[프로그래머스] 11053 N개의 최소공배수 - JAVA문제https://www.acmicpc.net/problem/14939문제 분석조건`arr`: 길이 1 이상 15 이하의 정수 배열각 원소는 1 이상 100 이하의 자연수배열에 주어진 모든 수의 최소공배수를 구해라풀이방법두 수의 최소공배수는 아래 공식을 사용해서 구할 수 있다.`LCM(a, b) = (a * b) / GCD(a, b)` GCD는 유클리드 호제법으로 구할 수 있음배열의 최소공배수는 순차적으로 두 수씩 계산해 나가면 된다코드class Solution { public int solution(int[] arr) { int answer = 1; int size = arr.length; for (int..