HwangHub

🤔 Intuition 체감상 어려워서 답을 참고했다. 막상 답을 보면 "간단하네..." 하는 문제를 마주하면 현타가 좀 오는데, 이번 문제도 그러했다. counting array를 운영하는 부분수열 유형이므로 투포인터로 해결할 수 있음은 명료하다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) * @memory O(N) 👨🏻‍💻 Logic 직관적이면서 가장 빠른 풀이는 maxEnd와 minEnd를 운영하는 것이다. (3 ms) right pointer를 +1씩 옮겨가면서 정확히 K개의 distinct elements로 구성된 가장 작은 subarray를 먼저 찾고, (right=minEnd) righter pointer를 그 상황에서 di..

🤔 Intuition 특정 element의 개수를 세가면서 부분수열의 개수를 구하는 문제이므로 투포인터 문제임을 알 수 있다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) : 10ms * @memory O(N) : 61.12 MB 👨🏻‍💻 Logic 중요 포인트는, right를 증가시키다가, max element가 k번 등장하는 경우에 "nums의 총 길이 - right의 index"를 연산하여 "max element가 k번 보다 더 많이 등장하는 경우의 수"를 단 한번의 연산으로 구해내는 작업이었다. 이를 통해 추가적인 포인터 이동 연산 없이 O(N)으로 문제를 해결할 수 있었다. public class LeetCode_2962 { /..

🤔 Intuition 명료하게 counting array를 이용하는 two pointer 문제이다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) : two pointer -> 449 ms * @memory O(N) : 42 MB 👨🏻‍💻 Logic 탐색할 때, 정답 갱신 조건과 탐색 종료 조건을 설정해주는 게 그나마 있는 출제 의도로 느껴졌다. 사실 체감상 단순 투포인터 템플릿을 이용하는 문제였다. public class CodeTree_1이k개이상존재하는부분수열 { private static int[] arr; private static int[] cntarr = new int[3]; public static void main(Stri..

🤔 Intuition 스택 문제인게 느껴졌는데 커서 관리를 어떻게 할까 고민했다. 근데 동작이 왼쪽 오른쪽 백스페이스 뿐이라, 스택을 두개 쓰면 N번 루프를 한번만 돌면서 중간 지점에 커서를 유지하고, 요구 연산을 O(1) 로 수행할 수 있겠다 판단했다. 🔎 Algorithm & Complexity * @algorithm stack * @time O(N) -> 1144 ms * @memory O(N) -> 311176 KB 👨🏻‍💻 Logic 단순하다. 커서 움직임에 따라 문자를 왼쪽 오른쪽 스택으로 옮겨주면 된다. 코드가 간단해서 보면 다들 이해가 쉬울 것이다. public class BOJ_5397_키로거 { private static int N; private static StringBuilder ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🤔 Intuition 직관적으로 떠오른 풀이는 누적합을 이용한 슬라이딩 윈도우였다. 구간의 사이즈가 고정되어있기 때문이다. 하지만 역시나 슬라이딩 윈도우는 투포인터로도 풀 수 있다. 두 알고리즘 모두 알고리즘 자체 시간복잡도는 O(N) 일 테니 소요 시간은 비슷할 것으로 예상했다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) -> 729 ms * @memory O(N) -> 38 MB * @algorithm prefix sum * @ti..

🤔 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..

상황은 이랬다.싸피 내 데스크탑을 이용하고 있었다.데스크탑 자리는 주기적으로 변경된다.나는 지난번엔 분명 이 PC에서 git을 이용했다.사용하고 있는 git repo 플랫폼은 git lab이다.어느날 갑자기 remote repository에 git을 이용하여 clone과 push를 하는 작업을 하려고 하면 위와 같은 에러가 발생했다.심지어 내 개인 repo에 push하는 것도 실행되지 않았다...(이 지점에서 무언가 단단히 잘못됨을 느낌) project 경로는 copy & paste로 입력한 거라서 잘못되었을 수 없다고 판단했다.그렇다면 권한이 문제라는 가정을 한 채로, ssh key나 access token이 만료되었나 체크해봤다. 아쉽게도 만료되어서 발생하는 문제는 아니였다. (물..

🤔 Intuition * 그래프를 활용할 것이라는 건 명확했지만, 위상정렬을 잘 몰라서 유니온 파인드로 접근하다가 데였다. * 정렬을 어떻게 하지? 하는 생각을 바탕으로 유니온 파인드만 써서 지저분하게 풀다가 "이거 안되는건가?" 하고 알아봤는데 위상정렬이었다. * 위상정렬이라는 유형이 존재하며, inDegree를 이용한 알고리즘을 한번 학습한 적은 있었지만 체화가 안되어있었다. * 최빈출 유형은 아니지만, 그래도 기왕 보게 된 김에 알아두자. * 알고보니 위상정렬 대표유형 문제... 어쩐지 정답률이 높더라 🔎 Algorithm & Complexity * @algorithm topological sort * @time O(N + M) ; indegree활용 위상정렬 - 노드개수 N, 간선개수 M -> 5..