HwangHub

🤔 Intuition * @intuition 사전순 출력이라는 말에서 완탐 느낌이 났지만, 시간초과가 날까 고민했다. 근데 시간 복잡도 계산해보니 충분할 것 같아서 백트래킹으로 구현했다. 🔎 Algorithm & Complexity * @algorithm backtracking * @time O(9 * N^2) 최대 N^2개의 빈칸에 대하여 9개씩의 경우를 배치 -> 368 ms * @memory O(N^2) N^2의 맵 운영 -> 16388 KB 👨🏻‍💻 Logic public class BOJ_2239_스도쿠 { private static int[] rowFlag = new int[10]; // 1 ~ 9번째 row에 대하여 고른 숫자 선택 private static int[] colFlag = ne..

🤔 Intuition 어려웠다. 자력으론 못풀었다. 해석을 참고했다. 이 문제는 조합 공식 아이디어를 DP 로직에 적용해보는 게 첫 번째였다. 근데 이게 다가 아니였다. 가장 중요했던 건, 기본적으로 DP 배열을 채워넣을 때와 정답을 뽑을 때에 사용되는 점화식을 다르게 세워야 한다는 것이었다. 처음에 DP 배열을 기록할 때에는 마치 색상환이 원형 구조가 아니라 선형 구조인 것처럼 고려해야 한다. 이제부터 이게 무슨 말인지 설명하겠다. 이 문제는 i번째 인덱스의 색상을 골랐을 때 i-1번째와 i+1번째를 선택하지 않아야 하는데, 이를 고려하는 점화식은 다음과 같다. DP[N][K] = DP[N-3][K-1] + DP[N-1][K]; N개의 숫자 중 K개를 고르는 경우의 수를 구하기 위해서, DP[N-3][..

🤔 Intuition 투포인터를 아직도 제대로 못 하는 것 같아서 트레이닝을 위해 개념 문제를 풀었다. 투포인터 문제인지 알고 접근했다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) : 선형탐색 * @memory O(N + R) : 주어지는 숫자 개수 N + 주어지는 숫자 범위 R 👨🏻‍💻 Logic 입력되는 숫자 배열을 운영함과 동시에, 숫자들의 등장 횟수를 저장하는 count array를 운영하면 투포인터를 진행하는 과정에서 숫자의 중복 여부 또는 숫자의 등장 횟수를 O(1)로 관리할 수 있다. 이를 이용하여 투포인터를 운영하면 된다. public class Main { private static int N; private stati..