728x90 반응형 👩💻 Programming/Algorithms & Data Structures21 [자료 구조] 트라이(Trie) 🤔 트라이란? => 주로 문자열을 검색하거나 저장된 문자열과 특정 문자열이 일치하는지 판별하는 데 쓰이는 특수한 트리이다. ⇒ 위 그림은 Sammie, Simran, Sia, Sam이라는 문자열을 저장한 트리이다. 각 노드는 분기되어 완전한 단어를 이룬다. 또한 각 노드는 경로의 끝을 나타내는 isCompleted이라는 boolean flag를 갖는다. 예를 들어 Sam이라는 문자열의 m은 endOfWord를 true로 만들어 해당 문자열의 끝임을 나타낸다. 노드 생성 ⇒ 트라이 노드는 자식을 저장하는 중첩된 객체를 사용하여 형성된다. 각 객체는 자신의 자식을 키로 삼는다. Trie 클래스는 위에서 보듯 TrieNode 클래스의 생성자에 의해 발현되는 root 노드를 갖는다. 삽입 ⇒ 문자열을 트라이에 .. 2023. 1. 30. DFS/BFS (깊이 우선 탐색/너비 우선 탐색) 이 문제를 다 풀고 나서 다른 사람들이 짜놓은 코드를 보는데 'DFS'라는 개념이 등장했다. 이전부터 어렴풋이는 알고 있었지만 막상 코드를 읽으니 어떻게 돌아가는지 머릿속에 잘 그려지지 않았다. 어차피 공부해야 하는 내용이니 이참에 확실히 짚고 넘어가야겠다 싶어 정리해보았다. 先요약 DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 큐 활용 🤔 DFS(Depth First Search, 깊이 우선 탐색) 🗣 그래프에서 깊은 부분부터 탐색하는 알고리즘. 스택 자료구조 활용. 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 pop 위의 과정 반복.. 2023. 1. 16. [자료 구조] 힙(Heaps) 힙(Heaps) 구조란? 👉 힙은 트리처럼 생긴 데이터 구조이다. 다른 트리형 데이터 구조와는 달리 자식을 가리키는 포인터 대신 데이터를 배열에다 저장한다. 따라서 인덱스를 활용하여 자식 노드에 간단히 접근할 수 있다. 👉 바이너리 힙(Binary Heap)의 경우 배열의 첫 번째 요소를 root로 삼고 좌우 자식 노드들이 번갈아가며 배열에 들어간다. 👉 부모 노드의 값이 자식 노드의 값보다 크면 최대 힙(Max-Heap), 작으면 최소 힙(Min-Heap)이라고 한다. 🔴 [2, 4, 23, 12, 13]과 같은 배열로 된 힙 구조를 그림으로 나타내면 다음과 같다. 힙 인덱스 🔴 바이너리 힙 구조에서 각 노드에 접근하기 위해 활용하는 인덱스는 다음과 같다. 퍼컬레이션(Percolation): Bubbl.. 2022. 11. 30. 힙 정렬(Heaps sort)에 대해 알아보자! 힙(Heaps)이란 무엇인가? 힙이란 트리(tree)처럼 생긴 데이터 구조이다. 부모가 자식보다 커서 내림차순 구조인 것을 max-heap, 부모가 자식보다 작아서 오름차순인 구조를 min-heap이라 한다. 데이터를 정렬하는 데 유용하게 쓰인다. 다른 트리 데이터 구조와 달리 자식에 대한 포인터를 가지지 않고 데이터를 저장하는 데 배열을 활용한다. 이번 글에서는 바이너리 힙(binary heaps)만을 다루겠다. 힙 구조 min-heap 구조를 그림으로 나타내면 다음과 같다. 위와 같은 min-heap은 뿌리 노드(root node)가 가장 낮은 값이 되고, max-heap은 뿌리 노드가 가장 높은 값이 된다. 바이너리 힙(Binary Heap)의 배열 인덱스 구조 바이너리 힙에서 다음과 같은 배열 인.. 2022. 6. 23. 하노이의 탑(Towers of Hanoi) References 이번 글은 아래 자료들을 참고하여 작성하였습니다. Towers of Hanoi on Khan Academy [파이썬]알고리즘 이야기(01. 하노이 탑) by 파이썬 클래쓰 on Youtube 무조건 이해시켜 드립니다. 비법 대방출! 재귀 알고리즘 Recursion - 하노이탑, 피보나치 수열 by 딩코딩 on Youtube 들어가며 하노이의 탑을 풀기 위해서는 우선 재귀 함수에 대한 이해가 필요하다. 재귀 함수는 javascript의 일반적인 동작 방식인 명령형(Imperative)이 아니라 선언형(declarative)으로 동작한다. 따라서 재귀 함수를 온전히 이해하려면 declarative programming에 대한 감각이 필요하다. 재귀 함수를 짤 때 중요한 것은 두 가지이다... 2022. 4. 7. 재귀 알고리즘(Recursive Algorithms) References 이번 글은 아래 자료들을 참고하여 작성하였습니다. Recursive Algorithms on Khan Academy Think Like a Programmer 위 인형은 러시아의 전통 인형 마트료시카이다. 큰 인형을 열면 그보다 작은 인형이 하나 나오고 다시 그 인형을 열면 또 작은 인형이 나오고를 반복하며 점점 크기가 작아진다. 재귀 함수도 이와 마찬가지로 주어진 조건을 충족할 때까지 함수 자신의 크기를 줄여가다 조건을 충족하면 결과값을 반환하는 함수이다. 배열 내 값 모두 더하기 // solution 1. const numArr1 = [1, 2, 3, 4, 5]; function iterativeArraySum(array, size) { let sum = 0; for (let i .. 2022. 4. 7. 퀵 정렬(Quick Sort) References 이번 글은 아래 자료를 참고하여 작성하였습니다. Insertion Sort on Khan Academy const partition = function (array, startIdx, lastIdx) { let partitonedArr = array, partitonedArrStartIdx = startIdx, partitonedArrLastIdx = lastIdx; const createPartitionedArr = function ( partitonedArr, partitonedArrStartIdx, partitonedArrLastIdx ) { let partitonedRightArrStartIdx = partitonedArr[partitonedArrStartIdx]; partit.. 2022. 4. 7. 삽입 정렬(Insertion Sort) References 이번 글은 아래 자료를 참고하여 작성하였습니다. Insertion Sort on Khan Academy Insertion Sort function insert(array, rightIndex, value) { // let temp; // for (let i = rightIndex; i >= 0; --i) { // if (value = 0 && array[i] > value; --i) { array[i + 1] = array[i]; array[i] = value; } } funct.. 2022. 4. 7. 합병 정렬(Merge Sort) References 이번 글은 아래 자료들을 참고하여 작성하였습니다. Section 33. Ack, MergeSort! Merge Sort on Khan Academy function mergeSort(arr) { if (arr.length === 1) { return arr; } const center = Math.floor(arr.length / 2); const left = arr.slice(0, center); const right = arr.slice(center); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { const results = []; while (left.length && right... 2022. 4. 7. 이전 1 2 3 다음 728x90 반응형
