[JAVA Algorithm] - 알고리즘

알고리즘이란?

문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

세 값의 최댓값 구해보기

package com.in28minutes.algorithm;

import java.util.Scanner;

public class Max3 {
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("세 정수의 최대 값을 구합니다");
		System.out.print("a의 값 : "); int a = stdIn.nextInt();
		System.out.print("b의 값 : "); int b = stdIn.nextInt();
		System.out.print("c의 값 : "); int c = stdIn.nextInt();
		int max = a;
		if(b > max) max = b;
		if(c > max) max = c;
		
		System.out.println("최댓값은 "+max+" 입니다");
	}

}

결과

 

세 정수의 최대 값을 구합니다
a의 값 : 12
b의 값 : 2
c의 값 : 100
최댓값은 100 입니다

 

순서

1. max에 a 값을 넣는다

2. b 값이 max보다 크면 max에 b값을 넣는다.

3. c 값이 max보다 크면 max에 c값을 넣는다.

 

이 세문장이 나란히 있다면 순서대로 실행이되고, 이렇게 여러 문장(프로세스)이 순차적으로 실행되는 구조를 순차적(concatenation) 구조라고 한다. 그런데 1은 단순 대입이지만 2,3은 if문이다. ()안에 있는 식의 평가 결과에 따라 프로그램의 실행 흐름을 변경하는 if 문을 선택(selection)구조라고 한다.

 

** System.in은 키보드와 연결된 표준 입력 스트림(standard input stream)이다.

** stdln.nextInt()가 호출되면 키보드로 입력한 정숫값을 얻을 수 있다.

** int max = a;는 변수를 만드는 시점에 값을 넣는 '초기화'이고, 이프로그램의 'max = a;'는 이미 만들어져 있는 변수에 ㄱ밧을 넣는 '대입'이다.

 

키보드로 숫자와 문자열 입력하기 

입력할 자료형에 따라 호출해야 하는 메서드는 다음과 같다.

 

메서드	자료형	입력값의 범위
nextBoolean()	boolean	true or false
nextByte()	byte	-128~+127
nextShort()	short	-32768~+32767
nextInt()	int	-2147483648~+2147483647
nextLong()	long	-9223372036854775808 ~ +9223372036854775807
nextFloat()	float	+-3.40282347E+38~ +-1.40239846E-45
nextDouble()	double	+-1.79769313486231507E+378~+-4.94065645841246544E-324
next()	String	문자열(스페이스, 줄 바꿈 문자로 구분)
nextLine()	String	문자열 1줄

 

여러 값에 대해서 최댓값 구해보기 

public class Max3 {
	
	static int max3(int a, int b, int c) {
		
		int max = a;
		if(b > max) max = b;
		if(c > max) max = c;
		
		return max;
	}
	
	public static void main(String[] args) {

		System.out.println("max3(3,2,1) =" +max3(3,2,1));
		System.out.println("max3(3,2,2) =" +max3(3,2,2));
		System.out.println("max3(3,2,1) =" +max3(3,2,3));
		System.out.println("max3(3,2,3) =" +max3(3,2,3));
		System.out.println("max3(2,1,3) =" +max3(2,1,3));
		System.out.println("max3(3,3,2) =" +max3(3,3,2));
		System.out.println("max3(3,3,3) =" +max3(3,3,3));
		System.out.println("max3(2,2,3) =" +max3(2,2,3));
		System.out.println("max3(2,3,1) =" +max3(2,3,1));
		System.out.println("max3(2,3,2) =" +max3(2,3,2));
		System.out.println("max3(1,3,2) =" +max3(1,3,2));
		System.out.println("max3(2,3,3) =" +max3(2,3,3));
		System.out.println("max3(1,2,3) =" +max3(1,2,3));
	}

}

결과 

max3(3,2,1) =3
max3(3,2,2) =3
max3(3,2,1) =3
max3(3,2,3) =3
max3(2,1,3) =3
max3(3,3,2) =3
max3(3,3,3) =3
max3(2,2,3) =3
max3(2,3,1) =3
max3(2,3,2) =3
max3(1,3,2) =3
max3(2,3,3) =3
max3(1,2,3) =3

연습문제 1 - 네 값의 최댓값을 구하는 max4 메서드를 작성하라

public class Max3 {
	
	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) {

		System.out.println("max4(3,2,1,4) =" +max4(3,2,1,4));
		System.out.println("max4(3,2,2,4) =" +max4(3,2,2,4));
		System.out.println("max4(3,2,1,4) =" +max4(3,2,3,4));
		System.out.println("max4(3,2,3,4) =" +max4(3,2,3,4));
		System.out.println("max4(2,1,3,4) =" +max4(2,1,3,4));
		System.out.println("max4(3,3,2,4) =" +max4(3,3,2,4));
		System.out.println("max4(3,3,3,4) =" +max4(3,3,3,4));
		System.out.println("max4(2,2,3,4) =" +max4(2,2,3,4));
		System.out.println("max4(2,3,1,4) =" +max4(2,3,1,4));
		System.out.println("max4(2,3,2,4) =" +max4(2,3,2,4));
		System.out.println("max4(1,3,2,4) =" +max4(1,3,2,4));
		System.out.println("max4(2,3,3,4) =" +max4(2,3,3,4));
		System.out.println("max4(1,2,3,4) =" +max4(1,2,3,4));
	}

}

결과 

max4(3,2,1,4) =4
max4(3,2,2,4) =4
max4(3,2,1,4) =4
max4(3,2,3,4) =4
max4(2,1,3,4) =4
max4(3,3,2,4) =4
max4(3,3,3,4) =4
max4(2,2,3,4) =4
max4(2,3,1,4) =4
max4(2,3,2,4) =4
max4(1,3,2,4) =4
max4(2,3,3,4) =4
max4(1,2,3,4) =4

 

연습문제 2 - 세 값의 최솟값을 구하는 min3 메서드를 작성하라

public class Max3 {
	
	static int min3(int a, int b, int c) {
		
		int min = a;
		if(b < min) min = b;
		if(c < min) min = c;
		
		return min;
	}
	
	public static void main(String[] args) {

		System.out.println("min3(3,2,1) =" +min3(3,2,1));
		System.out.println("min3(3,2,2) =" +min3(3,2,2));
		System.out.println("min3(3,2,1) =" +min3(3,2,3));
		System.out.println("min3(3,2,3) =" +min3(3,2,3));
		System.out.println("min3(2,1,3) =" +min3(2,1,3));
		System.out.println("min3(3,3,2) =" +min3(3,3,2));
		System.out.println("min3(3,3,3) =" +min3(3,3,3));
		System.out.println("min3(2,2,3) =" +min3(2,2,3));
		System.out.println("min3(2,3,1) =" +min3(2,3,1));
		System.out.println("min3(2,3,2) =" +min3(2,3,2));
		System.out.println("min3(1,3,2) =" +min3(1,3,2));
		System.out.println("min3(2,3,3) =" +min3(2,3,3));
		System.out.println("min3(1,2,3) =" +min3(1,2,3));
	}

}

결과 

min3(3,2,1) =1
min3(3,2,2) =2
min3(3,2,1) =2
min3(3,2,3) =2
min3(2,1,3) =1
min3(3,3,2) =2
min3(3,3,3) =3
min3(2,2,3) =2
min3(2,3,1) =1
min3(2,3,2) =2
min3(1,3,2) =1
min3(2,3,3) =2
min3(1,2,3) =1

 

연습문제 3 - 네 값의 최솟값을 구하는 min4 메서드를 작성하라

public class Max3 {
	
	static int min4(int a, int b, int c, int d) {
		
		int min = a;
		if(b < min) min = b;
		if(c < min) min = c;
		if(d < min) min = d;
		
		return min;
	}
	
	public static void main(String[] args) {

		System.out.println("min4(3,2,1,4) =" +min4(3,2,1,4));
		System.out.println("min4(3,2,2,4) =" +min4(3,2,2,4));
		System.out.println("min4(3,2,3,4) =" +min4(3,2,3,4));
		System.out.println("min4(3,2,3,4) =" +min4(3,2,3,4));
		System.out.println("min4(2,1,3,4) =" +min4(2,1,3,4));
		System.out.println("min4(3,3,2,4) =" +min4(3,3,2,4));
		System.out.println("min4(3,3,3,4) =" +min4(3,3,3,4));
		System.out.println("min4(2,2,3,4) =" +min4(2,2,3,4));
		System.out.println("min4(2,3,1,4) =" +min4(2,3,1,4));
		System.out.println("min4(2,3,2,4) =" +min4(2,3,2,4));
		System.out.println("min4(1,3,2,4) =" +min4(1,3,2,4));
		System.out.println("min4(2,3,3,4) =" +min4(2,3,3,4));
		System.out.println("min4(1,2,3,4) =" +min4(1,2,3,4));
	}
}

결과 

min4(3,2,1,4) =1
min4(3,2,2,4) =2
min4(3,2,3,4) =2
min4(3,2,3,4) =2
min4(2,1,3,4) =1
min4(3,3,2,4) =2
min4(3,3,3,4) =3
min4(2,2,3,4) =2
min4(2,3,1,4) =1
min4(2,3,2,4) =2
min4(1,3,2,4) =1
min4(2,3,3,4) =2
min4(1,2,3,4) =1

 

중앙값 구해보기

package com.in28minutes.algorithm;

import java.util.Scanner;

public 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) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("세 정수의 값을 구합니다");

		System.out.print("a 값 : ");
		int a = stdIn.nextInt();
		System.out.print("b 값 : ");
		int b = stdIn.nextInt();
		System.out.print("c 값 : ");
		int c = stdIn.nextInt();
		
		System.out.println("중앙값은 " +med3(a,b,c)+ "입니다");
	}
}

결과 

세 정수의 값을 구합니다
a 값 : 100
b 값 : 2
c 값 : 77
중앙값은 77입니다

 

연습문제 4 - 세 값의 대소 관계 13 종류의 모든 조합에 대하여 중앙값을 구하여 출력하는 프로그램을 작성하라 

public class Median {

	static HashMap<String,Object> med3(int a, int b, int c) {
		
		HashMap<String, Object> retMap = new HashMap<String, Object>();
		
		String resultText;
		String resultMed;
		
		if(a>=b) {
			if(a>b) {
				if(b>=c) {
					if(b>c) {
						resultText="a>b>c";
						resultMed = String.valueOf(b) ;
					}else {
						resultText="a>b=c";
						resultMed = String.valueOf(b) ;
					}
				}else {
					if(a>=c) {
						if(a>c) {
							resultText="a>c>b";
							resultMed = String.valueOf(c) ;
						}else {
							resultText="a=c>b";
							resultMed = String.valueOf(c) ;
						}
					}else {
						resultText ="c>a>b";
						resultMed = String.valueOf(a) ;
					}
				}
			}else {
				if(b>=c) {
					if(b>c) {
						resultText = "a=b>c"; 
						resultMed = String.valueOf(b) ;
					}else {
						resultText = "a=b=c";
						resultMed = String.valueOf(b) ;
					}
				}else {
					resultText="c>a=b";
					resultMed = String.valueOf(a) ;
				}
			}
		}else {
			if(a>c) {
				resultText = "b>a>c";
				resultMed = String.valueOf(a) ;
				if(a==c) {
					resultText = "b>a=c";
					resultMed = String.valueOf(a) ;
				}
			}else {
				if(b>c) {
					if(b==c) {
						resultText ="b=c>a";
						resultMed = String.valueOf(c) ;
					}else {
						resultText="b>c>a";
						resultMed = String.valueOf(c) ;
					}
				}else {
					resultText="c>b>a";
					resultMed = String.valueOf(b) ;
				}
			}
		}
		
		retMap.put("resultText", resultText);
		retMap.put("resultMed", resultMed);
		
		return retMap;
	}
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("세 정수의 중앙값을 구합니다");

		System.out.print("a 값 : ");
		int a = stdIn.nextInt();
		System.out.print("b 값 : ");
		int b = stdIn.nextInt();
		System.out.print("c 값 : ");
		int c = stdIn.nextInt();
		
		HashMap<String, Object> retMap = med3(a,b,c);
		
		System.out.println(med3(a,b,c));
		System.out.println(retMap.get("resultText")+"순으로 중앙값은 "+retMap.get("resultMed")+ "입니다");
		
	}
}

결과 1

세 정수의 중앙값을 구합니다
a 값 : 11
b 값 : 11
c 값 : 33
{resultText=c>a=b, resultMed=11}
c>a=b순으로  중앙값은 11입니다

 

결과 2

세 정수의 중앙값을 구합니다
a 값 : 88
b 값 : 77
c 값 : 55
{resultText=a>b>c, resultMed=77}
a>b>c순으로  중앙값은 77입니다

 

결과 3

세 정수의 중앙값을 구합니다
a 값 : 55
b 값 : 99
c 값 : 11
{resultText=b>a>c, resultMed=55}
b>a>c순으로  중앙값은 55입니다

 

 

 

----> 위 문제는 실습 문제가 왜 저렇게 ? 축약되는거에 대해서 그림을 그리면서 봐도 저렇게 빠지는게 이해가 안가서 한참 고민하다가 케이스바이케이스로 분기타서 만들었다. 일단 분기타면서도 아닌 것에 == else 조건을 먼저 치는 가지치는 형식으로 올라가며 작성함.

 

 

---

 

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;
}

 

일단은 실습문제에서 a>=b 이면 다시 b>=c / a<=c / else로 타지는게 결과를 알고보면 당연하지만 막상 문제해결할 때 왜이렇게 했지? 라고 하면 왜 바로 저 조건으로 분기 태웠는지 이해가 안가서 하나하나 케이스를 따서 역으로 결정 트리를 만들고 분기 태우는 걸로 코드를 작성해보았다. if / else if / else 실무에서 많이 썼지만 다시 해보니까 난 아직 이군 ..^^ 내 머릿속에서 막 ㅎ 계산되고 자동으로 따다다 나오면 좋겠다 -__- ㅠ 그날이 언제냐.. 그날은 될 때까지 ㅎ 

 

 

 

참고 :  자료구조와 함께 배우는 알고리즘 입문 - 자바편