오늘도 조으네💜

컴퓨터 공학 지식/자료구조, 알고리즘

📌 연결 리스트(Linked List) 하나의 객체를 이루는 노드가 연결되어 리스트를 이루는 구조이다. 노드에는 값을 담고 있는 '데이터'와 다음 노드를 가리키는 '링크' 정보를 저장하고 있다. '데이터'에는 숫자, 문자열, 또다른 연결리스트 등 다양한 형식을 가질 수 있다. 리스트의 맨 앞 노드를 헤드(Head), 맨 마지막 노드를 테일(Tail)이라고 한다. 👉 배열과 연결리스트의 차이 배열과 연결리스트는 언뜻 비슷해 보이나, 분명한 차이점이 있다. 배열은 메모리의 연속된 위치에 저장되고, 연결 리스트는 각 노드가 임의의 위치에 저장된다. 또한 배열은 인덱스를 활용하여 특정 원소를 지칭하는 것이 간편하나(O(1)), 연결 리스트는 인덱스가 없다. 그래서 마지막 노드를 찾으려면 첫 노드에서부터 포인터를..

2023. 10. 17.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 퀵 정렬 병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. pivot(중심축) 을 정하고, 중심축 보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보낸다. 이렇게 pivot을 정해서 왼쪽, 오른쪽으로 나누고 다시금 이에 대해 재귀적으로 pivot을 정해서 왼쪽, 오른쪽을 나누는 과정을 반복하면 최종적으로 정렬이 완성된다. 퀵정렬의 실행시간은 피벗 선택 위치에 따라 달라질 수 있는데 이상적으로는 데이터 집합의 중간값을 피벗으로 선택하는 것이다. 하지만 데이터의 중간값을 구하기 어려운 상황이라면 첫 번째 요소 또는 마지막 요소 또는 중간, 무작위 요소를 선택한다. 👀 Example const quickSort = funct..

2023. 10. 16.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 병합 정렬 병합 정렬은 분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬하는 알고리즘이다. 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합치는 과정을 거친다. 👀 Example function merge(arr1, arr2) { let results = []; let i = 0; let j = 0; while(i arr1[i]) { results.push(arr1[i]) i++; }else { results.push(arr2[j]) j++; } } while(i < arr1.length) { resul..

2023. 10. 16.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 자료구조(Data Structure)란? 자료구조는 다수의 자료를 담기 위한 구조이다. 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다. 👀 자료구조의 필요성 데이터를 효과적으로 저장하고 처리하는 방법에 대해 이해해야 한다. 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다. 👀 자료구조의 종류 1. 선형 구조 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다. 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다. 배열(array) 연결리스트(linked list) 스택(stack) 큐(queue) 2. 비선형 구조 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조이다. 데이터가 일직선상으로 연결되어 있지 않아도 된다. 트리(tree) 그..

2023. 3. 23.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 삽입 정렬 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 최선의 경우는 O(n)의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2)의 시간복잡도를 갖게 된다. 👀 Example function insertionSort(arr) { for(let i = 1; i 0; j--) { if(arr[j] < arr[j - 1]) { let temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; }else { break; } } } return arr; } insertionSort([..

2023. 2. 21.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 에라토스테네스의 체 에라토스테네스의 체는 소수를 판별하는 가장 대표적인 알고리즘이다. 소수란? 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 에라토스테네스의 체를 사용하지 않고 간단하게 소수를 판별할 수도 있다. 👀 Expamle 1 두 정수가 주어질 때, 두 정수 사이의 숫자 중 소수인 수만 구하기 let result = []; function isPrime(n) { if(n === 1) return false; // 1은 소수가 아니다. for(let i = 2; i < n; i++) { if(n % i === 0) return false; } ret..

2023. 2. 17.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 선택 정렬 선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 👀 Example function selectionSort(arr) { for (let i = 0; i < arr.length; i++) { let lowest = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[lowest]) { lowest = j; } } if (i !== lowest) { let temp = arr[i]; arr[i] = arr[lowest]; arr[lowest] = temp; } } re..

2023. 2. 16.

컴퓨터 공학 지식/자료구조, 알고리즘

📌 버블 정렬 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 시간 복잡도가 O(n^2)로 연산 수가 가장 많아 정렬 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 편이다. 👀 Example 한 회전(loop)씩 수행할 때마다 가장 큰 자료가 맨 뒤로 이동한다. 즉, 1회전 때는 맨 끝의 자료가 확정되므로 더 이상 비교할 필요가 없고, 2회전 때는 끝에서 두번째 자료가 확정되므로 이 또한 비교할 필요가 없다. 이렇게 한 회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. function bubbleSort(arr) { let swaps; for (let i = arr.length; i > 0; i--) { swaps = false; for (let j = 0; ..

2023. 2. 16.