알고리즘 공부 뿌셔!

알고리즘이란?

어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.
언젠가는 끝나야 하는 속성을 가지고 있다

알고리즘의 조건

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다
유한성 : 유한 번의 명령어를 수행 후에 종료한다
효율성 : 모든 과정은 명백하게 실행 가능한 것이어야 한다.

최댓값,최솟값,중앙값

public static int max(int a, int b, int c) {
        int max = a;
        if (b > max) {
            max = b;
        }
        if (c > max) {
            max = c;
        }
        return max;
    }
    public static int min(int a, int b, int c) {
        int min = a;
        if (b < min) {
            min = b;
        }
        if (c < min) {
            min = c;
        }
        return min;
    }
    
    public static int mid(int a, int b, int c) {
        if (a >= b)
            if (b >= c)
                return b;
            else if (a <= c)
                return a;
            else
                return c;
        else if (a > c)
            return a;
        else if (b > c)
            return c;
        else
            return b;
    }

중앙값의 경우 매우 복잡하다.
경우의 수가 13가지나 되기 때문에 복잡할 수 밖에 없다
아래는 중앙값을 구하는 방식을 보기좋게 구현해놓았다 위랑 비교 했을때 효율이 떨어지는데 그 이유는 ?

public static int mid(int a, int b, int c) {
       if((b >= a && c <= a) || (b <= a && c >= a))
       	return a;
       if((a > b && c < b ) || (a < b && c > b))
       	return b;
       return c;
    }

개인적인 생각일 수도 있지만 위 중앙값에서 return c; 에 도달하기 위해선 모든 경우의 수를 다 돌려봐야한다.
하지만 기존의 중앙값구하기에선 맨처음 if()문에서 false가 나오면 그안의 조건문은 실행하지 않기에 효율적인 면에서 좋은것 같다.

for,while 문

n이 7이면 1+2+3+4+5+6+7 = 28 로 출력 프로그램 작성

public static void Q7(int a) {
        int result = a;
        for (int i = 1; i < a; i++) {
            result += i;

            System.out.print(i + " + ");
        }

        System.out.print(a + " = " + result);

    }

1부터 10까지 합은 (1 +10) * 5 같은 방식으로 구할수 있습니다. 가우스의 덧셈이라는 방식을 이용하여 1부터 n 까지의 정수 합을 구하는 프로그램 작성

public static void Q8(int a) {

        int result = (1 + a) * (a / 2);
        if (a % 2 != 0) { // 홀수의 경우 가우스의 덧셈을 할때 (1 + a) /2 값을 넣어줘야 올바른 값을 도출
            result += (1 + a) / 2;
        }
        System.out.println(result);
    }

정수 a,b를 포함하여 그 사이의 모든 정수의 합을 구하여 반환하는 메서드 작성

public static void Q9(int a, int b) {
        int max = (a > b) ? a : b;
        int min = (a < b) ? a : b;
        int result = 0;
        for (int i = min; i <= max; i++) {
            result += i;

        }
        System.out.println(result);
    }

a,b 정수를 입력받고 b-a를 출력하세요 But b가 작은경우 다시 입력받으세요

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("a의 값:");
        int a = sc.nextInt();

        int b;
        do {

            System.out.print("b의 값:");
            b = sc.nextInt();
            if (b < a) {
                System.out.print("a보다 큰값을 입력하세요");
            }
        } while (b < a);

        System.out.print("b -a 는 " + (b - a) + "입니다.");
    }

양의 정수를 입력받고 자리수를 출력하는 프로그램 작성

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("a의 값:");
        int a = sc.nextInt();
        int count = 1;
        while (a > 9) {
            a /= 10;
            count++;
        }
        System.out.print(count);

    }

Q12 곱셈표만들기

public static void Q12() {
        System.out.print(" |  1  2  3  4  5  6  7  8  9\n");
        System.out.print("-+--------------------------\n");
        for (int i = 1; i < 10; i++) {
            System.out.print(i + "|");
            for (int j = 1; j < 10; j++) {
                System.out.printf("%3d", i * j);

            }
            System.out.println("");
        }
    }

Q13 덧셈표만들기

public static void Q13() {
        System.out.print(" |  1  2  3  4  5  6  7  8  9\n");
        System.out.print("-+--------------------------\n");
        for (int i = 1; i < 10; i++) {
            System.out.print(i + "|");
            for (int j = 1; j < 10; j++) {
                System.out.printf("%3d", i + j);

            }
            System.out.println("");
        }
    }

Q14 입력받은 숫자로 정사각형 표시 *로

public static void Q14(int a) {

        for (int i = 0; i < a; i++) {

            for (int j = 0; j < a; j++) {
                System.out.print("*");

            }
            System.out.println("");
        }
    }

Q15 직각 이등변 삼각형 출력

public static void Q15(int a) {
        
        for (int i = 1; i <= a; i++) {

            for (int j = 1; j <= i; j++) {
                System.out.print("*");

            }
            System.out.println("");
        }
    }

Q16 피라미드 출력

 public static void Q16(int a) {
        int count = 2 * a - 1;

        for (int i = 1; i <= a; i++) {
            int countStar = 2 * i - 1;
            for (int j = 0; j < count; j++) {
                if (a - i > j) {
                    System.out.printf(" ");
                } else if (a - i <= j && countStar > 0) {
                    System.out.printf("*");
                    countStar--;
                }

            }
            System.out.println("");

        }
    }

Q17 숫자 피라미드 출력

public static void Q17(int a) {
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= a - i; j++) {
                System.out.print(" ");
            }
            for (int j = 1; j <= 2 * i - 1; j++) {
                System.out.printf("%d", i);
            }
            System.out.println("");

        }

    }

for문 두개를 쓰면 비교적 간단해짐

자료구조

데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계

배열

각각의 방이 존재하며 줄수에 따라 1차원 배열 2차원 배열로 불린다.

선언 int[] a = new int[5];
길이 a.length == 5;
선언시 초깃 값은 0으로 고정된다. (배열의 구성요소와 클래스의 필드는 초깃값으로 초기화 되나 지역변수는 X)
선언,초기화 int[] a = {1,2,3,4,5} or new int[] {1,2,3,4,5};
복제 a.clone()

접근제한자

public : 모든 접근 허용
protected: 같은 패키지의 객체,상속 관계의 객체 허용
default : 같은 패키지의 객체 허용
private : 현재의 객체 안에서만 허용

접근 제한자 사용

class : public,default
생성자 : *
멤버 변수 : *
멤버 메서드 : *
지역 변수 : 사용불가능

Q2 배열 역순

public static void main(String[] args) {
        Random rand = new Random();
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        int[] a = new int[num];
        for (int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt(10);
        }
        for (int i = 0; i < a.length / 2; i++) {
            for (int j = 0; j < a.length; j++) {
                System.out.printf("%d ", a[j]);
            }
            System.out.println("");
            int temp = a[i];
            a[i] = a[a.length - i - 1];
            a[a.length - i - 1] = temp;

            System.out.printf("a[%d]와 a[%d]를 변경했습니다.\n", i, a.length - 1 - i);

        }
        System.out.println("역순 끝");

    }

6
4 9 8 6 0 1
a[0]와 a[5]를 변경했습니다.
1 9 8 6 0 4
a[1]와 a[4]를 변경했습니다.
1 0 8 6 9 4
a[2]와 a[3]를 변경했습니다.
역순 끝

Q3 배열의 모든요소 합계

public static void Q3(int[] a) {
        int result = 0;
        for (int i = 0; i < a.length; i++) {
            result += a[i];
        }
        System.out.printf("result : %d", result);

    }

Q4,Q5 배열 복사, 역순 복사

public static void Q4(int[] a) {
        int[] copy = new int[a.length];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = a[i];
            System.out.printf("%d ", copy[i]);
        }

    }

    public static void Q5(int[] a) {
        int[] copy = new int[a.length];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = a[a.length - i - 1];
            System.out.printf("%d ", copy[i]);
        }

    }

Q6 기수 변경

 public static void Q6(int x, int r, char[] d) {
        Before("Q6");
        int digits = 0;
        String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        do {
            d[digits++] = dchar.charAt(x % r);
            x /= r;

        } while (x != 0);

        for (int i = 0; i < digits; i++) {

            System.out.print(d[digits - i - 1]);

        }

        After("Q6");

    }

Q7 기수 변환과정 출력

public static void Q7(int x, int r, char[] d) {
        Before("Q7");
        int digits = 0;
        String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        System.out.printf("%d|%7d\n", r, x);
        do {
            System.out.printf("%d|%7d ... %d\n", r, x, x % r);
            d[digits++] = dchar.charAt(x % r);
            x /= r;
            System.out.println(" + ----------");

        } while (x != 0);
        System.out.printf("%d 진수로", r);
        for (int i = 0; i < digits; i++) {
            System.out.printf("%c", d[digits - 1 - i]);
        }

        After("Q7");

    }

소수판단

 public static void primeV1() {
        int count = 0; // 나눗셈 횟수

        for (int n = 2; n <= 1000; n++) {
            int i;
            for (i = 2; i < n; i++) {
                count++;
                if (n % i == 0)
                    break;
            }
            if (n == i)
                System.out.println(n);
        }
        System.out.println("나눔셈을 수행한 횟수 : " + count);

    }

현 프로그램으로 진행하게 된다면 1000 이하의 소수를 구하기위해 78000여번의 나눗셈을 합니다.

78000번의 나눗셈중에 불필요한 나눗셈이 많습니다 2,3으로 나누어 떨어지지 않으면 4(2x2),6(3x2)로도 나누어 떨어지지 않습니다.이러한 나눗셈을 개선해보도록 하겠습니다.

public static void primeV2() {
        int count = 0; // 나눗셈 횟수
        int ptr = 0; // 소수 갯수
        int[] prime = new int[500]; // 찾은 소수 저장

        prime[ptr++] = 2;
        for (int n = 3; n <= 1000; n += 2) { // 홀수만 진행
            int i;
            for (i = 1; i < ptr; i++) { // 이미 찾은 소수로만 진행
                count++;
                if (n % prime[i] == 0) // 나누어 떨어지면 소수 X
                    break;
            }
            if (ptr == i)
                prime[ptr++] = n;
        }
        for (int i = 0; i < ptr; i++) {
            System.out.println(prime[i]);
        }

        System.out.println("나눔셈을 수행한 횟수 : " + count);

    }

짝수는 소수가 되지 못하기에 홀수로만 반복문을 돌리고 저장된 소수로만 반복문을 돌려 소수를 찾습니다.
나눗셈 횟수 14000여회로 1/5 가량 줄었습니다. 제곱근을 이용해 더 개선 해보도록 하겠습니다.
N의 약수는 무조건 sqrt(N)의 범위에 존재한다.
N이 12라 가정할때 12의 제곱근은 약 3.46입니다
12의 약수는 1,2,3,4,6,12 입니다. 여기서 1과 12를 제외했을때
26 34 43 62의 결과입니다. 이들 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지면 몫이 작아지는 반비례 관계입니다. 결국 N의 절반(제곱근) 까지 향하게 되면 나누는 값이 반대로 바뀌게만 되는 상황이다.
따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별이 가능합니다.

 public static void primeV3() {
        int count = 0; // 나눗셈 횟수
        int ptr = 0; // 소수 갯수
        int[] prime = new int[500]; // 찾은 소수 저장

        prime[ptr++] = 2;
        prime[ptr++] = 3;
        for (int n = 5; n <= 1000; n += 2) { // 홀수만 진행
            boolean flag = false;
            for (int i = 1; prime[i] * prime[i] <= n; i++) { // 이미 찾은 소수로만 진행
                count += 2;
                if (n % prime[i] == 0) { // 나누어 떨어지면 소수 X
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                prime[ptr++] = n;
                count++;
            }
        }
        for (int i = 0; i < ptr; i++) {
            System.out.println(prime[i]);
        }

        System.out.println("나눔셈을 수행한 횟수 : " + count);

수행 횟수 3774회

같은 것을 구하더라도 알고리즘에 따라 계산 속도가 달라지는 것을 실감하게 되었다.

Author And Source

이 문제에 관하여(알고리즘 공부 뿌셔!), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gavri/알고리즘-공부-뿌셔

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)