분류 전체보기75 [TIL] LIS(최장증가수열) 에 대한 공부 dp문제를 풀다가 lis를 사용해야하는 문제가 나왔다. 예전에 알고특을 들을 때 그냥 가볍게 읽고 넘어간 내용이라 다시 떠오르려 하니 기억이 안 나는 상황 발생...(허걱) 완전히 이해하지 않고 그냥 이런거구나~ 하고 넘어가서 그런것같다. 게다가 난 dp에 약하기도 하고... 문제를 풀 아이디어가 번뜩하고 떠올랐음 좋겠다 .....ㅠㅠ 쨋든 최장증가수열에 대해 포스팅 시작하겠다 최장증가수열 : 최장증가수열은 길이 N인 수열이 있을때, 처음부터 하나씩 idx를 증가해나갈때 값이 증가하는 길이의 최댓값을 가지는 수열이다. 표로 보면 더 쉽다. 수열 arr value 5 2 4 1 6 3 7 idx 0 1 2 3 4 5 6 여기서 idx가 0인 5부터 시작해서 하나씩 idx를 증가해가면서 value가 증가하는.. 2023. 11. 9. [백준문제풀이] 17142 연구소3 java 접근법 : **1) 어떻게 풀 것인가?** **2) 시간복잡도** **3) 공간복잡도** **4) 풀면서 놓쳤던점** **5) 이 문제를 통해 얻어갈 것** //17142 연구소2 // 내가 생각한 풀이 방법 // 1. 값이 2인 좌표를 받기. // 2. 위 좌표들 중 조합을 사용하여 N개만큼 뽑고, 위 좌표들이 다 퍼지는데 얼마나 시간이 걸리는지에 대한 계산 // 3. 위 계산 중 가장 작은 값 출력. // ** 좌표가 중요한게 아니라 최소시간이 중요한거야 // import java.io.*; import java.util.*; public class Main { static class virus{ int x,y,vday; virus(int x, int y, int vday){ this.x = x; t.. 2023. 11. 5. [백준문제풀이] 15649 N과M 접근법 : **1) 어떻게 풀 것인가?** 문제는 쉽게 이해간다. 1부터 n까지의 수를 M개씩 중복순열로 출력하면 된다. **2) 시간복잡도** O(n!)인데 n의 최대는 8이므로 시간안에 충분히 가능하다 **3) 공간복잡도** 512mb **4) 풀면서 놓쳤던점** 딱히 없다 **5) 이 문제를 통해 얻어갈 것** 백트래킹에 대한 이해! import java.io.*; public class Main { static int n,m; static int[] ints; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { Buf.. 2023. 11. 3. [백준문제풀이] 11404 플로이드 java풀이 접근법 : **1) 어떻게 풀 것인가?** 플로이드 워셜을 사용한 문제 알고리즘 특강때 플로이드 워셜에 대해 설명을 듣고 나서 푼거라 어려운점은 없었다. **2) 시간복잡도** O(n^3)인데 n의 최댓값이 100이고, 이 문제는 1초의 제한시간을 가지므로 제한시간안에 가능하다. **3) 공간복잡도** 256mb **4) 풀면서 놓쳤던점** 딱히 없다!!- **5) 이 문제를 통해 얻어갈 것** 플로이드 워셜이 무엇인지/ 어떻게 풀어야하는지에 대한 감 import java.io.*; import java.util.*; public class Main { static int infinite = 200000000; public static void main(String[] args) throws IOExce.. 2023. 11. 2. 이전 1 2 3 4 5 6 ··· 19 다음