노랑꼬리의 개발 블로그

목차 1. 백트래킹 알고리즘 2. 로직 3. 구현 1. 백트래킹 알고리즘이란? - 모든 경우에 수에 대해 탐색 - 탐색 중에 해당 경로가 해가 될 가능성이 없다면 경로를 되돌아가 다시 결과를 찾는다. (가지치기) - 주로 DFS(깊이 우선 탐색) 방식으로 확인한다. 2. 로직 가. 유망성 검사 - 해가 될 가능성이 있는지 조건을 설정한다. 나. 가지치기 - 유망성 검사를 통해 가능성이 없는 경로를 차단(가지치기) 하여 탐색의 효율성을 높인다. 3. 구현 문제 예시 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. ..

목차 1. 유클리드 알고리즘 2. 로직 3. 구현하기 1. 유클리드 알고리즘이란? - 2개의 자연수 혹은 두 다항식의 최대 공약수를 구하는 방법 - 서로 나누어 해를 구하므로 유클리드 호제법(互除法 : 합(互)하고 나누는(除) 방법(法))이라고도 한다. 2. 로직 가. 최대 공약수 두개의 자연수 a,b (a>b)에 대하여 a를 b로 나눈 나머지가 r일 때, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이에 따라 b와 r에 대해서 나머지 r2를 구하고 r을 r2로 나누는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대 공약수가 된다. 나. 최소 공배수 최소 공배수는 최대 공약수를 이용하여 구할 수 있다. 두개의 자연수 a,b (a>b)에 대하여 a와 b의 최소 공배수는a와 b의 곱을..