Algorithm (12) 썸네일형 리스트형 [Algorithm] 백트래킹(Backtracking) 백트래킹(Backtracking) ? 백트래킹은 '가능한 모든 방법을 탐색한다'는 기본 아이디어에서 나온다. 브루트 포스 알고리즘과의 차이는 브루트 포스의 경우 모든 경우를 전부 시도해보는 방식이라면, 백트래킹의 경우 탐색을 진행하면서, 조건에 맞지 않는 부분을 제외하며 진행하는데에 차이가 있다. DFS는 현재 지점에서 방문할 곳이 있다면, 재귀 호출을 이용하여 계속 이동하게 되는데, 모든 곳을 방문하기 때문에, 목표지점이 있지 않는 경로에 빠져, 비효율적인 결과를 초래할 수 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 가지치기를 얼마나 잘하느냐에 따라 시간이 많이 단축이 될 수가 있으니, 반복적인 연습을 통해 조건.. [Algorithm] 동적 계획법(Dynamic Programming) # 동적 계획법이란? - 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. - 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘. # 메모이제이션 (Memoization) - 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다. 동적 계획법의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이다. [Algorithm] 유클리드 호제법 1. 개요 - 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나. 2. 방법 1. 입력으로 두 수 m,n(m>n)이 들어온다. 2. n이 0이라면, m을 출력하고 알고리즘을 종료한다. 3. m이 n으로 나누어 떨어지면 n을 출력하고 알고리즘을 종료한다. 4. 그렇지 않으면 m을 n으로 나눈 나머지를 새롭게 m에 대입하고 , m과 n을 바꾸고 3번으로 돌아온다. 3. 구현 - C++ int gcd(int a, int b) { int c; while(b) { c = a % b; a = b; b = c; } return a; } 4. 예시 문제 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는.. [Algorithm] 에라토스테네스의 체 1. 개요 - 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(primary number)를 찾는 방법이다. 마치 체를 치듯 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다고 함. - 임의의 자연수 n에 대하여 그 이하의 소수를 찾는 가장 간단하고 빠른 방법. 2. 방법 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열 한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. ...... 위 과정을 반복하면 구간의 모든 소수가 남는다. 3. 구현 - C++ void Eratos(int n) { /* 만일 n이 1보다 작거나 같으.. 이전 1 2 다음
