Kendrick's Blog

배열에서 가장 큰 정사각형 찾기프로그래머스에서 제공하는 문제 중 하나입니다.배열 내부를 탐색하여 가장 큰 정사각형을 찾는 알고리즘입니다.배열은 아래와 그림과 같이 제공되며 1이 정사각형일 때, 배열 내부의 가장 큰 정사각형의 값을 return 합니다. 위와같은 배열이 있으며, 가장 큰 정사각형은 아래와 같습니다.가장 큰 정사각형이 9칸을 차지하고 있으므로 답은 9입니다. 구현하는 방법이야 여러가지가 있겠지만 10000*10000의 배열이면 성능에 문제가 생기게 됩니다. 그래서 성능을 고려하여 DP(Dynamic Programming)를 사용하여 구현할 수 있습니다. 자바스크립트로 구현한 방법은 아래와 같습니다.function solution(board) { var answer = 0; var length..

이진 탐색 트리는 '이진 탐색'을 위한 '이진 트리' 입니다.이진 탐색 알고리즘의 경우 배열인 경우에만 사용할 수 있는 문제가 있습니다.링크드 리스트는 중앙 요소를 알 수 없기때문에 이진 탐색이 불가능합니다.이 딜레마를 해결해주는 자료구조가 바로 '이진 탐색 트리' 입니다. 이진 트리 탐색은 규칙이 있습니다. 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다. 위에서 부터 자식노드를 탐색을 하게 됩니다. 데이터도 위의 규칙대로 추가 되게 됩니다. 만약 20 노드가 삭제 될 시에는 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드로 위치가 옮겨가면 됩니다. 이진트리의 문제점 이진 탐색 트리의 경우 동적으로 크기가 증가해도 잘 대처 하며 탐색속도도 매우 훌륭합니다. ..

순차 탐색 순서대로 무식하게 찾는 방식입니다. 단순합니다. 조금 더 효율적인 방식을 위해 자기 구성 순차탐색이라는 방식이 존재합니다. 자기 구성 순차 탐색 자기 구성법은 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법입니다.아래 세가지 방식으로 구분됩니다.- 전진 이동법(Move To Front)- 전위법(Transpose)- 빈도 계수법(Frequency Count) 전진 이동법 전진 이동법은 어느 항목이 한번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞 (링크드 리스트에서는 헤드)에 위치시키는 방법입니다. 이렇게 할 경우 한번 찾은 항목을 연이어 또 찾을 때 단번에 탐색을 완료 할 수 있습니다. MS 워드의 '최근 문서' 기능과 같은 원리로 동작 ..

퀵 정렬은 전쟁 전략중의 하나인 분할 정복에 기반한 알고리즘입니다.분할 정복 전략은 적군의 전체를 공략하는 대신, 전체를 구성하는 구성 요소들을 나누어 잘개 쪼개진 적을 공략하는 전법입니다. 퀵 정렬은 아래과정을 거칩니다. 1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 기준 요소의 왼편에, 큰 값은 오른편에 위치시킵니다. 2. 이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택 후 같은 방법으로 데이터 집합을 분할합니다. 3. 1, 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 됩니다. function quickSort(array){ if(array.length < 2) return ..

삽입정렬이란?데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다.뒤섞여있는 트럼프 카드를 순서대로 정리하는 모습과 비슷합니다.데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하여 정렬된 데이터 집합을 찾아냅니다. 버블정렬은 반드시 모든 반복에 대해서 비교를 거치지만 삽입 정렬은 데이터 집합이 정렬되어 있는 경우에는 한번도 비교를 거치지 않습니다. var array= [1,9,-1,5,10,23,-2,7,4,5]; for (i = 0; i 0) && (array[j-1] > temp)) { array[j] = array[j-1];..

버블정렬이란 데이터를 정렬하는 과정이 마치 거품이 수면을 향해서 올라오는 모습과 같다고 붙여진 이름입니다.데이터 집합을 순회하면서 집합 내의 이웃 요소들 끼리의 교환을 통해서 정렬을 수행합니다. 아래 그림을 보시면 스텝이 진행 될 때마다 값을 비교하여 더 큰 숫자가 뒤로 가게 정렬되고 있습니다. 위 그림은 5번에 스텝에 정렬이 완료 되었지만, 더 복잡하게 섞인 정렬의 경우 위의 동작이 계속 반복되게 됩니다.아래 자바스크립트 코드를 참고하시기 바랍니다. #소스코드 var array= [1,9,-1,5,10,23,-2,7,4,5,1]; for (i = 0; i array[i+1]) { temp = array[i+1]; array[i+1] = array[i]; array[i] = temp; i = i-2; }..