본문 바로가기

Algorithm

 (21)
[Udemy] 단일 연결 리스트 (SingleLinked List) 구현 정의단일 연결 리스트는 선형 자료구조로,각 데이터는 value(값), next(포인터)를 가진 Node라는 객체로 이루어져있다.자료구조란, 데이터와 데이터 간의 관계 및 작업, 기능 등을 포함한 것을 의미한다. 단일 연결리스트는 head, tail, length 값을 가지고 있는 객체이다.head는 단일 연결 리스트의 시작 Node를 의미하고,tail은 마지막 Node를 의미한다.length는 단일 연결리스트의 길이를 의미한다. 코드 및 구현1. Node 객체 구현 ES2015 문법 중 class를 사용하여 구현해보자.class Node { constructor(val) { this.val = val; this.next = null; }} Node 클래스는 ..
[Udemy] 지수 정렬(Radix sort)이란? 정의지수정렬은 비교 정렬이 아닌 특수한 정렬 방법이다.이진법이든 십진법이든 정수 정렬에서만 수행된다.A가 B보다 큰지 작은지 비교하는 것이 아닌 자릿수를 통해서 정렬한다.  접근각 자리수를 버켓(bucket)에 담는다. 버켓에 담긴 낮은 숫자순으로 아래에서부터 재배열한다.이를 최대 자릿수까지 반복하여 모두 진행하면 결과가 나타난다. 1. 자릿수를 구하는 함수가 필요하다.2. 몇번 반복해야하는지 알기 위해 최대 자릿수를 알아내야한다.3. 최대 자리수만큼 반복하면서 버켓에 담긴 자릿수를 다시 배열로 정렬하여 마지막 결과값을 반환한다.  코드1. helper 메소드주어진 정수의 자릿수에 위치한 숫자를 구하는 함수가 필요하다.그래야 버켓에 원하는 위치에 추가할 수 있기 때문이다.function getDigit(..
[Udemy] 퀵 정렬(Quick Sort)이란? 정의배열에 1개 이하의 요소가 남을 때 까지 분할하여 정렬한다."피벗 포인트"라는 단일 요소를 선택하여 오름차순 정렬 시 이보다 작은 숫자를 좌측으로 이동시키고이보다 큰 숫자는 그대로 둔다.  접근퀵 정렬도 병합 정렬과 비슷한 가정으로 분할(split) → 정렬(sort) 로직으로 접근할 수 있는데,병합 정렬은 index의 중간을 기준으로 정했다면, 퀵 정렬은 "피벗 포인트"라는 단일 요소를직접 지정하여 정렬을 할 수 있다.  "피벗 포인트"는 처음, 중간, 끝 모두 지정할 수 있는데,이해를 돕기 위해 처음으로 지정해두자. 코드1. Pivot helper 함수 구현 우선, 피벗 포인트를 기준으로 모든 요소가 피벗 포인트보다 큰지, 작은지만 판단하여 좌,우로 정렬한다.이 때, 좌, 우 정렬된 요소들의 순서..
[Udemy] 병합 정렬(Merge Sort)이란? 정의말 그대로 Merge + Sorting을 실행하는 정렬 방법이다.사실은 분할(Split) → 정렬(Sort) → 병합(Merge)이 과정으로 진행한다.배열 길이가 1이하면 정렬되었다고 가정한다.접근분할과 정렬 + 병합 이렇게 2단계로 나눠서 접근해보자.1. 정렬 + 병합정렬 + 병합은 첫번째 배열과 두번째 배열을 비교하면서 정렬을 하면서 하나의 배열로 병합하는 로직이 필요하다.이는 앞서 배웠던 Two Pointer 패턴을 사용하면 쉽게 구현할 수 있다.인수로 전달 받은 두 배열은 정렬된 배열임을 가정하고 결과 배열을 선언한다.왜냐하면, 배열의 길이가 1이하인 것부터 정렬 + 병합하면서 진행할 것이기 때문이다.첫번째 배열 포인터 i, 두번째 배열 포인터 j 선언하여 둘 중 하나의 포인터가 배열을 순회하..
[Udemy] 삽입 정렬(Insertion Sort)이란? 정의배열의 과반을 점차적으로 정렬로 만들어 대상 요소를 정렬된 배열에 삽입하는 방식첫번째 배열에서 부터 비교하면서 좌측의 정렬된 배열을 점차 늘려나간다.기존 정렬된 배열을 재배열하지 않고 새로운 데이터를 삽입하므로기존 정렬을 유지하면서 새로운 데이터를 정렬할 때 사용하는 것이 유용하다. 코드function insertionSort(arr) { // 첫번째 요소를 정렬된 배열 변수에 추가한다. let sortedArr = [arr[0]] // 두번째 요소부터 반복문 시작하며 정렬된 배열에 어디에 삽입할지 비교한다. for (let i = 1; i = 0 && sortedArr.length === i; j--) { if (sortedArr[j] > currVal &&..
[Udemy] 선택 정렬(Selection Sort)이란? 정의요소를 비교하여 최솟값을 앞쪽으로 이동시켜 정렬하는 방법으로, 시간 복잡도는 O(n^2)이다.외부 반복문 1회당 swap이 1회 발생하는 특징이 있다. 코드function selectionSort(arr) { function swap(arr, idx1, idx2) { [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]] } for (let i = 0; i arr[j]) { min = j } } swap(arr,i,min) } return arr;} swap 함수를 따로 추출해서 사용했다.외부 반복문 변수 i를 선언하고 마지막 요소 이전까지 순회..
[Udemy] 버블 정렬(bubble sort)이란 ? 정의버블정렬은 오름차순 정렬 시 두 숫자를 비교해서 더 큰 숫자를 한번에 한칸씩 오른쪽으로 이동시키는 정렬이다. 접근1. i 변수를 선언하여 반복문을 순회한다. 이 때, 순회 순서는 역순으로 한다.2. j 변수를 선언하여 처음부터 i - 1 까지 순회한다.3. 오름차순 정렬이라면 arr[j] > arr[j+1] 을 만족하면 서로의 위치를 교환한다. 코드function bubbleSort(arr) { for (let i = arr.length; i > 0; i--) { for (let j = 0; j arr[j+1]) { let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] =..
[Udemy] 재귀 함수란 무엇인가? 재귀 함수란?Recursion, 자기 자신을 호출하는 함수 접근 방법한 가지 문제를 가지고 end point(종료점)에 도달할 때 까지 더 작은 부분이나 변경되는 부분에서 반복적으로 수행한다. 사용 하는 이유- 모든 곳에 사용된다.- JSON.stringify, JSON.parse, DOM 등...- 반복문으로 해결 가능한 문제를 재귀적으로도 접근할 수 있다. 기본 요소1. 종료 조건 종료 조건이 무조건 있어야 한다. 그렇지 않으면 무한 루프에 빠지게 된다. 2. 다른 입력값 재귀 함수가 return 값을 제대로 정의하지 않거나 처음 호출할 때 사용한 매개변수와 다른 값을 사용하지 않는다면 잘못된 값을 반환하게 된다. 재귀 함수 종류1. helper 메소드 결과를 저장하여 사용해야할 때 사용되는 패턴재귀..

티스토리툴바