[Java] 기본 알고리즘

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

 

1-1 알고리즘이란?

세 값의 최댓값

- 3개의 값중 최대값 찾기

class Max3 {
	Scanner scan = new Scanner(System.in);
    
    int a = scan.nextInt();
    int b = scan.nextInt();
    int c = scan.nextInt();
    
    int max = a;
    if (b > max) max = b;
    if (c > max) max = c;
    
    System.out.println("최대값은 : " + max + "이다.");
}

- 연습문제

Q1 네 값의 최댓값을 구하는 max4 메소드 작성

static int max4(int a, int b, int c, int d) {
	int max = a;
    
    if (b > max) max = b;
    if (c > max) max = c;
    if (d > max) max = d;
    
    return max;
}

public static void main(String args[]) {
	
    int max = max4(1, 2, 3, 4);
    System.out.println("최대값은 "+ max + "이다.");
    
}

Q2 세 값의 최솟값을 구하는 min3 메소드 작성

static int min3(int a, int b, int c) {
	int min = a;
    if (min > b) min = b;
    if (min > c) min = c;
    
    return min;
}

public static void main(String args[]) {
	
    int min = min3(1, 2, 3);
    
    System.out.println("최소값은 + min + "이다.");

}

 

- 3개의 값 중 중앙값 찾기

class Median {
	static int med3(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;
        			
        
    }
    
    public static void main(String args[]) {
    	
        int med = med3(1, 5, 10);
        System.out.println("중앙값은 " + med + "이다.");
    }

}

 

- 연습문제

Q5 중앙값을 구하는 메소드는 하단 처럼 작성할 수 있다. 상단의 메소드와 비교하여 효율이 떨어지는 이유 설명

static int med3(int a, int b, int c) {
	
    if ((b >= a && c <= a) || (b <= a && c >= a))
    	return a;
    else if ((a > b && c < b) || (a < b && c > b))
    	return b;
    return c;

}


//	가장 처음의 if문의 판단
//	if ((b >= a && c<= a) || (b <= a && c >= a))
//	에 주목합니다. 여기서 b >= a 및 b <= a의 판단을 뒤집은 판단(실질적으로 같은 판단)을 이어지는 else 이후의 
//	else if ((a > b && c < b) || (b <= a && c > b))
//	으로 수행합니다. 결국 가장 처음의 if가 성립한 경우 2 번째의 if에서도 (실질적으로)같은 판단을 수행하므로 효율이 나빠집니다.

 

조건 판단과 분기

- 정수값의 부호 판단하기

class JudgeSign {
	public static void main(String[] args) {
    
    	Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        
        if (n > 0 ) System.out.println("+");
        else if (n < 0 ) System.out.println("-");
        else System.out.println("0");
    
    }
}

 

 

1-2 반복

1부터 n까지 정수 합 구하기

class SumWhile {
	public static void main(String[] args) {
    
        int sum = 0;
        int i = 1; 
        int n = 10;

        while (i <= n) {
            sum += i;
            i++;
        }
        
        System.out.println("1부터 " + n + "까지의 합은 " + sum + "이다.");
    
    
    }
}

 

- 연습문제 

Q7 n이 7이면 1~7합이 28임을 출력하는 프로그램을 작성

int sum = 0;
int n = 7;

for (int i = 1; i <= n; i++) {
	
    sum += i;
    
    if (i < n) System.out.println(i + "+");
    else System.out.printl(i);
	
}

System.out.println(" = " + sum);

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

public static void main(String[] args) {
	int a = 1;
    int b = 10;
    
	int sum = sumof(a, b);


}

static int sumof(int a, int b) {
	int s = 0;
    int e = 0;
    int sum = 0;
    
	if (a > b) {
    	s = b;
        e = a;
    } else if (a < b) {
    	
    } 
    
    
	for (int s; s < e; s++) {
        sum += s;
        
    }
	return sum;
}

 

양수만 입력하기

- 연습문제

Q10 두 변수 a, b에 정수를 입력하고 b-a를 출력하는 프로그램 작성

public static void main(String[] args) {
	
    Scanner sc = new Scanner(System.in);
    int value = 0;
    int a = sc.nextInt();
    int b = 0;
   	while (true) {
        b = sc.nextInt();
        if (b > a)
            break;
        System.out.println("a보다 큰 값을 입력하세요!");
    }
   
	System.out.println("b-a는 " + b-a);


}

 

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

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
        
    
    while(true) {
    
    	if (n > 0) break;
    	System.out.println("0보다 큰 값 입력");
    }
	int no = 0; 			// 자릿수
    while (n > 0) {
        n /= 10; 			// n을 10으로 나눔
        no++;
    }
    System.out.println("자릿수 : " + no);
}

 

구조적 프로그래밍

- 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법을 구조적 프로그래밍이라고 한다.

- 구조적 프로그래밍은 순차, 선택, 반복 3종류의 제어 흐름을 사용한다.

 

- 입력한 값을 2자리 양수로 제한하는 프로그램

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
    int n;
    
    do {
    	n = sc.nextInt();
    } while (n < 10 || n > 99);


	System.out.println(n);
}

 

다중루프

- 연습문제

Q12 위쪽과 왼쪽에 곱한느 수가 있는 곱셈표 출력하는 프로그램 작성(못품ㅠㅠ)

public static void main(String[] args) {
    System.out.print("   |");
    for (int i = 1; i <= 9; i++)
        System.out.printf("%3d", i);
    System.out.println("\n---+---------------------------");

    for (int i = 1; i <= 9; i++) {
        System.out.printf("%2d |", i);
        for (int j = 1; j <= 9; j++)
            System.out.printf("%3d", i * j);
        System.out.println();
    }
}

Q14 입력 받은 수를 한 변으로 하는 정사각형을 *기호로 출력

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

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

}

 

직각 이등변 삼각형 출력

- 연습문제

Q15 왼쪽 아래가 직각힌 이등변 삼각형 출력

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
	triangle(n);
    
    
}

static void triangle(int n) {
	for (int i = 1; i <= n; i++) {
    	
        for (int j = 1; j < i; j++) {
        	System.out.print("*");
        }
        
        System.out.println();
    
    }

}