HwangHub

🤔 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 이 문제는 동시 탐색 결과를 구하는 코드를 구현할 수 있는가를 묻는 문제였다. 컴퓨터는 한번에 하나의 연산만을 수행하는 것이 기본이기 때문에, 이전 결과를 잘 저장해둬서 다음에 영향을 주게끔 구현해야 한다. 동시에 탐색하는 효과를 주기 위해 history라는 좌표 리스트를 운영하여, 이전 탐색에서 최선을 얻었던 값의 자취를 다음 탐색에 반영해주었다. 하지만 여기서 내가 놓쳤던 부분이 있다. 코드 상에서는 각 출발지가 모두 다르므로, 탐색이 시작되는 위치의 순서가 달라졌을 때 최선의 값이 달라질 수 있음을 고려해야 했다. 이를 고려해야 비로소 동시 탐색 결과를 알 수 있는 모든 케이스를 탐색할 수 있게 된다. 따라서 이는 순열을 접목하여 표현해 주었다. 🔎 Algorithm & Com..

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