반응형 알고리즘3 [JavaScript] 백트래킹(Backtracking) 알고리즘 오늘은 백트래킹(Backtracking, 되추적) 알고리즘에 대해서 공부했다. 백트래킹 알고리즘이란 되추적이라고도 하는데 해를 구하기 위해 모든 경우의 수를 조사하지만 유망한 경우만 검사한다고 생각하면 된다. 흔히들 말하는 '가지치기'이다. 백트래킹은 DFS를 기반으로 만들어진다. 깊이 우선 탐색으로 인해 해당 경우의 수로 탐색하며 내려가다가 해당 노드가 조건에 맞지 않는다고 생각되면 가지치기하듯이 그 경우를 잘라내고 다시 상위 노드로 돌아가 다른 하위 노드로 내려가는 과정을 반복한다. 이를 위해 먼저 DFS를 알아두어야 한다. 백트래킹의 대표적인 예시로는 N-Queen 문제가 있는데 퀸을 어디에 놓느냐에 따라 다음 퀸을 놓을 수 있는 위치에 영향을 끼쳐 백트래킹 기법으로 검사를 하는 것이 가장 좋다. .. 2020. 11. 6. [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. [JavaScript] 소수 판별식 소수(Prime Number)를 판별하는데 여러가지 방법이 있는데 오늘은 내가 알고리즘 공부를 하면서 직접 찾아본 세 가지 방법을 정리하려한다. 1) 직접 나누어서 계산하기 2) N/2 까지만 나누어서 계산하기 3) N의 제곱근 ( √ ) 까지만 나누어서 계산하기 이렇게 세 가지 방법이다. 먼저 첫번째는 가장 간단한 방법인거 같다. 2부터 소수를 판별할 수 있으니 2를 먼저 return 해주고 나머지는 반복문을 이용해 나눠지는 수가 있는지 계산해보고 나눠지만 false를 return 해주고 for문을 빠져나올때까지 나눠지는 수가 없다면 true를 리턴해준다. (이때의 시간복잡도는 O(N) 이다.) function isPrime(num) { if(num === 2) return true; for(let i.. 2020. 9. 10. 이전 1 다음 반응형
