공부/algorithm5 [알고리즘] 완전 탐색(Brute-Force Search) 문제를 해결하는데 가장 간단한 방법인 완전 탐색에 대해 알아보자 완전 탐색 정의 완전 탐색 예시 결론 완전 탐색 정의 완전 탐색 영어로 Brute-Force Search라고 쓰는데, 직역하면 '무식한 힘 탐색'이다. 이처럼 무식하게 가능한 경우를 모두 탐색하는 방법을 완전 탐색이라고 한다. 완전 탐색 예시 N개의 수를 입력받아서 그 중 3개를 더하여 가장 큰 수가 나오는 경우를 출력하는 프로그램을 작성해보자. #include using namespace std; int main() { int arr[1000]; int N; cin >> N; for (int i = 0; i > arr[i]; } int res = 0; for (int i = 0; i < N; i++) { fo.. 2023. 1. 26. [알고리즘] Dynamic Programming (DP, 동적 계획법) (c++) 이번 글에서는 알고리즘 보다는 계산 효율성을 증가시키는 방법 중 하나라고 할 수 있는 DP에 대해 알아보도록 하겠다. DP 정의 DP 사용이유 DP 예시, 구현 DP 정의 DP는 Dynamic Programming의 약자고 한글로는 다이나믹 프로그래밍, 동적 계획법 등등으로 부른다. DP는 큰 문제를 여러 개의 작은 문제로 나누어 풀고, 결합하여 문제를 해결한다. 이렇게만 보면 분할 정복과 비슷하다고 볼 수 있지만, DP는 메모이제이션(memoization) 방식을 사용한다는 것이 다르다. 메모이제이션은 연산 중 이미 계산한 값을 배열에 저장해두고 이후에 그 연산을 하게 되면 저장된 값을 배열에서 가져와 사용하여 중복된 연산을 하지 않는 것이다. DP 사용이유 재귀 함수만을 사용하여 어떤 문제(아래 예시.. 2023. 1. 16. [알고리즘] BFS(Breadth-First Search, 너비 우선 탐색) (C++) 이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해 알아본다. 그래프에 대한 간단한 설명을 보고 오면 더 좋다.(https://085a.tistory.com/8) BFS 정의 BFS 장,단점 BFS 탐색 과정 BFS 구현 BFS 정의 BFS는 Breadth-First search의 약자로 너비 우선 탐색이라고 한다. 임의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. BFS 장, 단점 BFS의 장점 해를 구할 때 최단 경로가 나온다. 노드의 수가 적고 깊이가 얕으면 빠른 탐색이 가능하다. BFS의 단점 DFS와 비교하면 더 큰 저장공간이 필요하다. BFS 탐색 과정 BFS가 그래프를 어떤 과정으로 탐색하는지 그림으로 확인해보자. 위 그림처럼 생긴 그래프를 예시로 한다. 탐색을 시작할.. 2023. 1. 4. [알고리즘] DFS(Depth-First Search, 깊이 우선 탐색) (C++) 이번 글에서는 그래프를 탐색하는 방법 중 하나인 DFS에 대해 알아본다. 그래프에 대한 간단한 설명을 보고 오면 더 좋다.( [자료구조] 그래프(graph) 개념 : https://085a.tistory.com/8 ) DFS 정의 DFS 장,단점 DFS 탐색 과정 DFS 구현 DFS 정의 DFS는 Depth-First Search의 약자로 깊이 우선 탐색이라고 한다. 그래프에서 깊은 부분을 우선적으로 탐색하는 방법이다. 탐색을 시작할 노드에서 최대로 진입할 수 있는 노드까지 탐색한 뒤 다시 돌아와서 같은 방식으로 탐색한다. DFS 장,단점 DFS의 장점 구현이 단순하다. BFS와 비교하면 적은 저장 공간을 필요로 한다. DFS의 단점 해가 없을 경우 경로 깊게 빠져 시간이 오래 걸릴 수 있다. (탐색 깊.. 2022. 12. 30. 이전 1 2 다음
