LDS - 최장 감소 부분 수열주어진 수열에서 요소들이 감소하는 순서대로 선택되는 가장 긴 부분 수열을 말한다.수열의 원래 순서를 유지하면서 순서대로 감소하는 숫자들을 선택하여 만들 수 있는 가장 긴 부분 수열을 찾아야 한다.DP반복문을 돌면서 감소하는 부분 수열의 최대 길이를 배열에 저장하는 메모이제이션 방식으로 문제를 풀어야 한다. 최대 길이가 저장되는 배열을 dp라고 할 때, dp는 모두 1로 초기화한다.감소하는 부분 수열이 없다면 자기 자신만 가지게 되기 때문이다. 감소하는 부분 수열이기 때문에 자신보다 왼쪽에 있는 값이 더 커야 한다.먼저 기준 값(A [I])을 정하고, 왼쪽의 값(A [J])들을 모두 비교한다.A [J]가 A[I] 보다 크다면 A [J]가 가진 길이에서 +1 하여 A [I]의 ..

'완벽하게 게임을 했을 때'라는 말이 조금 추상적으로 들렸다.턴이 길어져도 1개씩 가져가는 것인지이길 수 있는 최적의 선택을 하는 것인지문제를 풀고 봤을 때, 이상한 포인트에 고민을 했던 것 같다.후자라고 판단되어, 남은 돌의 갯수가 3개 이상인 경우 3개를 가져갈 수 있도록 하고, 반대라면 1개를 가져가결과적으로 남은 돌의 갯수가 0이 될 때까지 반복할 수 있도록 구현했다. 구현 1 - 일반 반복문import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste..

각 주사위의 윗면은 이전 주사위의 아랫면과 일치해야 한다는 규칙에 맞게,주사위마다 아랫면과 윗면을 정하고 옆면의 최댓값을 구해야 한다.그리고 ABCDEF 중 정해진 아랫면과 윗면이 없어 모든 경우를 고려해야 한다. 주사위의 마주 보는 면을 구할 때 (0,5) , (1,3) , (2,4) 관계가 고정이므로 해당 조건에 맞게 윗면, 아랫면을 구해야 한다.구해진 면의 주사위 값을 제외한 최댓값을 찾고, 주사위마다 이 과정을 반복한다. 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public s..

풀이주어진 wires를 모두 한 번씩 끊었을 때 나올 수 있는 각각의 전력망에서,송전탑의 개수를 비교하여 차이를 반환해야 한다. 모든 wires를 끊어보려면 반복을 돌 때마다 전선 환경을 초기화해줘야 한다.만약 1, 3번 전선을 끊었을 때의 송전탑 차이를 계산했다면계산한 값을 저장해두고 끊었던 전선을 다시 연결해줘야 한다.위 과정을 반복해서 송전탑 차이가 가장 적은 값을 반환해 주면 된다. 구현import java.util.*;class Solution { private List[] tree; private boolean[] visited; public int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; ..