최대공약수 최소공배수 구하기



최대공약수 접근방법


1. 최대공약수는 두개의 값을 받아 두개의 값 모두 같은 수로 나누어 나머지가 0이 되는 공통되는 수를 찾는 것을 말한다.


2. 두 수 value1, value2 (15, 35) 를 받고 2개의 수를 비교해 작은 수(15)를 변수(a)에 담고  


3. value1과 value2를 각각 변수(a)로 나누었을때 ( value1 % 변수a == 0 ) && ( value2 % 변수a == 0 ) 둘다 나머지가 0이 나오면 


4. 최대공약수이다. 둘다 나머지가 0 이 나오지 않으면 둘다 나머지가 0이 나올 때 까지 변수a값을 -1 씩 감소시키며 반복한다.




유클리드 접근방법


1. 재귀 형식으로 접근한다.


value1과 value2 값을 받아 앞의값 % 뒤에값이 0 이 나오지 않으면 반복한다.

나머지가 0이 나오면 최대공약수를 리턴한다.


myMethod2(value2, value1%value2)




최소공배수 접근방법


1.  value1 * value2 / 앞서 구한 최대공약수 = 최소공배수이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package test1;
 
import java.util.Scanner;
 
public class Gcd_Lcm {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner scan = new Scanner(System.in);
         
        System.out.println("숫자 2개 입력:");
 
        int value1, value2;
        value1 = scan.nextInt();
        value2 = scan.nextInt();
                
        pubMethod1 pub_method1 = new pubMethod1();
        
        // gcb
        pub_method1.myMethod1(value1, value2);
        System.out.println("gcb(최대공약수): "+pub_method1.myMethod1(value1, value2));
        
        // 유클리드
        pub_method1.myMethod2(value1, value2);
        System.out.println("유클리드: "+pub_method1.myMethod2(value1, value2));
        
        // lcm
        pub_method1.myMethod3(value1, value2);
        System.out.println("lcm(최소공배수): "+pub_method1.myMethod3(value1, value2));
    }
 
}
 
class pubMethod1{
    
    // 1. 일반적인 gcb(최대공약수) 구하기
    public int myMethod1(int value1, int value2){
        int minNum1 = Math.min(value1,value2);
        while(true){
            if(value1%minNum1==0 && value2%minNum1==0){
                return minNum1;
            }
            minNum1-=1;
        }
    }
    
    // 2. 유클리드 알고리즘
    // gcb(a,b) = gcb(b, a%b)
    public int myMethod2(int value1, int value2){ // 40 20
        if(value2==0){
            return value1;
        }else{
            return myMethod2(value2, value1%value2); // 20 , 40 / 20 
        }
    }
    
    // 3. lcm(최소공배수) 구하기
    public int myMethod3(int value1, int value2){
        return value1 * value2 / myMethod1(value1, value2);
    }
    
}
cs


출력 결과



마지막으로 해당 소스를 첨부한다.


Gcd_Lcm.java



'전체 > 알고리즘' 카테고리의 다른 글

기본적인 알고리즘 문제 풀기(Project Euler) - 1  (0) 2017.12.14
문자열 거꾸로 출력하기  (0) 2017.12.13
하노이의 탑 구현  (0) 2017.12.12
자바 배열 최대값 구하기, 배열 중복되는 값 구하기  (0) 2017.12.12
피보나치 수열 구현 두가지 방법  (0) 2017.12.11


하노이의 탑


원반이 n개인 하노이 탑이 어떻게 이동되는지 몇번 이동하는지 구해보자.



조건


하노이의 탑은 다음과 같이 크기 가 다른 원반이 한 기둥에 놓여져 있고 


원반을 모두 왼쪽에서 오른쪽으로 옮겨야 한다.


원반은 큰 것이 아래로 가게 쌓아야 하며 작은 원반 위에 큰 원반이 올 수 없다.


원반을 옮길 때에는 가장 위에 쌓여있는 원반 부터 옮겨야 한다.




1. 원반이 1개 일때


1번에서 3번으로 옮기면 된다.



2. 원반이 2개 일때


1번 기둥의 맨 위에 있는 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )


1번 기둥의 마지막 남아있는 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )


2번 기둥에 있는 원반 하나를 3번 기둥에 옮긴다. ( 2 -> 3 )



3. 원반이 3개 일때


1. 1번 기둥의 가장 작은 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )


2. 1번 기둥의 중간 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )


3. 3번 기둥의 가장 작은 원반 하나를 2번 기둥에 옮긴다 ( 3 -> 2 )


4. 1번 기둥의 가장 큰 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )


5. 2번 기둥에 가장 작은 원반 하나를 1번 기둥에 옮긴다. ( 2 -> 1 )


6. 2번 기둥에 중간 원반 하나를 3번 기둥에 옮긴다. ( 2 > 3 )


7. 1번 기둥에 가장 작은 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )


총 7번 옮김



4. 원반이 n개 일때


1번 기둥에 있는 n-1개 원반을 2번 기둥에 옮긴다.


1번 기둥에 가장 큰 원반을 3번 기둥으로 옮긴다.


2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.



소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package test1;
 
public class Hanoi {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("n=3");
        MyHanoi myHanoi = new MyHanoi();
        
//        myHanoi.hanoiFunction(3, 1, 2, 3);
        System.out.println("총 옮긴 횟수: "+myHanoi.hanoiFunction(3, 1, 2, 3)); // 2의 n제곱 - 1 = 옮긴 횟수
    }
}
class MyHanoi{
    int count = 0 ;
    int hanoiFunction(int n, int first, int second, int third) { 
        if(n==1){
            System.out.println(first+"->"+third); 
            count++;
            return count;
        }
        hanoiFunction(n-1, first, third, second);  
        System.out.println(first+"->"+third); 
        count++; 
        hanoiFunction(n-1, second, first, third); 
        
        return count;
    }    
}
cs



출력결과


마지막으로 해당 소스를 첨부한다.


Hanoi.java





'전체 > 알고리즘' 카테고리의 다른 글

문자열 거꾸로 출력하기  (0) 2017.12.13
최대공약수 최소공배수 구하기  (0) 2017.12.13
자바 배열 최대값 구하기, 배열 중복되는 값 구하기  (0) 2017.12.12
피보나치 수열 구현 두가지 방법  (0) 2017.12.11
n값을 받아 1부터 n까지의 합계 구하기  (0) 2017.12.11


배열에서 최대값 구하기



접근방법


1. 배열의 첫번째 index에 해당하는 값에 max value 라고 변수 지정해준다.


2. max value 변수를 배열의 길이만큼 하나하나 비교한다.


3. 비교해서 기존의 max value보다 배열의 index에 해당하는 값이 크면 max value에 값을 바꿔준다.


4. 반복을 다 돌면 배열에서 가장 큰 값이 max value가 된다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package test1;
 
public class MaxValue {
 
    public static void main(String[] args) {
        
        int[] value = {10,5,2,7,15,30,50,100,150,3,5,7};
        int valueLength =value.length;
        int maxValue = value[0];
        int maxIdx = 0;
                
        MyMethod1 mymethod1 = new MyMethod1();
        System.out.println(mymethod1.findMaxValue(value, valueLength, maxValue));
        
        System.out.println(mymethod1.findMaxNumber(value, valueLength, maxIdx));
 
    }
 
}
 
 
class MyMethod1{
    
    // 최대값 구하기
    int findMaxValue(int[] value,int valueLength, int maxValue){
        for(int i=0; i<valueLength; i++){
            if(value[i] > maxValue){
                maxValue = value[i];
            }
        }
        
        return maxValue;
    }
    
    // 최대값의 배열Index 구하기
    int findMaxNumber(int[] value,int valueLength, int maxIdx){
        for(int i=0; i<valueLength; i++){
            if(value[i] > value[maxIdx]){
                maxIdx = i;
            }
        }
        return maxIdx;
    }
    
}
cs


같은 방식으로 최대값의 Index값도 확인 할 수 있다.


출력결과



배열에서 중복되는 값 구하기


접근방법


1. value 배열의 John값을 Eric, Mike, Kelly ... 마지막 원소의 값까지 1:1 비교한다.


2. String 값이 같은 것은 John, Mike , Kelly


3. 2번째 Eric을 Mike Kelly ... 순으로 비교


4. 자기자신과는 비교하지 않고 자기 다음 이름과 비교만 하면 된다.


5. 이름이 같다면 배열에 추가



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package test1;
 
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
 
public class SameNameFind {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] value = {"John","Eric","Mike","Kelly","Mike","Tom","Kelly","Henly","John"};
        int valueLength = value.length;
    
        findNameMethod findnamemethod = new findNameMethod();
        System.out.println(findnamemethod.findSameName(value, valueLength));
        findnamemethod.findSameName2(value, valueLength);
        
    }
 
}
 
/*
 * 1. value 배열의 John값을 Eric, Mike, Kelly ... 마지막 원소의 값까지 1:1 비교한다.
 * 2. String 값이 같은 것은 John, Mike , Kelly
 * 3. 2번째 Eric을 Mike Kelly ... 순으로 비교
 * 4. 자기자신과는 비교하지 않고 자기 다음 이름과 비교만 하면 된다.
 * 5. 이름이 같다면 배열에 추가
 * 
 */
 
 
class findNameMethod{
    
    // 배열에서 중복되는 값 찾아 존재하면 중복되는 값 새 배열에 추가
    ArrayList<String> listA = new ArrayList<String>();
    ArrayList<String> findSameName(String[] value, int valueLength){
        for(int i=0; i<valueLength-1; i++){// 자기 자신을 제외한 모든 이름 비교
            for(int j=i+1; j<valueLength; j++){ // 앞에 비교한 이름을 비교하지 않는다.
                if(value[i] == value[j]){
                    listA.add(value[i]); // 같으면 추가한다.
                }
            }
        }
        return listA;
    }    
    
    // 각각 어떻게 비교하는지 확인
    void findSameName2(String[] value, int valueLength){
        for(int i=0; i<valueLength-1; i++){// 자기 자신을 제외한 모든 이름 비교
            for(int j=i+1; j<valueLength; j++){ // 앞에 비교한 이름을 비교하지 않는다.
                System.out.println(value[i]+","+value[j]);
            }
        }
    }    
}
cs


출력결과



배열에서 중복되는 값이 무엇인지, 어떻게 비교하는지 출력결과를 통해 알수 있었다.


마지막으로 해당 소스를 첨부한다.



MaxValue.java

SameNameFind.java




'전체 > 알고리즘' 카테고리의 다른 글

문자열 거꾸로 출력하기  (0) 2017.12.13
최대공약수 최소공배수 구하기  (0) 2017.12.13
하노이의 탑 구현  (0) 2017.12.12
피보나치 수열 구현 두가지 방법  (0) 2017.12.11
n값을 받아 1부터 n까지의 합계 구하기  (0) 2017.12.11



피보나치 수열이란?


피보나치 수열은 앞의 두 개의 수를 더한 값을 다음 값으로 넣는 방식이다.


예를 들어 다음과 같이 리스트에 숫자 2개 0,1 이 있다고 해보자.

그다음 숫자는 0과 1을 더한 1이 리스트에 추가된다. 그다음 숫자는 1과 1을 더한 2가 리스트에 추가된다.


0, 1 then  0+1 = 1 


then 0, 1, 1


0, 1, 1 then 1+1 = 2


then 0, 1, 1, 2


0, 1, 1, 2 then 1+2 = 3


then 0, 1, 1, 2, 3 ...


이런 방식으로 추가하면 다음과 같은 리스트가 될 것이다.


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...


피보나치 수열 구현하는 방식을 두 가지 방법으로 표현하였다.


1. Binary Recursive (이진 재귀)

2. Tail-end Recursive (꼬리 재귀)





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package test1;
 
public class Pibonachi {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyFib1 myfib1 = new MyFib1();    
        System.out.println("myfib1 value: "+myfib1.fib(5));
        
        MyFib2 myfib2 = new MyFib2();
        System.out.println("myfib2 value: "+myfib2.fib(5));
        
    }
}
 
 
// 피보나치 수열 두가지 방법
 
// 1. Binary Recursive 이진 재귀
// f(n) = f(n - 1) + f(n - 2) 재귀 함수를 두번 실행 
class MyFib1{
    public int fib(int n) {
        if (n < 2){
            return n;
        }else{
            System.out.println("call fib("+(n-1)+")"+"+"+"call fib("+(n-2)+")");
            return fib(n - 1) + fib(n - 2); 
        }
    }    
}
 
// (F(n)) 실행 시간에 실행되며, Ω(1.6n)의 시간을 갖는다.
 
 
// 2. Tail-end Recursive 꼬리 재귀
// f(n - 1, fibo1 + fibo2, fibo1)로 재귀함수를 한 번만 실행
class MyFib2{
    long fib(long n) {
        return fibo_iter(n, 0, 1);
    }
    
    long fibo_iter(long x, long a, long b) { // 5, 0, 1
        if (x==0) return a;
        else return fibo_iter(x-1, b, a+b); // 4, 1, 1 // 3, 1, 2 //  2, 2, 3 // 1, 3, 5 // 0, 5, 8 => 5
    }            
}
 
// Θ(n) 실행 시간에 실행된다.
 
cs


1번 Binary Recursive에 경우 함수안의 자신의 함수를 2번 부른다.


받는 숫자 n이 커질수록 재귀 호출을 두 번 이상 부르므로 함수 호출 횟수가 방대하게 증가하는 문제가 발생하고, 


재귀 호출 깊이가 깊어지면 Stack을 많이 사용하는 문제가 발생한다.



2번 Tail Recursive에 경우 함수안의 자신의 함수를 1번 부른다.


Tail Recursion 를 쓰거나 반복 방식을 사용하면 Binary Recursive의 시간복잡도 및 Stack 사용을 줄일 수 있다.



마지막으로 소스를 첨부한다.


Pibonachi.java




'전체 > 알고리즘' 카테고리의 다른 글

문자열 거꾸로 출력하기  (0) 2017.12.13
최대공약수 최소공배수 구하기  (0) 2017.12.13
하노이의 탑 구현  (0) 2017.12.12
자바 배열 최대값 구하기, 배열 중복되는 값 구하기  (0) 2017.12.12
n값을 받아 1부터 n까지의 합계 구하기  (0) 2017.12.11



스택을 이용한 n값을 받아 1부터 n까지의 합계 구하기 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package test1;
 
public class StackProblem {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MySum1 mysum1 = new MySum1();
        System.out.println(mysum1.sum(10000)); // StackOverFlow Error
        
        MySum2 mysum2 = new MySum2();
        System.out.println(mysum2.sum(10000));
        
    }
}
 
// 1부터 n까지의 재귀함수 호출의 합
class MySum1{
    int sum(int n) {
        if (n < 2)
            return n;
        return n + sum(n - 1);
    }    
}
 
// 1부터 n까지의 반복을 사용한 합 
class MySum2{
    int sumResult = 0;
    int sum(int n){
        while(n >= 0) {
            sumResult += n--;
        }        
        return sumResult;
    }    
}
cs


스택을 이용해 n값을 받으면 1부터 n값까지의 합계를 출력하는 소스이다.


예) n을 10으로 받으면 1부터 10까지 더해 값이 55가 나온다.



출력 값은 다음과 같다.







합계를 구하는 메소드는 총 2개(재귀함수 호출 function, 반복을 사용한 function) 로 나눠서 만들었다.



1. 1부터 n까지 재귀함수를 호출한 합



n값이 큰 상태에서 재귀함수를 호출해 합계를 하면 어느정도 숫자가 커지게 되었을 때 




다음과 같이 StackOverflowError가 발생하게 된다.


스택에 모두 담지 못하기 때문에 에러가 발생한 것이다.




2. 1부터 n까지 반복을 사용한 합



2번째 메소드는 에러를 발생시키지 않고 값이 나오는 것을 확인했다.


마지막으로 해당소스를 첨부한다.


StackProblem.zip


'전체 > 알고리즘' 카테고리의 다른 글

문자열 거꾸로 출력하기  (0) 2017.12.13
최대공약수 최소공배수 구하기  (0) 2017.12.13
하노이의 탑 구현  (0) 2017.12.12
자바 배열 최대값 구하기, 배열 중복되는 값 구하기  (0) 2017.12.12
피보나치 수열 구현 두가지 방법  (0) 2017.12.11

+ Recent posts

티스토리툴바