목록알고리즘 (31)
delpho
Think 처음에는 벽 위치를 저장해두고, 하나씩 벽을 없애면서 모든 경우의 수를 dfs 했다. 그런데… 알고보니 시간복잡도가 NM^2였다. https://kscodebase.tistory.com/66를 참고했다. int[][][] isVisited를 활용하여, 벽을 뿌신 경우와 안뿌신 경우를 구분해서 관리할 수 있었다. DFS는 가중치가 없을 경우(다익스트라를 사용하지않아도 되는 경우), 무조건 최단거리를 보장한다. 또한, Queue 특성상, 벽을 뚫고 가는 경우와 안뚫고 돌아가는 경우 모두 체크가 가능하다 이 개념이 이 문제를 푸는 아이디어를 이해하는데에 중요한 포인트라고 생각한다 왜냐면…. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에..
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..