HwangHub

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

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

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 Intuition 처음에는 DP라고 생각했다. 근데 아니였다. DP가 성립하려면 2가지 조건을 성립해야 한다. 부분 반복 문제 (Overlapping subproblem) : 어떤 문제가 부분 문제로 쪼개질 수 있는지 최적 부분 구조 (optimal substructure) : 부분 문제에서 구한 최적의 답이, 원래 문제의 최적의 답과 동일한지 이 문제를 통해 위 조건을 검토해보자면, 부분 반복은 된다. 왼쪽으로 한칸, 오..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🤔 Intuition 주어지는 숫자의 범위가 넓으므로 해시맵을 활용하여 좌표를 압축해야 할 것으로 봤다. 두 수의 합이 k가 되는가를 구하기 위해서는 각 숫자의 개수끼리 곱해주고, 동일한 숫자에 대하여는 조합 공식을 이용하여 개수를 구해줬다. 🔎 Algorithm & Complexity * @algorithm hash-map * @time O(N) : 키 개수만큼 순회 * @memory O(N) : 키-값 쌍 개수 👨🏻‍💻 Logic 1. 각 숫자별로 몇 개씩 존재하는지 hashmap에 저장 2. key..

Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 🤔 Intuition 그래프 탐색 기법을 이용한 완탐으로 보였다. 다만, 움직이는 과정에서 현재 자율주행 차량의 진행방향을 기억해두고, 진행 가능 여부를 판단할 때 이용해야 한다는 점만 고려하면 된다. 진행 방향을 고려하기 위해 mod 4를 한 값이 0 ,1 , 2 , 3 단위로 움직일 수 있도록 -1 해서 각 방향들을 받아주었다. 그리고 방문 여부는 점수 중복 계산을 방지하기 위해서만 사용하였다. 단순한 문제인데, 괜히 문제가 길어서 피곤하게 만듦으로써 사람을 쫄게 하는 문제이다. 🔎 Algorithm & Complexity * @algorithm BFS * @time O(N^2) : 그래프 완탐 * @memory O(N^2) : 배..

🤔 Intuition BFS를 이용한 완탐으로 보였다. 귀신이 남우를 따라잡는 여부를 어떻게 알 수 있나 기준을 잡는 게 중요했는데, 귀신이 남우보다 먼저 목적지에 갈 수 있는 경우에는 무조건 귀신이 남우를 따라잡을 수 있는 것으로 봤다. 여기서 고민을 했던 부분은 최악의 경우 10^6 개의 귀신을 가질 텐데, 이들이 모두 BFS를 돌면 시간을 쉬이 초과할 것이다. 따라서 탐색을 할 귀신을 선정하는 게 중요한데, 나는 도착지와 맨해튼 거리가 가장 가까운 귀신만 검사해줬다. 어차피 가장 가까운 귀신의 이동 거리만 필요하기 때문이다. (솔직히 처음에 제출할 때에는, "에이 그래도 이게 뻑이 안나도록 문제를 줬을거야 누가봐도 BFS 문제인데?" 라는 아주아주 안일한 생각을 했다. 결론은, 문제에서 단순 완탐이..