반응형 전체 글44 캐나다 IT 코딩 Dijkstra Dijkstra(다익스트라) 알고리즘은 그래프에서 두 노드 사이의 최단 경로를 찾기 위한 알고리즘입니다. 음수가 아닌 간선 가중치를 가진 그래프에서 작동하며, 시작 노드로부터 그래프의 다른 모든 노드까지의 경로들을 찾아 비교합니다. Dijkstra 알고리즘의 정의 Dijkstra 알고리즘을 이해하기 위해서는 우선 BFS (Breadth-first search) 알고리즘을 학습하는 것을 추천드립니다. 이를 통해 우선 Graph라는 데이터 형식과 Node, Edge 등에 대해 확실히 이해를 할 수 있고, 이 두 가지 알고리즘의 비교를 통해 구체적으로 이해할 수 있게 됩니다. Dijkstra 알고리즘과 BFS(Breadth-first search) 알고리즘은 둘 다 그래프에서 최단 경로를 찾는 데 사용되는 알.. 2024. 1. 6. 캐나다 IT 코딩 Breadth-first search 너비 우선 탐색(Breadth-first search-BFS)은 그래프 순회 알고리즘으로, 그래프의 모든 정점(Node)을 정확히 한 번만 방문해서 탐색하고, 큐(Queue) 자료 구조를 사용하여 저장하고 필요한 데이터를 추적하는 알고리즘입니다. Breadth-first search의 정의 Graph, Node 그리고 Edge의 정의 우선 BFS라는 알고리즘을 알기 전에 Graph와 Node 그리고 Node 간의 관계에 대해서 우선 알아보도록 하겠습니다. 의미 자체가 어렵고 이를 구성하는 세부 요소들을 글로 이해하는 것이 애매모호하기 때문에 예를 들도록 하겠습니다. X라고 하는 장소에서 Y 장소에 도달하기 위한 방법으로 우리는 여러 가지 시나리오를 생각할 수 있습니다. 직접적으로 갈 수 있는 방법은 없고.. 2023. 12. 21. 캐나다 IT 코딩 Hash Table Hash Table은 키와 값으로 데이터를 저장하는 자료구조입니다. 키를 해시 함수를 통해 해시값으로 변환하여 인덱스로 사용하며, 이를 통해 빠른 데이터 접근이 가능합니다. O(1)의 평균 시간 복잡도를 가지는 효율적인 자료구조입니다. Hash Table의 정의 Hash Table은 키(Key)와 값(Value)을 연결하여 데이터를 저장하는 자료구조입니다. 키(Key)를 해시 함수를 통해 해시값(Hash Value)으로 변환한 후, 해당 해시값을 인덱스로 사용하여 값을 저장하고 검색합니다. 이를 통해 데이터에 대한 빠른 접근이 가능하며, 평균적으로 O(1)의 시간 복잡도를 가지는 효율적인 자료구조입니다. Hash Table은 다양한 용도로 사용될 수 있으며, 데이터베이스, 캐시, 인덱싱, 집합 연산 등 .. 2023. 12. 16. 캐나다 IT 코딩 Quick Sort Quick Sort(퀵 정렬)는 분할 정복 접근 방식을 따르는 정렬 알고리즘입니다. 아직 정렬되지 않은 배열을 Pivot(기준 값)을 기준으로 분할하여 작은 값과 큰 값으로 분리한 후, 하위 배열들을 재귀적으로 정렬합니다. Quick Sort의 정의 Quick Sort(퀵 정렬)는 Divide and Conquer(분할 정복 접근 방식)을 따르는 널리 사용되는 정렬 알고리즘입니다. 이 알고리즘은 배열에서 피벗 요소를 선택하고, 나머지 요소들을 피벗보다 작은지 큰지에 따라 두 개의 하위 배열로 분할합니다. 그런 다음, 하위 배열들은 동일한 과정을 반복하여 재귀적으로 정렬됩니다. 대용량 데이터셋에 효율적이며, 평균 시간 복잡도는 O(n log n)입니다. 하지만 반드시 O(n log n) 이 보장되는 것은 .. 2023. 12. 12. 캐나다 IT 코딩 Recursion Recursion 알고리즘은 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. Base case(기본 사례)에서는 재귀 호출을 멈추는 조건을 설정하고, Recursive case(재귀 사례)에서는 문제를 더 작은 부분 문제로 나누어 자기 자신을 호출하여 해결합니다. Recursion (재귀) 알고리즘의 정의 Recursion 알고리즘은 앞서 잠깐 언급한 것과 같이 두 가지 요소로 구성됩니다: base case(기본 사례)와 recursive case(재귀 사례). Base case(기본 사례): Recursion 알고리즘이 멈추는 조건을 정의합니다. Base case에서는 일반적으로 단순한 문제를 해결하거나, 재귀 호출을 멈추는 조건을 설정합니다. 이 조건이 설정되지 않으면 Infinite L.. 2023. 12. 9. 캐나다 IT 코딩 Selection Sort Selection Sort(선택 정렬)는 배열의 정렬되지 않은 부분에서 반복적으로 최소(혹은 최고) 요소를 선택하고 정렬된 부분의 시작에 배치하는 정렬 알고리즘입니다. 이 과정은 전체 배열이 오름차순 (혹은 내림차순)으로 정렬될 때까지 계속됩니다. Selection Sort(선택 정렬)의 정의 Selection Sort(선택 정렬)에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 두 개의 하위 배열로 분할됩니다. 초기에는 정렬된 부분은 비어 있고, 정렬되지 않은 부분은 배열의 모든 요소를 포함합니다. 알고리즘은 정렬되지 않은 부분에서 최소 요소(혹은 최고)를 선택하고 정렬되지 않은 부분의 가장 왼쪽 요소와 교환합니다. 이렇게 하면 최소 요소가 정렬된 부분에서 올바른 위치에 배치됩니다. 정렬된 부분의 크기.. 2023. 12. 7. 이전 1 2 3 4 ··· 8 다음
