HwangHub

🤔 Intuition아이디어를 떠올리기 어려워 결국 다른 이의 풀이를 참고했다. 요지는, 전체 부분수열을 부분집합 알고리즘으로 탐색하게 되면 (2 ^ 40) 정도라서 시간을 초과하지만, 이를 절반씩 쪼개서 부분집합을 구하면 (2 * 2 ^ 20) 이라서 시간이 터지지 않는다. 따라서 이를 절반으로 쪼개어 부분수열의 합을 구한 뒤, 한쪽 절반의 부분수열의 합을 기준으로 다른 반쪽의 부분수열의 합과 더한 값이 S가 될 때의 개수를 세주면 된다.🔎 Algorithm & Complexity * @algorithm backtracking (powerset)* @time O(2^N/2) : 976 ms* @memory O(N) : 96908 KB 👨🏻‍💻 Logic오른쪽 반 쪽의 부분수열의 합을 먼저 구..

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 🤔 Intuition 처음에는 그리디하게 풀 수 있을까 싶었지만, 예외가 있을 것으로 보였다. 그래서 주어진 조건을 보면서 백트래킹을 이용한 완탐으로 풀 수 있을 것으로 봤고, 다행히 추측이 맞았다. (근데 합리적으로 정확하게 계산을 못하겠다... 이 글을 보는 사람은 풀이의 도움을 얻으려는 사람 뿐이겠지만 누군가 백트래킹 시간복잡도 계산에 대하여 잘 안다면 좀 알려주세요....) 🔎 Algorithm & Complexity * @algorithm bac..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 Intuition 완전 아이디어 싸움인 문제라고 생각한다. 내 풀이는 2초 정도 걸리는 풀이인데, 어떤 사람은 300ms에 풀었더라. 방법이 여러가지일 것 같은데, 나는 거진 완탐 방식으로 푼 셈이다. 플로이드 워셜을 이용하여 각 노드 간 연결성을 앞뒤로 체크해줬다. 유향그래프이므로, 내 노드가 모든 노드를 타고 갈 수 있는지를 판별하면 된다. 여기서 포인트는 플로이드 워셜은 아닌데, 그냥 로직 간단하게 구성하려고 플로이드 워셜 썼다. 🔎 Algorithm & Complexity * @algorithm floyd warshall * @time O(V^3) : ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 Intuition 중복 순열을 사용해서 터뜨릴 벽돌을 선택하고, 터뜨리면 되는 문제다. 시뮬레이션 유형이라고 판단했다. 🔎 Algorithm & Complexity * @algorithm simulation * @time (W^4 * W * H) -> 211 ms * @memory (W * H) -> 98,464 kb 👨🏻‍💻 Logic 관건은, 중복 순열을 일반적인 permutation으로 구하면 시간이 터지므로 효율적으로 뽑아야 한다는 거다. 즉, 순열을 다 뽑아놓고 그것에 대하여 숫자를 계산하는 게 아니라, 각 숫자를 뽑으면서 그 때마다 시뮬레이션을 수행..

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