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

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

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

🤔 Intuition 시뮬레이션 문제인 것은 확실하나, 탐색을 어떻게 할지 고민하였다. 우선되는 먹이의 조건이 (1) 거리가 가까울 것 (2) row가 작을 것 (3) column이 작을 것 이었으므로 델타탐색을 "상 좌 우 하" 로 하면서 가장 먼저 나오는 먹이를 낼름 먹어버리면 될 것으로 봤다. 하지만 위는 틀렸다. 위의 경우에는 항상 거리값이 가장 가까운 먹이를 찾을 수 있지만, 바로 만난 먹이가 가장 위에 있고, 가장 왼쪽에 있다는 것을 보장할 수 없다. 아래 예시를 보면 이해가 가능하다. private static int[] dy = {-1, 0, 0, 1}; private static int[] dx = {0, -1, 1, 0}; . . 1 . . . 2 x 3 . 4 x C x 6 . 5 x..

🤔 Intuition 처음에 완탐인 줄 알았다. N과 M이 50 이하이고 시간제한이 2초 이내라서 거의 확신을 했다. 근데, 일단 TC만 맞고 나서, 제출하니까 3%에서 바로 틀렸다. (실전이였다면 맞았다고 착각해서 틀렸을 확률 99.9%) 진실을 아는 사람들이 있는 파티에 참여하는 사람들도 진실을 알게 되는데, 이게 1다리만 계산하면 되는 게 아니라 엮이는 사람 간의 관계 모양이 skewed tree가 될 경우에는 반복수를 감안할 수 없기 때문에 브루트포스로는 반복수의 기준이 명확하지 않다. 즉, 관계성을 계속 저장해둬야 하는 문제였던 거다. 이는 사람간의 그래프를 형성하는 문제라고 볼 수 있으므로, union find로 풀어낼 수 있다. 🔎 Algorithm & Complexity * @algorit..

문제 링크 해석 공유기를 설치하는 거리를 x라고 할 때, x를 이분 탐색으로 구하여 답을 도출할 수 있다. 답을 가정할 때, 특정 구간에서는 해당 답이 거짓이고, 특정 구간에서는 해당 답이 참일 수 있는 경우에는 이분탐색을 통한 답 도출을 하는 "parametric search"를 활용할 수 있다. 이 문제는 공유기 설치를 어느 거리로 해야 최대 거리로 설치할 수 있는지 묻는 문제로, parametric search 문제 중 대표 유형인 "칸막이 설치" 유형이라고 할 수 있다. 로직 기본적으로 이분탐색을 통해 찾는 값이 "가장 가까운 라우터끼리의 거리"이다. 라우터 좌표를 배열에 저장하고 정렬한다. 배열을 순회하면서 누적 거리를 재고, 이분탐색을 통해 설정한 '기준 거리'를 넘어갈 때 routerCnt를..

문제 문제 링크 해석 그리디는 "언제나 최선"인 경우라는 기준이 존재하여, 그 기준을 바탕으로 차례대로 선택하는 것이 가능할 때, 정렬이나 특정 연산을 통해 전체 연산을 최적화하는 알고리즘이다. 이 문제는 그리디 알고리즘 개념학습 마지막 문제이며, 이를 해결하기 위해서는 직관적으로 알 수 있듯 "가장 앞의 숫자가 큰 숫자를 먼저 고른다." 가 첫 번째 기준이 되어야 한다. 그리고 두 번째 조건이 중요한데, "가장 앞자리의 숫자가 동일할 경우, 두 세 번째 숫자도 체크해야 한다."는 게 고려되어야 한다. 즉, 결국 모든 숫자를 체크해야만 할 것 같은 느낌이 든다. 하지만 이를 잘 생각해보면, 일단 앞 자리 기준으로 큰 숫자를 먼저 앞으로 배치하되, 만약 앞자리가 같다면 직접 붙여봐서 더 큰 경우가 될 때의..