Algorithm/AlgorihmFoundation4

• 

  최대공배수_최대공약수(유클리드 호제법(암기)) www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법은 2개의 자연수에 대한 최대공약수를 구하는 알고리즘이다. 호제법이란? => 두 수가 서로 상대방 수를 나누어서 최대공약수를 얻는 것이다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다... Algorithm/AlgorihmFoundation 2020. 12. 19.

• MnimumSpanningTree (Kruskal+Disjoint_set(UnionFind) Union find package AlgorithmFoundation.Minimum_Spanning_Tree; public class UnionFind_Test { static int parent[]=new int[9]; public static void main(String[] args) { // 초기화 과정 for (int i = 1; i x) parent[y]=x; else parent[x]=y; } } public static boolean inSameParent(int x,int y) { x=find(x); y=find(y); if(x==y) { return true; } return false; } public static int find(int x) { if(parent[x]==x) retu.. Algorithm/AlgorihmFoundation 2020. 12. 15.

• Backtracking _N-Queen www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen(해당 코드는 밑에 첨부) 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. N * N 판에 각 행 당 퀸이 있을경우 서로 공격할 수 없게 하는 경우의 수를 구하는 프로그램을 작성하는 것이다. 여기에 퀸의 주 업무는 해당 모든 방향으로 갈 수 있다. 입력 첫째 줄에 N이 주어진다. (1.. Algorithm/AlgorihmFoundation 2020. 11. 23.

• Backtracking-N과 M (1) www.acmicpc.net/step/34 백트래킹 단계 조금 더 복잡한 백트래킹 문제 1 www.acmicpc.net 백트래킹이란? -현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘- -백트래킹은 재귀와 관련이 있다. (n-1개의 관한 것또한 일정한 패턴이 존재) -DFS와 관계가 있다고 생각한다.(깊이우선탐색이 관련이 있는 이유는 해당 수를 계속적으로 재귀적으로 이어가다가 불충족시에는 다시 전단계 또는 전전단계 등... 되돌아오고 다음것으로 다음 안쪽으로 다음 안쪽에 안쪽으로... 불충족하면 돌아가고 충족하면 더 깊이 가다가 일정 조건을 만족한다면 충족이라고 간주 하는 것으로 보이기 때문이다.) 왜 재귀와 관련이 있을까? 예를 들어 설명하자면, 오목을 둘 때 기본적으로 상대방의 다.. Algorithm/AlgorihmFoundation 2020. 11. 23.