Algorithm 뽀개기

최대공약수, 최소공배수 구하기 (유클리드 호제법)

딸기케잌🍓 2022. 7. 22. 00:29

Combination1

package step3_step2;

import java.util.*;

public class Combination1 {
	public static void main(String[] args) {

		int[] nums = {1,2,3,4};

		//1. 조합(Combination) - visit 배열로 사용 여부 체크하는 방법
		boolean[] visit1 = new boolean[nums.length];
		combination1(nums, 4, 2, 0, visit1);
		System.out.println();

		//2 조합(Combination) - 재귀 호출로 사용 여부 결정하는 방법   nCr
//		int[] ans1 = new int[2];
//		combination2(nums, ans1 , 4,2,0,0);	
		
		//3 중복 조합
//        int[] ans2 = new int[2];
//        recombination(nums, ans2, 4 ,2, 0 ,0 );
	}

	//1. 조합(Combination) - visit 배열로 사용 여부 체크하는 방법
	static void combination1(int[] nums, int n , int r , int start , boolean[] visit) {
		if(r == 0) {
			for(int i = 0 ; i < nums.length ; i++ ) {
				if(visit[i]) {
					System.out.print(nums[i] + " ");
				}
			}
			System.out.println();
			return;
		}

//		for(int i = start ; i < nums.length  ; i++ ) {
//			visit[i] = true;
//			combination1(nums, n, r-1 , i+1 , visit);
//			visit[i] = false;
//		}
		
		for(int i = start ; i < nums.length  ; i++ ) {
			System.out.println("r="+ r + " start=" + i + " 함수 호출전 visit 변경 전 " + Arrays.toString(visit));
			visit[i] = true;
			System.out.println("r="+ r + " start=" + i + " 함수 호출전 visit 변경 후 " + Arrays.toString(visit));
			combination1(nums, n, r-1 , i+1 , visit);
			System.out.println("r="+ r + " start=" + i + " 함수 호출후 visit 변경 전 " + Arrays.toString(visit));
			visit[i] = false;
			System.out.println("r="+ r + " start=" + i + " 함수 호출후 visit 변경 전 " + Arrays.toString(visit));
		}
	}
	
	//2 조합(Combination) - 재귀 호출로 사용 여부 결정하는 방법
	static void combination2(int[] nums, int[] ans, int n , int r, int idx, int target) {
		if(r==0) {
			for(int i : ans) {
				System.out.print( i + " ");
			}
			System.out.println();
			return;
		}

		if(target == n) return;
		ans[idx] = nums[target];
		combination2(nums,ans, n , r-1, idx+1, target+1); // 선택
		combination2(nums,ans, n , r, idx, target+1); // 선택 안함
	}

	//3 중복조합(Combination with repetition)
	static void recombination(int[] nums , int[] ans , int n , int r ,int idx , int target ) {
		if( r == 0 ){
			for(int i : ans) {
				System.out.print(i + " ");
			}
			System.out.println();
			return;
		}

		if(target == n) return;
		ans[idx] = nums[target];
		recombination(nums, ans , n , r-1, idx+1, target);
		recombination(nums, ans , n , r , idx , target+1);
	}
}
public class GcdLcm {
	
	 static int gcd(int a, int b) {
		 while(b!=0) {
			 int r=a%b;
			 a=b;
			 b=r;
		 }
		 return a;
	 }
	 
	 static int lcm(int a,int b) {
		 return a*b/gcd(a,b);
	 }

	 public static void main(String[] args) {
		 int a = 8;
		 int b = 4; 
		 System.out.println(gcd(a, b));
		 System.out.println(lcm(a, b));		 
	 }
}
유클리드 호제법
 
2개의 자연수  a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), 
a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고, 
다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 
나누는 수가 a와 b의 최대공약수이다.

 

 

ArrayRotation

package step3_step2;

public class ArrayRotation {

	public int[][] rightRotation90(int [][]A){
		int n = A.length;
		int[][] B = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				//B[i][j] = A[n - 1 - j][i];
				B[j][n-1-i] = A[i][j];
			}
		}

		return B;
	}
	
	public int[][] leftRotation90(int[][] A) {
		int n = A.length;
		int[][] B = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				//B[i][j] = A[j][n -1 -i];
				B[n-1-i][j] = A[j][i];
			}
		}

		return B;
	}
	
	public int[][] Rotation180(int[][] A) {
		int n = A.length;
		int[][] B180 = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				B180[i][j] = A[n - 1 - i][n - 1 - j];
			}
		}

		return B180;
	}
	
	public static void main(String[] args) {
		/*  
        int[][] A = { { 5, 4, 7}, 
					  { 1, 5, 4}, 
					  { 7, 6, 8} };
        */
		
        
        int[][] A = { { 2,7,11,9}, 
					  { 13,8,12,3}, 
					  { 31,18,5,6},
					  {7,17,14,7}};		        
        
        ArrayRotation sol = new ArrayRotation();
        
        int[][] right = sol.rightRotation90(A);
        printAry(right);
        
        int[][] left = sol.leftRotation90(A);
        printAry(left);
        
        int[][] res180 = sol.Rotation180(A);
        printAry(res180);

    }    

	//확인용
    public static void printAry(int[][] array){
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array[i].length; j++){
                System.out.print(array[i][j] + "\t ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

 

 

 

 

DiagonalTravel

import java.util.Arrays;

public class DiagonalTravel {

	public static int[][] solution(int N, int x, int y){
		int [][]answer = new int[N][N];
		int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
		int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};


		answer[x][y] = 1;
		print(answer);

	    
		for (int i=0; i<dx.length; i++) {
		    int nx = x + dx[i];
			int ny = y + dy[i];			
			if ((0<= nx && nx < N) && (0<= ny && ny < N))
			       answer[nx][ny] = 1;
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		int N = 8;
		int x = 3;
		int y = 3;
		int [][]result = solution(N, x, y);
		print(result);

	}

	public static void print(int [][]ta){
		for(int []tmp : ta){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}
}

 

DiagonalTravel1

import java.util.Arrays;

public class DiagonalTravel1 {

	public static int[][] solution(int N, int x, int y){
		int [][]answer = new int[N][N];
		int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
		int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};


		answer[x][y] = 1;
		print(answer);

		for (int c = 1; c < 3; c++) {
			for (int i = 0; i < dx.length; i++) {
				int nx = x + dx[i] * c;
				int ny = y + dy[i] * c;
				if ((0 <= nx && nx < N) && (0 <= ny && ny < N))
					answer[nx][ny] = 1;
			}
			print(answer);
		}

		return answer;
	}
	
	public static void main(String[] args) {
		int N = 8;
		int x = 3;
		int y = 3;
		int [][]result = solution(N, x, y);
		print(result);

	}

	public static void print(int [][]ta){
		for(int []tmp : ta){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}
}

DiagonalTravel1_2

import java.util.Arrays;

public class DiagonalTravel1_2 {

	public static int[][] solution(int N, int x, int y){
		int [][]answer = new int[N][N];
		int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
		int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};


		answer[x][y] = 1;
		print(answer);

		for (int i = 0; i < dx.length; i++) {
			int nx = x;
			int ny = y;

			while (true) {
				nx = nx + dx[i];
				ny = ny + dy[i];

				if (0 > nx || nx >= N || 0 > ny || ny >= N)
					break;

				answer[nx][ny] = 1;
			}
			
			print(answer);

		}

		return answer;
	}
	
	public static void main(String[] args) {
		int N = 8;
		int x = 3;
		int y = 3;
		int [][]result = solution(N, x, y);
		print(result);

	}

	public static void print(int [][]ta){
		for(int []tmp : ta){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}
}

 

 

Permutation1

package step3_step2;
import java.util.*;

public class Permutation1 {
	public static void main(String[] args) {

		int[] nums = {1,2,3,4};
		
		//1 순열(Permutation)  nPr  nP2
		permutation(nums, 4 , 2, 0);
		System.out.println();

		//2 순열(Permutation) visit 사용
		boolean[] visit2 = new boolean[nums.length];
		LinkedList<Integer> ansList1 = new LinkedList<>();
		permutation2(nums , 4 , 2 , ansList1 , visit2);
		System.out.println();

		//3 증복 순열(Permutation with Repetition)
//		LinkedList<Integer> ansList2 = new LinkedList<>();
//		repermutation(nums , 4 , 2, ansList2);
	}	

	//1 순열(Permutation) 
	static void permutation(int[] nums, int n , int r , int depth ) {		
		if(depth == r) {
			for(int i =0 ; i < r ; i++ ) {
				System.out.print(nums[i] + " ");
			}
			System.out.println();
			return;
		}

		for(int i = depth ; i < n ; i++ ) {
			swap(nums, depth , i);
			permutation(nums ,n , r, depth+1);
			swap(nums, depth , i);			
		}
		
//		for(int i = depth ; i < n ; i++ ) {
//			System.out.println("[함수 호출 전] swap 전 " + depth + " " + i + " " + Arrays.toString(nums));
//			swap(nums, depth , i);
//			System.out.println("[함수 호출 전] swap 후 " + depth + " " + i + " " + Arrays.toString(nums));
//			permutation(nums ,n , r, depth+1);
//			System.out.println("[함수 호출 후] swap 전 " + depth + " " + i + " " + Arrays.toString(nums));			
//			swap(nums, depth , i);
//			System.out.println("[함수 호출 후] swap 전 " + depth + " " + i + " " + Arrays.toString(nums));
//			
//		}
	}
	static void swap(int[] nums, int a, int b) {
		int temp = nums[a];
		nums[a] = nums[b];
		nums[b] = temp;
	}

	
	//2 순열(Permutation) visit 사용
	static void permutation2(int[] nums , int n , int r , LinkedList<Integer> ansList , boolean[] visit ) {
		if(ansList.size() == r) {
			for(int i : ansList) {
				System.out.print(i + " ");
			}
			System.out.println();
			return;
		}

		for(int i = 0 ; i < n ; i ++) {
			if(!visit[i]) {
				visit[i] = true;
				ansList.add(nums[i]);
				permutation2(nums, n , r, ansList, visit);
				visit[i] = false;
				ansList.removeLast();
			}
		}
	}
	

	//3 증복 순열(Permutation with Repetition)
	static void repermutation(int[] nums , int n , int r , LinkedList<Integer> ansList) {
		if(ansList.size() == r) {
			for(int i : ansList) {
				System.out.print(i + " ");
			}
			System.out.println();
			return;
		}

		for(int i = 0 ; i < n ; i ++) {
			ansList.add(nums[i]);
			repermutation(nums, n , r, ansList);
			ansList.removeLast();
		}
	}

}

 

 

TwoArray

package step3_step2;

import java.util.Arrays;

public class TwoArray {

	public static void main(String[] args) {
		int N = 7;
		int [][]ta = new int[N][N];
		ta[3][2] = 1;
		
		int posx = 3;
		int posy = 2;
		
		int num = 2;
		
		int []dx = {-1, 1, 0, 0};
		int []dy = { 0, 0, -1,1};
		
		print(ta);
		
		
		for (int d = 1; d <= num; d++) {
			for (int i = 0; i < 4; i++) {
				int nx = posx + dx[i]*d;
				int ny = posy + dy[i]*d;
				
				if(nx >= 0 && nx < N && ny >= 0 && ny < N){
					ta[nx][ny] = 1;
				}	
				print(ta);
			}
						
		}	
	}
	
	public static void print(int [][]ta){
		for(int []tmp : ta){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}

}

TwoArray2_1

package step3_step2;

import java.util.Arrays;

public class TwoArray2_1 {

	public static void main(String[] args) {
		int N = 9;
		int [][]table = new int[N][N];
		
		
		String pos = "d4";
		
		table[(pos.charAt(0)-'a')][(pos.charAt(1)-'0')] = 1;
		
		int num = 3;
		
		int []dx = {-1, 1, 0, 0};
		int []dy = { 0, 0, -1,1};
		
		print(table);		
		
		for (int d = 1; d <= num; d++) {
			for (int i = 0; i < 4; i++) {
				int nx = (pos.charAt(0)-'a') + dx[i]*d;
				int ny = (pos.charAt(1)-'0') + dy[i]*d;
				
				if(nx >= 0 && nx < N && ny >= 0 && ny < N){
					table[nx][ny] = 1;
				}
				print(table);	
			}
					
		}	
	}
	
	public static void print(int [][]table){
		for(int []tmp : table){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}

}

TwoArray2_2

package step3_step2;

import java.util.Arrays;

public class TwoArray2_2 {

	public static void main(String[] args) {
		int N = 9;
		int [][]table = new int[N][N];
		
		
		String pos = "4e";
		
		System.out.println((pos.charAt(0)-'0'));
		
		table[(pos.charAt(0)-'0')][(pos.charAt(1)-'a')] = 1;
				
		int []dx = {-1, 1, 0, 0};
		int []dy = { 0, 0, -1,1};
		
		print(table);	
		
		
		for (int i = 0; i < 4; i++) {	
			char r = pos.charAt(0);
			char c = pos.charAt(1);		
			
			while(r>='0' && r <='8' && c >= 'a' && c <= 'i'){				
				table[r-'0'][c-'a'] = 1;
				r = (char)(r + dx[i]);
				c = (char)(c + dy[i]);				
			}			
			print(table);			
		}	
	}
	
	public static void print(int [][]table){
		for(int []tmp : table){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}

}

TwoArray2_3

package step3_step2;

import java.util.Arrays;

public class TwoArray2_3 {

	public static void main(String[] args) {
		int N = 9;
		int [][]table = new int[N][N];
		
		
		String pos = "d4";
		
		table[(pos.charAt(0)-'a')][(pos.charAt(1)-'0')] = 1;
		
		int num = 3;
		
		int []dx = {-1, 1, 0, 0};
		int []dy = { 0, 0, -1,1};
		
		print(table);
		
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			char r = pos.charAt(0);
			char c = pos.charAt(1);	
			
			while(r>='a' && r <='i' && c >= '0' && c <= '8'){	
				cnt++;
				table[r-'a'][c-'0'] = 1;
				r = (char)(r + dx[i]);
				c = (char)(c + dy[i]);
				
				if(cnt == num){
					cnt = 0;
					break;
				}
			}			
			print(table);			
		}	
	}
	
	public static void print(int [][]table){
		for(int []tmp : table){
			System.out.println(Arrays.toString(tmp));
		}		
		System.out.println();
	}

}


/*
 * �ٸ� �ڵ��� ������ ����ϸ�, TwoArray2_1.java �ڵ��� ���ó�� ���ѵ� ������ŭ �����¿�� 1�� ä����� �� ��
 * ī��Ʈ �� �� �ִ� ������ �ϳ��� �� �� ���� �ִٴ� ���� �ڵ��� ���̹Ƿ� �����ϼ���.
 * 
 */

'Algorithm 뽀개기' 카테고리의 다른 글

<COS Pro 1급 Java> [1차 #4번 문제] 타임머신  (0) 2023.09.28
[Algorithm] 시간복잡도 Big-O 표기법  (0) 2021.04.15

'Algorithm 뽀개기'의 다른글

  • 현재글최대공약수, 최소공배수 구하기 (유클리드 호제법)

관련글

티스토리툴바