HwangHub

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

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🤔 Intuition 주어지는 숫자의 범위가 넓으므로 해시맵을 활용하여 좌표를 압축해야 할 것으로 봤다. 두 수의 합이 k가 되는가를 구하기 위해서는 각 숫자의 개수끼리 곱해주고, 동일한 숫자에 대하여는 조합 공식을 이용하여 개수를 구해줬다. 🔎 Algorithm & Complexity * @algorithm hash-map * @time O(N) : 키 개수만큼 순회 * @memory O(N) : 키-값 쌍 개수 👨🏻‍💻 Logic 1. 각 숫자별로 몇 개씩 존재하는지 hashmap에 저장 2. key..

Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 🤔 Intuition 그래프 탐색 기법을 이용한 완탐으로 보였다. 다만, 움직이는 과정에서 현재 자율주행 차량의 진행방향을 기억해두고, 진행 가능 여부를 판단할 때 이용해야 한다는 점만 고려하면 된다. 진행 방향을 고려하기 위해 mod 4를 한 값이 0 ,1 , 2 , 3 단위로 움직일 수 있도록 -1 해서 각 방향들을 받아주었다. 그리고 방문 여부는 점수 중복 계산을 방지하기 위해서만 사용하였다. 단순한 문제인데, 괜히 문제가 길어서 피곤하게 만듦으로써 사람을 쫄게 하는 문제이다. 🔎 Algorithm & Complexity * @algorithm BFS * @time O(N^2) : 그래프 완탐 * @memory O(N^2) : 배..

커뮤니티 서비스는 likelion univeristy 서비스의 핵심 기능 중 하나이다. 유저들에게 가치를 전달할 수 있는 핵심 도메인이다. 즉, 서비스의 성공의 선두에 커뮤니티 서비스가 제공되어야 한다. 그럼에도, 현재는 쿼리 하나하나를 무겁게 실행하고 있어 데이터가 조금만 많아져도 서버가 많은 부담을 느끼고 있다. 이를 확인하고자 먼저 테스트 데이터를 강제로 늘려보았다. 운영 DB를 mysql로 사용하고 있기 때문에 이와 최대한 근사한 환경을 구축하고자 로컬 test db로 mysql로 구성하였다. 테스트용 더미데이터 입력을 위해 프로시저를 제작하여 등록하여 호출을 통해 데이터 복제를 수행하였다. CREATE DEFINER=`likelion`@`localhost` PROCEDURE `InsertMill..

🤔 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 이 문제는 동시 탐색 결과를 구하는 코드를 구현할 수 있는가를 묻는 문제였다. 컴퓨터는 한번에 하나의 연산만을 수행하는 것이 기본이기 때문에, 이전 결과를 잘 저장해둬서 다음에 영향을 주게끔 구현해야 한다. 동시에 탐색하는 효과를 주기 위해 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 문제가 내 것이 되지 않은 ..