HwangHub

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 🤔 Intuition 시뮬레이션 문제인데, 1월부터 4월까지 오랜 기간에 걸쳐 총 3번의 시도 끝에 성공했다. 다시 도전해서 드디어 성공했다... 이 문제는 상어가 움직이는 걸 수식으로 구현하는 게 포인트이다. (이걸 그냥 단순 반복으로 한칸한칸 움직이게 구현하면 시간초과 발생, 근데 또 수식으로 구현하려니 머리 아픔) 옛날에는 애초에 시뮬레이션 문제를 잘 못풀었고, 2트 째에는 수식 완성을 못했다. 그리고 3트 째에 드디어 풀었다... 🔎 A..

4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🤔 Intuition 가중치가 있는 그래프 상에서, 가중치의 합이 최소가 되는 경로를 구하는 문제이므로 전형적인 다익스트라 문제이다. 다익스트라 기본 유형 연습용 문제로 보인다. 다익스트라 구현을 할 때 인접 행렬, 인접 리스트 두 가지 버전이 있으므로 두 가지로 풀어봤다. 🔎 Algorithm & Complexity * @algorithm dijkstra * @time1 O(E * logV) ; 인접리스트+우선순위큐 -> 264 ms * @t..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 Intuition 수학? 아이디어? 문제다. 이 문제의 아이디어는, 주어진 점들의 맨해튼 거리가 짝수로만 or 홀수로만 이어져 있는 경우에만 이동이 가능하다. 맨해튼 거리가 가장 큰 숫자가 들어올 수 있으면 다른 점은 알아서 들어온다. 따라서 원점으로부터의 거리가 짝수로만/홀수로만 주어지는 점들에 대하여, 가장 먼 점을 몇 번 만에 원점으로 끌어올 수 있는지만 고려하면 된다. 🔎 Algorithm & Complexity * @algorithm math * @time O(N) -> 265 ms * @memory O(1) -> 51,712 kb 👨🏻‍💻 Logic..

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