본문 바로가기

algorithm17

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라의 이론적 설명과 구현 방법, 경로 추적까지 살펴보겠습니다. [ Contents ] 1. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra): 현재까지 찾은 최적경로를 바탕으로 목적지까지의 최단경로를 탐색하는 알고리즘 출발지에서 가까운 지점부터 차례대로 최단경로를 탐색하며, 목적지까지의 최단경로를 탐색하는 알고리즘입니다. 그리디 알고리즘 기법으로, 한 번 결정된 최단 경로는 절대 바뀌지 않으며 이를 바탕으로 목적지까지의 최단경로를 계산합니다. 예를 들어, 출발지 A에서 목적지 D까지의 최단경로를 구해봅시다. 다익스트라 알고리즘에서는 A 주변 노드부터 최단거리를 계산하고, 점차 넓혀갑니다. 아직 A와의 거리를.. 2022. 3. 22.
[Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다. [ Contents ] 1. DFS 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. DFS(Depth First Search) 깊이 우선 탐색(DFS): 방문하지 않은 인접. star7sss.tistory.com 깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식 DFS는 끝이 나올.. 2022. 3. 20.
[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 그래프 그림에서 '노드(Node)'는 원으로 된 지역이고, '간선(Edge)'은 각 지역으로 이동할 수 있는 경로입니다. 간선마다 이동거리 혹은 이동시간에 따른 가중치가 부여됩니다. '모든 쌍의 최단 경로'는 말 그대로, 지역 간 최단거리를 구하는 작업입니다. 보통은 A에서 B로 바로 가면 빠르지만, 경유지를 거쳐서 가는 게 더 지름길일 때도 있죠. 이런 경우를 모두 고려해서 계산해야 합니다. 예를 들어, 위 경로에서는 1->3으로 바로 가는 것보다, 2를 경유해서 가는 게 더 빠릅니다. 2. 플로이드 - 와샬(Floyd-Warshall) 알.. 2022. 2. 28.
[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. DFS(Depth First Search) 깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식 그래프에서 '노드(Node)'는 원으로 표현된 데이터이며, 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 시작 노드를 1번이라고 할 때, DFS는 하나하나 끝까지 탐색합니다. [ 1 -> 2 -> 4 -> 5 -> 6 -> 3 ] (같은 거리 내 인접한 노드는 작은 노드부터 탐색한다고 가정) 2. 스택(Stack)을 이용한 탐색 방식 2022.02.10 - [Algorithm] - [Algorithm] 스택.. 2022. 2. 23.
[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First Search) 너비 우선 탐색(BFS): 가까운 주변 노드부터 탐색하며 점점 넓혀가는 방식 그래프에서는 원 안의 데이터를 '노드(Node)', 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 1을 시작으로 할 때, BFS는 주변 노드부터 탐색합니다. [ 1 -> 2 -> 3 -> 4 -> 5 -> 6 ] (같은 거리 내 인접한 노드는 숫자가 작은 노드부터 탐색한다고 가정) 2. 큐(Queue)를 이용한 탐색 방식 2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조 [Algori.. 2022. 2. 23.
[Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐 그래프의 트리 구조 중 하나인 '힙'과 구현 방법에 대해 알아보고, 그와 관련된 우선순위 큐도 살펴보겠습니다. [ Contents ] 1. 완전 이진트리(Complete Binary Tree) 완전 이진트리: 왼쪽부터 오른쪽으로 한 줄씩 채워가는 이진트리 트리(Tree) 구조는 마치 나무의 뿌리가 뻗어나가는 것처럼 위에서 아래로 확장되는 그래프 구조를 갖고 있습니다. 그래프에서 데이터는 '노드(node)'에 담기며, 맨 위 노드를 '루트(Rout) 노드'라고 합니다. 자신의 아래층에 있는 노드는 '자식 노드'이고, 위층에 있는 노드는 '부모 노드'입니다. 루트 노드는 부모 노드가 없으며, 리프(leaf) 노드는 자식 노드가 없습니다. (위 그래프에서 루트 노드: 1 / 리프 노드: 4, 9, 7) 이진트.. 2022. 2. 20.
[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic programming, DP): 작은 문제들에 대한 결과를 배열(리스트)에 저장하고, 이를 이용해서 입력 크기가 더 큰 문제를 점진적으로 해결하는 방법 동적계획법은 이전 문제들의 답을 메모해두는 알고리즘입니다. 메모해두면, 동일한 문제가 나왔을 때 바로 답을 찾아서 쓸 수 있습니다. 다시 계산할 필요가 없기 때문에, 이전 문제의 해가 필요할 때 많은 시간을 절약할 수 있습니다. fibo(0) = 0 fibo(1) = 1 fibo(2) = fibo(1) + fibo(0) fibo(3) = fibo(2) + fibo(1) ... fibo(n) = fibo(n-1) + fibo(n-2) 다이.. 2022. 2. 12.
[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조 [ Contents ] 1. 큐(Queue) 큐(Queue): 선입선출(First-in-First-out), 가장 먼저 들어간 자료부터 꺼내는 자료구조 큐는 '줄 서는 것'과 비슷합니다. 먼저 들어가서 기다린 자료부터 차례차례 꺼냅니다. 앞에서부터 꺼내며, 추가된 자료는 뒤에서부터 줄을 세웁니다. 자료의 중간이나 뒤부터 꺼낼 수 없으며, 앞에서부터 차례차례 꺼내야 합니다. 2. 큐 함수 .push(a) 맨 뒤에 a 자료 추가 (enqueue) .pop() 맨 앞의 자료 꺼내고 삭제 (dequeue) .front() 맨 앞의 자료 반환 .rear() 맨 뒤의 자료 반환 .isEmpty() 비어있으면 1, 아니면 0 반환 맨 앞의 자료만 삭제할 수 있고, 맨 뒤에 자료를 추가할 수 있습니다. 맨 앞과 뒤의 .. 2022. 2. 10.
[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조 [ Contents ] 1. 스택(Stack) 스택(Stack): 후입선출(Last-in-First-out). 가장 최근에 들어간 자료부터 꺼내는 자료구조 스택은 말 그대로 쌓는(stack) 자료 구조입니다. 아래서부터 차곡차곡 쌓은 다음, 위에서 하나씩 뺍니다. 밑에 있는 걸 억지로 뺄려고 하면 무너지겠죠.. 가장 마지막에 들어간 자료부터 꺼내며, 억지로 앞에 있는 자료를 꺼낼 수 없습니다. 2. 스택 함수 .push(a) a 추가 .pop() 가장 최근 자료를 삭제하고 반환 .peek() 가장 최근 자료를 반환 (삭제 X) .empty() 스택이 비어있으면 1, 아니면 0 반환 스택 함수는 가장 마지막에 넣은 자료만 조작할 수 있습니다. 3. 스택 구현 class Stack: # top은 가장 최근 .. 2022. 2. 10.

티스토리툴바