[알고리즘] 위상 정렬 (Topology Sort)

목 차 위상정렬(Topological Sorting) 기본 개념 및 조건 위상정렬을 구현하며 배운 것들 구현 방법 위상정렬(Topological Sorting) 위상정렬은 방향이 있는 그래프에서 유효하다. 예를 들면, 여러 작업이 서로 의존 관계를 가질 때, 어떤 순서로 작업을 진행해야 하는지를 결정할 때 유용하다. 위상정렬은 결과가 매 번 다를 수 있다. 예를 들면, 4는 2의 앞에 있어야 하고, 3은 1의 앞에 있어야 한다고 가정할 때 예상되는 경우의 수는 4231, 4321, 4312 등 여러 개가 될 수 있다. 기본 개념 및 조건 방향성 그래프: 각 간선에 방향이 있는 그래프여야 한다. 단방향 그래프: 각 간선에 방향이 있되 양방향이지 않아야 한다. 위상정렬을 구현하며 배운 것들 최적화 전 더보기..

Algorithm 2023.11.29

[자료구조] 세그먼트 트리 (Segment Tree)

목 차 세그먼트 트리 개념 세그먼트 트리를 하며 배운 것들 세그먼트 트리 코드 세그먼트 트리 개념 세그먼트 트리는 구간 쿼리와 업데이트를 최적으로 수행할 수 있는 유연한 자료구조이다. 주로 구간 합, 또는 구간 내 최솟값이나 최댓값을 찾는 문제에 사용된다. 기본 구조 트리 구조: 세그먼트 트리는 이진 트리 구조이며, 각 노드는 배열의 특정 구간(Segment)을 대표한다. 리프 노드: 트리 구조에서 자식 노드가 없는 노드를 말한다. 즉 트리 가장 아래에 위치한 노드들을 말한다. 내부 노드: 자식 노드들의 값을 합치거나 비교하여 해당 구간의 값을 저장한 노드들을 말한다. 작동 원리 트리 초기화: 주어진 배열로 완전 이진 트리를 만든다. O(N) SUM함수: 구간합을 구하는 함수 O(log N) UPDATE..

Algorithm 2023.11.21

[알고리즘] 다익스트라(Dijkstra algorithm)와 우선순위 큐(MinHeap)

목 차 최소 힙 (MinHeap) 다익스트라 알고리즘 기본 개념 다익스트라 알고리즘 구현 최소 힙 (MinHeap) 다익스트라 알고리즘은 우선순위 큐(MinHeap)를 사용하는 것이 일반적이다. 최소 힙(MinHeap)의 정의 최소힙은 부모 노드가 자식 노드 보다 작거나 같은 값을 가지고 있는 이진 트리이다. 힙의 루트에는 트리에서 가장 작은 값이 위치한다. 최소 힙(MinHeap)의 연산 - 삽입: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위치를 조정하여 힙 속성을 만족시킨다. - 추출: 힙의 루트노드를 제거하고 마지막 노드를 루트로 이동시킨 다음, 자식들과 비교하며 위치를 조정하여 힙 속성을 만족시킨다. 여기서 추출할 때 JS 기준으로 shift() 메서드를 사용하면 앞에 노드를..

Algorithm 2023.11.14