반응형 알고리즘 공부5 [JavaScript] 백트래킹(Backtracking) 알고리즘 오늘은 백트래킹(Backtracking, 되추적) 알고리즘에 대해서 공부했다. 백트래킹 알고리즘이란 되추적이라고도 하는데 해를 구하기 위해 모든 경우의 수를 조사하지만 유망한 경우만 검사한다고 생각하면 된다. 흔히들 말하는 '가지치기'이다. 백트래킹은 DFS를 기반으로 만들어진다. 깊이 우선 탐색으로 인해 해당 경우의 수로 탐색하며 내려가다가 해당 노드가 조건에 맞지 않는다고 생각되면 가지치기하듯이 그 경우를 잘라내고 다시 상위 노드로 돌아가 다른 하위 노드로 내려가는 과정을 반복한다. 이를 위해 먼저 DFS를 알아두어야 한다. 백트래킹의 대표적인 예시로는 N-Queen 문제가 있는데 퀸을 어디에 놓느냐에 따라 다음 퀸을 놓을 수 있는 위치에 영향을 끼쳐 백트래킹 기법으로 검사를 하는 것이 가장 좋다. .. 2020. 11. 6. [JavaScript] DFS와 BFS에 대해서 오늘은 DFS와 BFS에 대해서 알아보았다. DFS와 BFS는 그래프를 순회하며 탐색하는 알고리즘으로 DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색으로 DFS는 Depth-First Search BFS는 Breadth-First Search를 뜻한다. 그래프란 정점과 간선으로 이루어진 자료구조의 일종으로 그래프를 탐색한다는 것은 어느 특정한 정점을 시작으로 모든 정점을 방문하는 것을 뜻한다. 그래프 더 알아보기 [Data-Structure] Graph (그래프) 오늘은 비선형 구조 중 하나인 그래프(Graph)에 대해서 공부했다. 그래프(Graph)는 노드(Node, 또는 정점 -vertex- 이라고도 부른다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된다. 그래프는 ant-progr.. 2020. 11. 5. [C++] 삽입 정렬(Insertion sort) 알고리즘 오늘은 삽입 정렬 알고리즘을 C++ 을 이용하여 구현해보았다. 삽입 정렬 알고리즘은 두 번째 원소부터 검사를 하는데 현재 값과 이전 값을 이중 포문을 이용하여 검사 후 이전 값이 현재 값보다 더 크다면 오른쪽으로 이동하여 정렬을 진행한다. #include #include void inser_sort(int ans[], int n) { int i, j, temp; for (i = 1; i = 0 && ans[j] > temp; j--) // 현재 값과 이전 값 비교 후 이전값이 더 크다면 오른쪽으로 이동 { ans[j + 1] = ans[j]; } ans[j + 1] = temp; /.. 2020. 9. 14. [C++] 이분 탐색(Binary Search) 오늘은 C++ 로 이분 탐색 알고리즘에 대해서 알아보았다. 이분 탐색은 미리 정렬되어 있는 배열에서 탐색 범위를 계속해서 줄여가면서 탐색하고자 하는 값을 찾아가는 알고리즘이다. 정렬된 배열에서 중간값과 찾고자 하는 값을 비교하여 찾고자 하는 값보다 중간값이 크다면 범위를 왼쪽으로 줄이고 찾고자 하는 값보다 중간값이 더 작다면 범위를 오른쪽으로 줄이면서 탐색 범위를 좁혀나가면 된다. #include int BinSearch(int *arr, int n, int key) { int start = 0; int end = n - 1; int mid; do { mid = (start + end) / 2; //중앙 값 if (arr[mid] == key) //key값을 찾았을때의 index 반환 return mid.. 2020. 9. 14. 이전 1 2 다음 반응형
