bright jazz music

그래프와 이진 힙을 사용한 우선순위 큐를 알아야 한다. 다익스트라 알고리즘의 목적은 그래프의 두 정점(vertex) 사이에 존재하는 최단 경로를 찾는 것이다.- 서울에서 부산으로 가는 최단경로(GPS)- 인간 사이의 바이러스의 감염 경로- 목적지까지의 가장 저렴한 경로 이를 위해 선행되어야 하는 작업은 두 정점 사이에 가중치(예를 들면 거리) 가 존재하도록 해야 한다는 것이다. 이전 포스팅에서는 양방향 무가중치 그래프만을 다뤘다. 그래프(Graph)무방향 그래프를 인접 리스트로 구현한 예시.class Graph { constructor() { this.adjacencyList = {}; // 인접리스트 생성 } /* 정점(노드) 추가 */ addVertex(vertex) { // 인접리스트에 입력한 정점..

무방향 그래프를 인접 리스트로 구현한 예시.class Graph { constructor() { this.adjacencyList = {}; // 인접리스트 생성 } /* 정점(노드) 추가 */ addVertex(vertex) { // 인접리스트에 입력한 정점이 없으면 빈 배열 생성. 이미 존재한다면 아무 작업도 수행하지 않음. if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } /* 간선 추가: 두 정점 사이에 간선 추가. 정점이 가진 리스트에 상대 정점을 추가해 주는 방식*/ addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2);..

해시테이블은  키-값 쌍을 저장하는 데 사용된다.해시 테이블의 키는 순서를 가지지 않는다.값을 찾고, 추가하거나, 제거하는 속도가 빠르다. 많은 프로그래밍 언어가 해시 테이블 자료구조를 기본적으로 제공한다.- 파이썬: Dictionary- 자바스크립트: Object, Map (오브젝트의 경우 string 타입만을 키로 설정할 수 있다.)- 자바&고 : Map- 루비: Hash 이 포스팅에서는 기본적으로 제공하는 해시 테이블 자료구조를 사용하지 않고 직접 간단한 해시테이블을 만들어 보았다. 충돌처리에는 Separate Chaining 방식을 사용하였다. 이는 해싱을 통해 동일한 값을 가지게 된(충돌한) 키-값 쌍이 해당 원소의 이중 배열에 추가되는 방식을 의미한다. 이 방식 외에 선형 조사법(Linear ..

우선순위 큐(Priority Queue)우선순위 큐는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조다.다른 자료구조를 사용해도 되지만 이진 힙을 사용하는 것이 효율적이기 때문에 이진 힙으로 우선순위 큐를 구현하는 경우가 일반적이다. 아래 링크는 이진 힙 관련 포스팅:https://catnails.tistory.com/537  필수 구현 메서드:enqueue(value, priority) - 우선순위와 함께 새로운 요소 추가dequeue() - 가장 높은 우선순위의 요소를 제거하고 반환peek() - 가장 높은 우선순위의 요소를 반환isEmpty() - 큐가 비어있는지 확인 시간 복잡도:삽입(enqueue): O(log n)삭제(dequeue): O(log n)조회(peek)..

이진 힙은 트리의 일종이다.이진 힙은 이진 탐색 트리와 같이 두 개의 자식을 가진다.두 자식이 부모보다 작은 경우, 즉 루트가 최대 크기가 되는 힙이 최대 힙이다.자식들이 부모보다 큰 경우 최소 힙이며 이 경우, 루트가 최소값이 되는 최소힙이다.이진 힙은 이진 탐색트리와는 다르게 두 자식을 나누는 기준이 없다. 좌우로 나누는 기준은 없다는 것이다. 그저 부모보다 크거나 작기만 하면 된다. 특정 인덱스를 가진 노드의 자식 노드의 인덱스를 확인하려면 아래와 같은 식을 따르면 된다.왼쪽 자식: 2n + 1오른쪽 자식: 2n + 2 역으로 자식 노드에서 부모 노드를 찾으려면부모 노드의 인덱스를 사용해 자식 노드의 인덱스를 구하는 방식을 역으로 하면 된다. 즉 2n+1을 역으로 하면 된다.(n-1)/2 을 하고..

1. 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 현재 노드보다 작은 값, 오른쪽 자식은 큰 값을 가지는 특별한 형태의 이진 트리이다. 필수 구현 메서드:insert(value) - 새로운 값을 적절한 위치에 삽입find(value) - 특정 값을 찾아서 반환remove(value) - 특정 값을 가진 노드를 삭제getMin() - 최솟값(가장 왼쪽 노드) 반환getMax() - 최댓값(가장 오른쪽 노드) 반환주요 구현 포인트: 1. 삽입 시 순서 결정:if (value   2. 삭제 시 3가지 경우 처리:리프 노드: 직접 삭제하나의 자식: 자식을 현재 위치로 승격두 개의 자식: 중위 후속자로 대체3. 균형 관리:트리가 한쪽으..

트리(Tree) 트리는 노드들의 계층적 구조로, 한 노드가 여러 자식 노드를 가질 수 있는 비선형 데이터 구조이다. 최상위에 있는 노드를 루트라 하고, 자식이 없는 노드를 리프 노드라 한다. 주요 용어:노드(Node) - 트리의 기본 요소로 데이터와 자식 노드들의 참조를 포함루트(Root) - 트리의 최상위 노드부모-자식(Parent-Child) - 두 노드의 직접적인 연결 관계리프(Leaf) - 자식이 없는 말단 노드높이(Height) - 루트에서 가장 먼 리프까지의 거리깊이(Depth) - 특정 노드까지 루트로부터의 거리장점:계층적 데이터 표현에 적합빠른 검색과 삽입 가능 (구현에 따라 O(log n))동적인 크기 조절 가능자연스러운 재귀적 구조단점:구현이 복잡할 수 있음균형 유지가 어려울 수 있음메..

스택(Stack)스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조이다. 데이터는 한쪽 끝에서만 삽입되고 삭제되며, 가장 최근에 추가된 항목이 가장 먼저 제거된다. 장점:단순하고 효율적인 구현모든 기본 연산이 O(1) 시간복잡도메모리 사용이 예측 가능하고 효율적함수 호출 스택, 실행 취소(undo) 기능 등에 적합단점:중간 데이터 접근 불가크기가 고정될 수 있음 (배열로 구현 시)데이터 검색에 부적합특정 위치 삽입/삭제 불가시간복잡도:push(): O(1)pop(): O(1)peek(top): O(1) - 스택의 맨 위 요소를 제거하지 않고 확인isEmpty(): O(1)search(n): O(n) - 특정 값 검색access(n): O(n) - 특정 위치 접근주요 응용:함..

이중 연결리스트(Doubly Linked List)이중 연결리스트는 각 노드가 데이터와 함께 이전 노드와 다음 노드를 모두 가리키는 포인터를 가진 선형 데이터 구조이다. 각 노드는 양방향으로 연결되어 있어 이전 노드와 다음 노드 모두에 접근이 가능하다.장점:1. 양방향 순회 가능 - 이전/다음 노드 모두 접근 가능2. 삭제 연산 최적화 - 이전 노드 참조가 있어 O(1)로 가능3. 특정 노드 탐색 최적화 - 양쪽에서 탐색 가능하여 단일 연결리스트 대비 평균 탐색 시간 절반4. 단일 연결리스트의 장점(동적 크기, 유연한 메모리 할당) 유지단점:1. 추가 메모리 공간 필요 (이전 노드 포인터 추가)2. 삽입/삭제 시 포인터 처리가 더 복잡3. 구현이 단일 연결리스트보다 복잡4. 특정 인덱스 접근은 여전히 O..

단일 연결리스트(Singly Linked List)단일 연결리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 선형 데이터 구조이다.각 노드는 다음 노드만을 가리키며 (단방향), 이전 노드로는 접근할 수 없다. 장점:1. 동적 크기 - 메모리를 효율적으로 사용2. 삽입/삭제가 배열보다 효율적3. 메모리 할당이 유연함 단점:1. 특정 인덱스로의 접근이 O(n)2. 이전 노드로 접근 불가3. 추가 메모리 공간 필요 (다음 노드 포인터) 필수 구현 메서드 push() - 끝에 추가pop() - 끝에서 삭제shift() - 앞에서 삭제unshift() - 앞에 추가get() - 조회set() - 수정insert() - 중간 삽입remove() - 중간 삭제 위 목록은 단일 연결 리스트를 구현..