[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 오늘 포스팅할 내용은 다익스트라 알고리즘으로 앞서 포스팅했던 벨먼-포드 알고리즘과 마찬가지로 그래프의 최단 경로를 구하는 알고리즘 이다. 알고리즘의 이름은 개발자 에츠허르 W, 데이크스트라[Edsger W. Dijkstra]의 이름에서 유래했다. 다익스트라 알고리즘을 보기전에 그래프 자료구조와 벨먼-포드 알고리즘을 보고 오면 더 이해하기 쉬울 것이다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com [알고리즘] 벨먼-포드 알고리즘 (Bellman-Ford Algorithm)이번에 포스팅할 알고리즘.. 2025. 2. 6. [알고리즘] 벨먼-포드 알고리즘 (Bellman-Ford Algorithm) 이번에 포스팅할 알고리즘은 벨먼-포드 알고리즘으로 그래프의 최단 경로를 찾는 알고리즘이다. 이 알고리즘의 이름은 개발자인 리차드 E. 벨먼[Richard E. Bellman]과 레스터 포드 주니어[Lester Ford Junior]의 이름에서 유래 한다. 벨먼은 알고리즘의 중요 분야 중 하나인 동적계획법을 고안한 사람이기도 하다. 벨먼-포드 알고리즘을 보기전에 그래프 자료구조에 대해 잘 모른다면 아래의 포스팅을 보고 오면 좋다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com 현재 차근차근 해보.. 2025. 2. 4. [알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search) 이번 포스팅은 그래프를 탐색하는 알고리즘 중 하나인 깊이 우선 탐색(DFS)에 대해 알아보려고 한다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com 현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!📝 개념처음 시작할 때 그래프의 구조를 모르는 상태에서, 어떤 정점(시작점)에 위치 하고 있다고 가정해보자.목적은 간선에 따라가며.. 2025. 1. 17. [알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search) 이번 포스팅은 그래프를 탐색하는 알고리즘 중 하나인 너비 우선 탐색(BFS)에 대해 알아보려고한다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com 현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다! 📝 개념처음 시작할 때 그래프의 구조를 모르는 상태에서, 어떤 정점(시작점이라고 함)에 위치 하고 있다고 가정해보자. 목적은 시.. 2025. 1. 17. [알고리즘] 병합 정렬 (Merge Sort) 현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.📌 개념병합 정렬은 정렬할 수열을 거의 같은 길이의 수열 두 개로 분할한다. 더 이상 분할 할 수 없게 되면(즉, 각 그룹의 숫자가 한 개가 되면) 그룹끼리 통합하기 시작한다. 통합할 때는 정렬된 수열 두 개를 통합하여 하나로 정렬한다. 이러한 과정을 정렬된 수열이 하나가 될 때까지 반복한다. 1부터 7까지의 임의의 수열로 예를 들어 보겠다.먼저 수열을 반으로 분할해 간다. 먼저 두개로 분할 하고... 다시 분할하여.. 하나씩 될 때 까지 분할해 준다. 이제 분할이 완료되었으니 그룹을 합.. 2024. 10. 16. [알고리즘] 퀵 정렬 (Quick Sort) 현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.📌 개념퀵 정렬은 기준이 되는 수(피봇(pivot)이라고 함)를 수열 안에서 임의로 하나 선택한다. 그리고 피봇 이외의 수를 '피봇보다 작은 수'와 '피봇보다 큰 수'의 두 그룹으로 나누고, 이것을 다음과 같이 배치한다.[피봇보다 작은 수] 이제 각 [ ] 안을 정렬하면 전체가 정렬된다. [ ] 안을 정렬할 때도 다시 퀵정렬을 사용한다. 임의의 수열로 퀵정렬을 실시해 보겠다. 기준이 되는 수(피봇)을 임의로 하나 선택한다. 여기서는 6을 선택해 보겠다. 피봇 이외의 각 숫자를 피봇과 비.. 2024. 10. 14. 이전 1 2 3 다음
