Knowledge/Algorithm
-
최단 경로 찾기 알고리즘 (다익스트라 / 플로이드 워셜) (python)Knowledge/Algorithm 2023. 7. 5. 15:38
최단 경로를 찾는 알고리즘 중 대표적인 두가지로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있습니다. 다익스트라 알고리즘 - 개념 다익스트라 알고리즘은 출발 노드에서 특정 노드로 가는 최단 경로를 구할 때 사용할 수 있는 알고리즘입니다. 출발 노드부터 시작해 그 노드에서 갈 수 있는 모든 방문하지 않은 노드를 방문 비용이 낮은 것 부터 확인하며 최단 거리 테이블을 갱신해 나가는 방식으로 최단 경로를 구해 나가며, 방문 비용이 낮은 것을 확인하기 위해 heap을 사용하는 것이 특징입니다. 다익스트라 알고리즘의 시간 복잡도는 최대 간선의 개수를 E, 노드의 개수를 V 라고 했을 때 O(ElogV) 입니다. - 구현 다익스트라 알고리즘 구현은 대표적인 유형인 백준 최소비용 구하기 문제를 예시로 풀며 진행..
-
탐색 알고리즘 DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색) (python)Knowledge/Algorithm 2023. 6. 27. 10:53
- 개념 DFS (깊이 우선 탐색) 와 BFS(너비 우선 탐색) 는 대표적인 탐색 알고리즘입니다. 동작하는 방식은 이름 그대로입니다. 위와 같이 그래프 형태로 데이터를 정렬했을 때 깊이 탐색을 우선하는 게 DFS, 너비 탐색을 우선하는 게 BFS입니다. 탐색 방향과 그로 인해 사용하는 자료 구조가 조금 다를 뿐 모든 노드를 다 탐색한다는 것은 같기 때문에 DFS로 풀리는 문제는 보통 BFS로도 풀립니다. 그 말인 즉 둘 중 하나만 제대로 알고 있어도 탐색 문제는 대부분 해결 가능하다는 말이지만 공부하는 단계에선 두 개념을 정확히 이해하고 구현도 모두 익히길 권장드립니다. - 구현 백준에 올라온 문제 중 'DFS와 BFS' 라는 기초 문제가 있어 이를 토대로 구현해보겠습니다. https://www.acmi..
-
다이나믹 프로그래밍 ( 동적 계획법 )Knowledge/Algorithm 2019. 9. 6. 16:38
- 다이나믹 프로그래밍이란 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 당연히 큰 문제를 작은 문제를 나누는 것과 다이나믹은 아무런 관련이 없다 이 용어를 처음 사용한 Richard Bellman은 그냥 '다이나믹'이 멋있어 보여서 사용했다고..ㅋ 다이나믹 프로그래밍으로 풀 수 있는 문제는 두가지 속성을 만족해야 한다. 1. Overlapping Subproblem ( 겹치는 부분 문제 ) : 큰 문제를 여러개의 부분 문제로 나누어서 풀 때 부분 문제간의 중복이 발생 가능해야 한다. 2. Optimal Substructure ( 최적 부분 구조 ) : 문제의 정답을 작은 문제의 정답을 통해 구할 수 있어야 한다. 예를 들어 대전에서 부산을 갈 때 최적의 루트가 대구를 거치는 거..