알고리즘7 [알고리즘] 완전 탐색(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. 백준 2638번: 치즈 (c++) 문제 : https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 해석 N x M의 모눈종이에 치즈가 표시되어 있다. 치즈의 4변중 2변 이상이 외부 공기와 접촉하면 한 시간 뒤에 녹아 없어진다. 주어진 치즈가 모두 녹아 없어지는데 걸리는 시간을 출력한다. 첫 째 줄에는 모눈 종이의 크기를 나타내는 N, M을 입력한다. ( 5 = N || visited[ny][nx]) continue; if (map[ny][nx] == 0) { q.p.. 2023. 1. 5. 백준 1260번: DFS와 BFS (c++) 문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해석 조건에 맞게 DFS와 BFS를 구현하면 되는 문제이다. 풀이 이 문제에서 주의해야 할 점은 두 가지이다. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 DFS 실행 후 방문을 체크하는 배열(visited)을 false로 초기화 후 BFS 실행 1번 해결 : graph를 정렬하여 번호가 작은 것부터 방문하도록 하.. 2023. 1. 4. 이전 1 2 다음
