반응형 알고리즘21 QuickSort 정리 목표 QuickSort 알고리즘 이해 QuickSort 알고리즘을 자바스크립트로 구현 QuickSort 특징 이해 QuickSort 시간복잡도 이해 QuickSort 알고리즘 개념 불안정 정렬이며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬이다. 정렬 속도가 매우 빠르다. 분할 정복 알고리즘이다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 결과들을 모아서 원래의 문제를 해결하는 전략 리스트를 두개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 부분 리스트를 다시 합하여 전체가 정렬되도록 하는 방법 분할(Divide) : 입력 배열(arr)을 arr[0](pivot)을 기준으로 비균등 하게 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. .. 2021. 10. 17. 알고리즘 20 : Binary Heap(Max) BinaryHeap 배열의 최대값, 최솟값을 찾아내는 메소드는 다음과 같다. Math.max(...arr) Math.min(...arr) 위 메소드들은 배열의 모든 요소를 순회한다. 이는 배열의 길이가 길때 연산시간이 오래걸린다는 단점이 있다. BinaryHeap은 시간복잡도를 줄이면서 최대값, 최솟값을 빠르게 찾아내기 위한 자료구조 알고리즘이다. 이진 힙에서 부모 노드의 값이 자식 노드의 값보다 큰 경우를 최대 힙(max heap), 반대의 경우를 최소 힙(min heap)이라고 한다. (이진 트리이므로 자식노드는 2개이다.) 문제 정수를 요소로 갖는 배열을 입력받아 이진 힙(binary heap)*을 리턴해야 합니다. 이진 힙(binary heap)은 노드의 값이 특정한 순서를 가지고 있는 완전 이진.. 2021. 10. 14. 알고리즘 19 : robotPath 문제 세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다. 입력 인자 1 : room 배열을 요소로 갖는 배열 room.length는 M room[i]는 number 타입을 요소로 갖는 배열 room[i].length는 N room[i][j]는 세로로 i, 가로로 j인 지점의 정보를 의미 room[i][j]는 0 또는 1 인자 2 : src number 타입을 요소로 갖는 배열 src.length는 2 src[i]는 0 이상의 정수 src.. 2021. 10. 13. 알고리즘 13-2 : spiralTraversal,배열 나선형으로 순회 https://wnsdufdl.tistory.com/142 알고리즘 13 : spiralTraversal, 배열 나선형으로 순회 문제 2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다. 입력 인자 1 : matrix 세로 길이(matrix.length)가 M, 가로 길이(matrix[i].length)가 N인 2차원 배열 matrix[i]는 string 타입을 요소로 갖는 배.. wnsdufdl.tistory.com 저번에 올린 알고리즘은 일일히 배열을 수작업으로 순회하는 알고리즘이었다. 이번엔 레퍼런스코드를 보고 자동화된 알고리즘을 익혔다. spiralTraversal 문제 2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다. 입력 인자 1 : matrix 세로 길이(ma.. 2021. 10. 13. 이전 1 2 3 4 ··· 6 다음 반응형
