HwangHub

🤔 Intuition // 맨 아래의 어떤 숫자를 고르고 그 숫자에 따라 연쇄적으로 나머지 주사위들의 숫자를 지운 뒤 최대값의 합을 출력 // 시간제한이 최대 2초이므로 완탐을 노리고 있는 것으로 보인다. 🔎 Algorithm & Complexity * @algorithm brute-force * @time O(D^2 * N) : 처음 주사위의 윗면 고르기 D * N개의 주사위 순회 * 각 주사위 정해진 윗면 찾기 D -> 428 ms * @memory O(N*D) : N개의 주사위 면 정보 저장 배열 -> 41928 KB * D : 주사위 면 개수(=6), N : 주사위 개수 👨🏻‍💻 Logic // 주사위들을 배열로 저장해둔다. // 첫 번째 주사위의 선택 숫자를 6으로 순회한다. (이는 윗 면을 어..

🤔 Intuition 새 과제가 오면 stash 해두고 나중에 시간 남을떄마다 꺼내보는 구조이므로 stack 문제겠다. 정답률이 낮아서 조금 쫄았지만, 별거 없는 문제였다. 백준에서 유사한 문제를 풀어봤었기에 접근이 어렵지 않았다. 🔎 Algorithm & Complexity * @algorithm stack * @time O(N logN) : 배열 정렬 O(N logN) * for loop iteration O(N) * stack 비우기 O(N) * @memory O(N) : plans가 2차원 배열이지만 이는 입력배열이라 제외, 그 외 stack 및 answer 는 최악의 경우 O(N) 👨🏻‍💻 Logic 하라는 대로 하면 된다. 아래 과정이 반복되면서 정답 배열을 채워나간다. 과제가 시작시간 순으로..

🤔 Intuition 백트래킹을 학습할 때 주로 다루는 대표 문제임을 이미 알고 접근하긴 했으나, N이 작은 편이므로 완탐을 우선적으로 고려해볼 만 하다는 점은 분명해 보인다. Queen을 둬보면서 탐색하고, n개의 퀸을 조건에 맞게 배치하는 경우의 수를 모두 탐색하는 건 둬보고, 회귀하여 다시 둬보는 백트래킹으로 가능할 것으로 봤다. 개인적으로 생각하기에 이 문제를 푸는 중요 포인트는, 배열을 board 배열을 2차원으로 관리하겠다는 게 사람 입장에서의 관점인데, 항상 1개의 행에 1개의 퀸만 둘 수 있다는 건 자명하므로 이를 1차원으로 운영할 수 있겠다는 아이디어를 캐치하는 것이다. 이 문제를 두 번째 푸는 건데도, 처음에는 2차원으로 접근했었다... 아직도 N-Queen 문제가 내 것이 되지 않은 ..

🤔 Intuition 딱 봐도 단순 구현으로 보였다. 시간복잡도가 들어오는지 계산해봤는데, 시간제한이 2초인 데다가 1초 이내로도 충분히 끊어낼 것으로 봐서 단순 구현으로 풀었다. 🔎 Algorithm & Complexity * @algorithm implementation * @time O(N*M*K*R*C) : 노트북 위 탐색기준좌표 O(N*M) * 스티커 개수 O(K) * 스티커 크기만큼 탐색 O(R*C) -> 188ms * @memory O(N*M + R*C) : 노트북 배열 O(N*M) + 스티커 배열 (R*C) -> 16204 KB 👨🏻‍💻 Logic 하라는 대로 하면 된다. 1. 스티커를 입력받고 2. 노트북에 스티커를 붙일 수 있는지 체크하고 (조건에 따라 좌상부터 우하 방향으로 진행) 3..

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

🤔 Intuition 바라는 게 많은 시뮬레이션 문제. 길을 잃지 않도록 변수명을 잘 선언하고, 로직을 잘 구성한 뒤 코드를 작성해야 할듯. 탐색은 정직하게 달팽이탐색으로 구현할 것. pull 또는 stretch 과정에서 temp 배열 인덱스를 복잡하게 운영하는 것보다는 1차원으로 차곡차곡 쌓아두고, 이를 고대로 다시 달팽이탐색으로 복붙하는게 편할 듯 연속되는 구슬을 터뜨리기 위해 좌표를 저장하는 건, 나중에 길이를 체크하고 되돌아가서 하나하나 터뜨리는 논리이므로 stack 자료구조가 적절할 듯 🔎 Algorithm & Complexity Algorithm : 시뮬레이션 시간복잡도 : O(N^4) : N^2 탐색 X 최악의 경우 stack에 N*N개 채워진 상태로 뒤로감기 → 480 ms 공간복잡도 : ..

🤔 Intuition 첫 인상에서 그리디/Meeting-room-problem과 유사해보였습니다. 그리디로 선택을 한다고 할 때, 예외가 있는지 고민해봤는데 결국 널빤지를 최소한으로 깔아야 하니 최대한 길게 배치하는게 좋다는 건 자명하면서, 널빤지 영역을 빠짐없이 커버해야 하니까 결국 시작점을 기준으로 그리디하게 배치하면 문제 없겠다 싶었습니다. 다만, 하나의 널빤지로 두 웅덩이를 커버할 경우, 이를 체크할 수 있냐 없냐가 포인트였던 것 같고, 저는 이걸 마지막으로 널빤지를 두었던 좌표 +1 좌표(다음 널빤지를 놓기 시작할 위치) int lastIdx라는 변수로 저장하여 이를 기준으로 다음 웅덩이의 시작점 int s와 끝점 int e를 이용해 if 분기로 검사해 주었습니다. 이 과정에서 널빤지 개수가 좌..

🤔 INTUITION 그냥 중력 시뮬 문제로 이해했습니다. 다만, 합쳐진 숫자였는지 여부 체크를 곁들인... 중력 적용 중 숫자가 동일할 경우 merge 연산이 수행되어야 하는데, 이게 연속적으로 발생할 수 없다는 게 이 문제의 유일한 포인트로 보였습니다. merge 연산 여부를 체크하는 걸 어떻게 할까 하다가, 저는 int 범위 이상의 숫자를 merge 연산 결과에 더해줘서 그 이후로는 이 숫자가 그 어떤 숫자와도 일치하지 않도록 해서 중복 연산되지 않도록 처리해 줬습니다. 이는 다시 배열을 업데이트 할 때 mod 연산으로 제거해 줬습니다. ✅ ALGORITHM 시뮬레이션 map을 저장합니다. int[] temp 를 이용하여 한 줄 한 줄 중력을 적용해 줍니다. 만약, 숫자가 합쳐지는 경우에는 10^1..

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

문제 링크 해석 이 문제는 조합과 그래프 탐색을 조합하여 푸는게 일반적인 방식이다. 하지만 유니온파인드로 풀어보라고 제안을 받아서 이를 이용하여 "부분집합 + 유니온파인드"로 풀었다. 정점의 개수가 N, 간선의 개수가 E라고 할 때, 유니온파인드 시간복잡도가 O(E * log N)이고, 부분집합의 시간복잡도가 선택하냐 마냐이므로 O(2^N)이다. 따라서 내가 구성한 로직은 O(2^N * E) 인데, 10! 이 약 4백만이고, N이 10까지이므로 1초 내로 구성할 수 있을 것으로 판단했다. 풀이 코드가 길고 지저분해서, 만약 코드를 보고자 하는 분은 흐름을 먼저 체크해주시길 바란다. /* * 1. 부분집합을 구한다. * * 2. 구해진 부분집합을 기준으로 선거구로 가능한지 체크한다. * -> adj 리스트..