Jveloper

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 Tree { value: 0, children: [ Tree { value: 1, children: [Array] }, Tree { value: 2, children: [Array] } ] } // 들어오는 형태 1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 2. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것 3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 선택함 Tree.prototype.BFSelect = function(filter) { let result = []; let queue = []; let nextNode; queue.push..

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 Tree { value: 1, children: [ Tree { value: 2, children: [Array] }, Tree { value: 3, children: [Array] } ] } // 들어오는 형태 1 2 3 4 5 6 7 1. filter(callback..

O(N^2) Sort 버블 정렬(Bubble Sort) 시간복잡도는 거의 모든 상황에서 최악의 성능을 보여준다. 만들기 쉽고 직관적일 뿐 되도록이면 쓰지 말아야 할 정렬. 단 예외적으로 이미 정렬된 자료는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다. 선택 정렬(Selection Sort) 버블 정렬이 비교하고 바로 바꿔 넣는걸 반복한다면, 선택 정렬은 모든 요소를 훑어서 가장 작은 요소를 골라내는 방식을 n번 반복한다. 버블 정렬과 비슷하지만 보다 개선된 알고리즘이라고 할 수 있다. 어떻게 정렬되어있건 일관성있게 n(n-1)/2에 비례하는 시간이 걸린다는 특징이 있고, 버블 정렬보다 일반적으로 2배정도 빠르다. 공간복잡도는 역시 단 하나의 ..

자료구조 '힙(Heap)' 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 자료구조 '힙(Heap)' 자세히 알아보기 힙 정렬(Heap Sort) 알고리즘의 개념 요약 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다. - 내림차순을 기준으로 정렬 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다. 내림차순 정렬을 위한 최대 힙의 구현 힙(Heap)은 1차원 배열로 쉽게..

선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)과 최대 선택 정렬(Max-Selection Sort)로 구분 할 수 있다. 최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다. 1. 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다. (정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.) 2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다. 3. 다음 인덱스에서 위 과정을 반복해준다. 이 정렬 알고리즘은 n-1개, n-2개... 1개씩 비교를 ..

삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다. 1. 삽입 정렬은 두번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다. 2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다. 3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다. 4. 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장한다. 이 정렬 알고리즘은 최악의 경우(역으로 정렬되어 있을 경우)엔 n-1개, n-2개... 1개씩 비교를 반복하여 시간복잡도는 O(N^2)이지만, 이미 정렬되어 있는 경우에는 한번씩..

버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다. 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼만 반복해주면 된다. 1. 삽입 정렬은 두번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전의 인덱스 값을 비교한다. 2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다. 3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다. 4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다. 이 정렬 알고리즘은 1부터 비교를 시작하여..

합병 정렬은 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을때까지 반복한다. 입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계쏙 쪼개 나간 뒤, 합치면서 정렬해 최우에는 하나의 정렬을 출력한다. 합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해나간다. 오름차순의 경우 배열A, 배열B를 비교하여 배열A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A, B의 반복을 진행한다. 이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다..