Algorithm

[개요]그래프 탐색 알고리즘.그래프 : 여러 개체들이 연결되어 있는 자료구조탐색 : 특정 개체를 찾기 위한 알고리즘  대표적 문제 유형1. 경로탐색 유형 (최단거리, 시간)2. 네트워크 유형 (연결)3. 조합 유형 (모든 조합 만들기) DFS : 재귀함수로 구현하는 것이 일반적BFS : 큐나 링크드 리스트를 사용하여 구현하는 것이 일반적 [DFS - 깊이 우선 탐색]   [BFS - 너비 우선 탐색]    [Java 코드]import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.*;public class D..

- 개요다익스트라 알고리즘은 '그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘' 이다. (최단 경로 문제 | Shortest Path Problem) 시작점 부터 순차적으로 최단 거리를 구하는 방식으로 진행된다. - 예시를 이용한 알고리즘 설명위와 같은 경로맵이 있다.시작점은 "정점 4" 이다. '정점 방문 여부' 와 '각 정점 별 최단 거리' 테이블을 통해 순차적으로 최단 거리를 구한다.시작점인 '정점 4' 는 이미 방문한 것으로 표시하고, 시작점이기 때문에 최단 거리는 0 으로 설정한다. [탐색 정점 : 정점 4]정점 4 와 인접한 정점 2, 1, 6 에 대해 최단 거리를 갱신한다.  [탐색 정점 : 정점 1]미방문 상태인 정점 (1, 2, 3, 5, 6) 중 출발점으로 부터 ..

"탐색 (Search)" 알고리즘에 대해 알아보자. 탐색 알고리즘은 "저장된 데이터들 중 원하는 데이터를 찾는 알고리즘" 이다. 다양한 탐색 방식의 알고리즘이 존재한다. 각각의 탐색 방식과 시간복잡도 등 다양한 형태에 따라 적절한 탐색 알고리즘을 적용한다. 탐색 알고리즘 1. 선형탐색 (Linear Search) : 한쪽 끝에서 하나하나 순서대로 탐색하여 원하는 값을 찾는 알고리즘. (- 정렬되지 않은 배열도 가능) 선형 탐색은 순차 탐색 이라고도 불린다. 장점은 탐색 알고리즘의 가장 간단하고 직접적인 방법으로, 구현하기 쉽다. 그러나, 배열의 크기에 직접적인 영향을 받는다. (일반적으로 배열이 클수록 시간이 많이 든다.) * 시간복잡도 Best Case : 배열의 첫 부분(탐색하는 첫 데이터)이 key..

1. Dynamic Programming (동적 계획법) 이란? : 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 뜻한다. => 주어진 문제를 풀기 위해서, 문제를 여러 하위 문제로 나누어 해결한 다음 그 해결책을 저장해 둔 후 결합하여 주어진 문제를 해결하는 문제해결 패러다임이라고 할 수 있다. * 최적 부분 구조를 이룬다. (Optimal Substructure) * 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다. (Overlapping Recursive Call) 위 두가지 성질이 있는 문제에 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거한 것을 "동적 계획법" 이라 한다..