목록2024/03 (4)
delpho
Think 1. 주어진 N의 범위를 보고, 일반적인 순열 알고리즘으로는 시간초과가 나겠다는 생각을 했다. 2. 문제풀이 아이디어가 떠오르지 않아 https://nanyoungkim.tistory.com/233를 참고했다. 3. 순열의 경우의 수 = 팩토리얼인 사실을 활용한 풀이방식이다. 범위만큼의 팩토리얼을 미리 초기화하고, k에 순열 경우의수를 빼면서 값을 찾거나, 순열 값 이전까지 탐색하면서 k의 값을 구하는 방식이 되게 인상깊었다. 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class test { static int N..
Think 1. 하 DP.... 정말 어렵다 문제에 주어진 조건을 성립하면서 DP로 푸려는 아이디어가 어려웠다. 2. https://st-lab.tistory.com/132 를 참고했다. 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class test { static int n; static int sequence[]; static Integer dp[]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); stat..
Think 1. LIS인 이 문제를 보고 고민해보았으나, 풀이 접근 방법이 떠오르지 않음 (이걸 dp로 어떻게 풀지..? 라는 생각) 2. https://st-lab.tistory.com/137 를 참고하여 풀이 방법을 공부함 3. 현재 수열 기준으로 이전 값들을 탐색하며 이전 값이 더 작다면 해당 인덱스의 dp 값 + 1과 현재 dp값을 비교하여 최대값을 저장해준다 4. 해당 풀이법은 시간복잡도가 N^2라고 하며, 이분탐색을 활용하면 NlogN까지 가능하다고 함 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public..
Think 1. 점화식을 잘못 찾아서 틀렸다. 2. https://yinq.tistory.com/68 를 참고하여 풀었다. 3. 예제를 활용하여 점화식을 검토하는 방법이 있다. 4. 문제를 여러 개 풀면서 여러 점화식을 접해보자. 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n; static Integer dp[]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringT..