Keep it Real

머지 소트 구현! 이전부터 공부해보고 싶었던 알고리즘인데 마침 해커랭크 문제가 있어서 구현해봤습니다. 어려워 보일 수도 있으나 원리만 정확히 이해하면 누구나 충분히 구현 할 수 있을 것 같습니다. 소트나 검색 알고리즘에서 항상 트리를 이용하기 때문에 트리 검색이나 소트 할 때 가장 최적화된 방식으로 하는 걸 공부하고 고민하면서 머지 소트에 대한 이해도를 높이는 것도 도움이 될 것 같습니다. 다음엔 대부분의 라이브러리에서 소트된 키-밸류 컨테이너를 구현할 때 사용하는 레드 블랙 트리를 직접 구현해보고 싶네요 👻 struct MergeArray { vector left; vector right; }; shared_ptr Split(const vector& arr) { MergeArray mergeArray;..

링크 https://www.hackerrank.com/challenges/find-the-nearest-clone/ 코드 int findShortest(int graph_nodes, vector graph_from, vector graph_to, vector ids, int val) { //vector links(graph_nodes + 1, vector()); map links; for (int index = 0; index < graph_from.size(); ++index) { int fromNum = graph_from[index]; int toNum = graph_to[index]; links[fromNum].push_back(toNum); links[toNum].push_back(fromNum..

문제 링크 - https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem 코드 int maxRegion(vector grid) { int length = grid[0].size(); int height = grid.size(); vector heightsVisited(length, false); vector visited(height, move(heightsVisited)); using IntPair = pair; queue findQueue; int maxCount = 0; for (int y = 0; y < height; ++y) { vector arr = grid[y]; bool bFound = false; int coun..

vector bfs(int n, int m, vector arr, int start) { vector answer(n, -1); vector visited(n + 1, false); vector numLinks(n + 1); for (auto nums : arr) { vector linkArr; int firstNum = nums[0]; int secondNum = nums[1]; numLinks[firstNum].push_back(secondNum); numLinks[secondNum].push_back(firstNum); } queue numQueue; int weight = 0; numQueue.push(start); answer[start - 1] = weight; while (true) { if..

링크 : https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/start/ 풀이 : Max Slice 의 또 다른 변형 문제이다. 이 알고리즘의 핵심은 최선의 값을 얻을 수 있는 조건이 되는 값(minPrice)을 찾아내는 것이다. 그리고 현재의 최선의 값과 지금까지의 최선의 값을 max 로 비교하여 최종적인 최선의 값을 얻어내는 방식인 것 같다. int solution(vector& arr) { if (arr.size() == 0) { return 0; } int maxProfit = 0; int minPrice = arr[0]; for (int index = 1; index < arr.size(); ++index..

링크 : https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/ Max Slice 알고리즘 설명 : https://haewoneee.tistory.com/161 기존 max slice 알고리즘에서 약간 변형해서 풀어야 한다. 모든 slice 의 합이 음수여도 0이 아닌 음수를 반환하도록 변형해야 한다. int solution(vector& arr) { int maxEnding = 0; int maxSlice = arr[0]; for (int index = 0; index < arr.size(); ++index) { int currentNum = arr[index]; maxSlice = max(maxSlice, ..

링크 : https://app.codility.com/programmers/lessons/8-leader/equi_leader/ 풀고 나서 이게 쉬움이라고??? 했던 문제 🤔🤔🤔 우선 Equi 리더를 만족 시키려면 원본 배열에 무조건 leader 숫자가 있어야 하고, 해당 숫자가 Equi 리더 배열에서도 leader 숫자일 것이다. 원본 배열의 leader 숫자가 아니였던 숫자는 equi leader 배열의 leader 숫자가 될 수 없을 것이다. 해당 가정으로 먼저 원본 배열에서 leader 숫자와 leader 숫자의 index 들을 찾아낸다. 그 다음 equi leader 을 찾아내기 위해 원본 배열을 순회한다. 인덱스 기준으로 배열을 두 개로 나눈 뒤에, 아까 찾았던 leader 숫자의 index ..

링크 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/ 내 풀이 : 맨 처음 시도에는 이중 for문을 돌면서 검사했더니 시간 초과가 났다. 두 번째 시도는 1 을 가진 인덱스를 다른 배열에 저장해두고 0을 가진 인덱스와 비교하여 1을 가진 인덱스가 더 크면 (다른 배열의 크기 - 1을 가진 인덱스) 의 값을 최종 값에 더했다. 하지만 비교하는 다른 배열의 크기가 커서 그런지 시간 초과가 났다. 세 번째 시도는 0 을 가진 인덱스 배열을 추가로 선언해 불필요한 연산을 줄였다. 그리고 0의 인덱스와 1의 인덱스를 비교했을 때 1의 인덱스가 더 작으면, 1을 가진 인덱스 배열에서 해당 값을 지움으로써 비교 연산을 줄였다. 시간..

문제 링크 : https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/ 내 풀이 : 숫자가 있는지 없는지 판별하기 위해 다른 카운트 배열 하나를 선언하고, 배열을 순회하면서 숫자가 있으면 카운트를 올린다(인덱스가 숫자를 나타낸다). 다시 카운트 배열을 순회하면서 값이 0인 인덱스를 찾는다. 해당 인덱스에 들어있는 값이 0인 숫자가 배열에 없는 것이다. 인덱스가 숫자를 나타내므로 인덱스 숫자를 반환한다. 시간복잡도 는 O(2N) 이다. int solution(vector& A) { // Implement your solution here vector numCount(A.size() + 2, 0); for (auto n..

문제 링크 : https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 내 풀이 : 소팅한 뒤에 숫자의 갯수를 카운팅한다. 숫자가 달라질 때 카운팅 한 갯수가 홀수면은 짝이 없는 걸로 판별하고 해당 숫자를 반환한다. 배열의 끝까지 검색했다면 마지막 숫자가 짝이 없는 숫자이므로 마지막 숫자를 반환한다. int solution(vector& A) { // Implement your solution here sort(A.begin(), A.end()); if (A.size() == 1) { return A[0]; } int count = 0; int unpairedNum = 0; int prevNum = 0; for (aut..