[자료구조] 알고리즘이란

자료구조와 함께 배우는 알고리즘 입문을 통해 자료구조 기초를 쌓아보자! 

[1장. 기본 알고리즘]

1. 알고리즘이란?

알고리즘 & 순서도 개념. 태블릿에 메모해둔 내용. 

- 값과 최댓값

• 순차적 구조 : 여러 문장(프로세스)이 순차적으로 실행되는 구조 
• 선택 구조 : 식의 평가결과에 따라 프로그램의 실행 흐름을 변경하는 if문
• 개발할 때 순서도(플로우 차트)를 그리는 습관을 가지는 것이 좋다! 개발 구상이 복잡하거나, 팀원들과 전체 서비스 흐름을 공유하고 검토받는 데 유용하다.
• 알고리즘 : 문제를 해결하기 위한 것으로 명확하게 정의되고 순서가 있는 유한개의 규칙으로 이루어진 집합

- 조건 판단과 분기

• 연산자 : +,- 등의 연산기호
  • 단항 연산자 : 피연산자 1개 a++
  • 2항 연산자 : 피연산자 2개 a < b
  • 3항 연산자 : 피연산자 3개 a ? b : c
  •  피연산자 : 연산의 대상이 되는 것.

public class Test {
	
	final static Scanner SCANNER = new Scanner(System.in);
	
	/**
	 * 연습문제 Q1 : 네 값의 최대값 구하기
	 */ 
	static int searchMax(int a, int b, int c, int d) {
		System.out.println("************** searchMax");
		int max = a;
		
		if (b>max) {
			max = b;
		}
		if (c>max) {
			max = c;
		}
		if (d>max) {
			max = d;
		}
		
		return max;
	}
	
	/**
	 * 연습문제 Q2 : 세 값의 최솟값 구하기
	 */ 
	static int searchMin(int a, int b, int c) {
		System.out.println("************** searchMin");
		int min = a;
		
		if (b<min) {
			min = b;
		}
		if (c<min) {
			min = c;
		}
		return min;
	}
	
	/**
	 * 연습문제 Q3 : 네 값의 최솟값 구하기
	 */ 
	static int searchMin(int a, int b, int c, int d) {
		System.out.println("************** searchMin");
		int min = a;
		int arr[] = {b,c,d};		
		for (int i : arr) {
			if(min > i) {
				min = i;
			}
		}		
		return min;
	}
	
	/**
	 * 연습문제 Q4 : 세 값의 중간값 구하기
	 */ 
	static int searchMed(int a, int b, int c) {
		System.out.println("************** searchMed");
		if (a >= b) {
			if (a <= c) {
				return a;
			} else if ( b >= c) {
				return b;
			} else {
				return c;
			}
		} else if (a > c) {
			return a; 
		} else if (b > c) {
			return c;
		} else {
			return b;
		}
	}
	
	/**
	 * 연습문제 Q5
	 * OR조건이면 조건에 해당하는지 모두 확인해야 하므로 효율이 떨어진다
	 */
	static int med3(int a, int b, int c) {
		System.out.println("************** med3");
		TimeUtil time = new TimeUtil();
		int result;
		
		time.start();
		if ((b >= a && a <= c) || (c >= a && a <= b)) {
			result = a; 
		} else if ((a > b && c < b) || (a < b && c > b)) {
			result = b;
		} else {
			result = c;
		}
		time.end();
		
		return result;
	}
    
    	public static void main(String[] args) {
		System.out.println("최대값: " + searchMax(5,99,2,6));
		System.out.println("3개 중 최소값: " + searchMin(99,2,6));
		System.out.println("4개 중 최소값: " + searchMin(99,2,1,6));
		System.out.println("3개 중 중앙값: " + searchMed(99,2,40));
		
		SCANNER.close();
	}

}

연습문제 1~5 실행결과

- 순서도의 기호

• 데이터(data) : 데이터의 입력과 출력
• 처리(process) : 정보의 값, 자료형, 위치를 바꾸도록 정의한 연산, 연산 집합의 실행, 연속적인 몇 가지 흐름 가운데 방향을 결정하는 연산 집합이나 연산군의 실행
• 미리 정의한 처리(predefined process) : 서브 루틴 및 모듈 등 다른 곳에서 이미 정의한 하나 이상의 연산 또는 명령어 들로 이루어진 처리
• 판단(decision) : 하나의 입구와 하나 이상을 선택할 수 있는 출구가 있고, 기호에서 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능. 주로 예상되는 평가 결과의 경로를 선 가까이에 쓴다.
• 루프 범위(loop limit) : 두 부분으로 구성되어 루프의 시작과 종료를 의미. 시작 기호 또는 종료 기호 안에 초깃값, 증갓값, 종료 값을 표기
• 선(line) : 제어의 흐름. 흐름의 방향을 분명히 하고자 할 때 화살표를 붙임. 순서도를 작성할 때도, 보기 쉽게 화살표를 붙이기도 함.
  • 실선(real line) : 끊어진 곳 없이 이어진 선

  • 점선(dotted line) : 일정한 간격으로 점을 찍어 이어진 선

  • 파선(broken line) : 긴 선과 짧은 선을 3 : 1 비율로 이은 선
• 단말(terminator) : 외부환경으로 나가서 외부환경에서 들어오는 것. 프로그램 흐름의 시작과 종료

---

2. 반복

• 반복 구조(루프) : 어떤 조건이 성립하는 동안 처리(프로그램의 명령문 또는 명령어의 집합)를 반복하여 실행하는 것
  • 관련 예제 : 1부터 n까지의 정수 합 구하기, SumWhile, SumFor, 양수만 입력하기

• 구조적 프로그래밍

  •  하나의 입구와 하나의 출구를 가진 구성요소만을 계층적으로 배치하여 프로그램을 구성하는 방법. 순차, 선택, 반복이라는 제어 흐름을 사용.
  • 논리 연산자의 단축 평가 : 논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피연산자의 평가를 수행하지 않은데 이를 단축 평가라고 한다. 
  • 드모르간 법칙 : 각 조건을 부정하고 논리곱을 논리합으로 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.
    1.  x && y 와 !(!x || !y) 는 같다
    2.  x || y 와 !(!x && !y) 는 같다 

• 다중 루프

  • 반복 루프 안에 다시 반복 루프가 있는 구조
  • 직각 이등변 삼각형 출력

public class SumWhile {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n;
		int sum = 0;
		int i = 1;
		
		System.out.println("1부터 n까지의 정수 합 구하기");
		System.out.print("n:");
		n = stdIn.nextInt();
		stdIn.close();
		
		// 사전 판단 반복 구조.
		while (i <= n) {
			sum += i;
			i++;
		}
		
		// 연습문제 Q6
		System.out.printf("증가값 i: %d\n", i);
		System.out.printf("1부터 %d까지의 정수 합 : %d", n, sum);
	}
}

public class Test {
	
	final static Scanner SCANNER = new Scanner(System.in);
	
	/**
	 * 연습문제 Q7 1~7를 더한 결과를 출력해주는 메소드
	 */
	static void sum7() {
		System.out.println("************** sum7");
		
		StringBuffer sb = new StringBuffer("");
		int i = 1;
		int sum = 0;
		
		// 사전 판단 반복 구조.
		while (i <= 7) {
			sum += i;
			sb.append(i++).append(" + ");
		}
		
		sb.append("= ").append(sum);
		System.out.println(sb.toString());
	}
	
	/**
	 * 연습문제 Q8 : 가우스의 덧셈
	 */
	static void sumGauss() {
		System.out.println("************** sumGauss");
		int n;
		int result;
		System.out.println("1부터 합계를 구할 정수");
		System.out.print("n:");
		
		n = SCANNER.nextInt();
		result = (1+n) * n/2;
		
		System.out.printf("1부터 %d까지 합(가우스 덧셈): %d\n",n, result);
	}
	
	/**
	 * 연습문제 Q9 : 정수 a, b 를 포함해서 그 사이의 모든 정수의 합을 구하는 메소드
	 */
	static int sumOf() {
		System.out.println("************** sumOf");

		System.out.println("합계를 구할 두 정수");
		System.out.print("a:");
		int a = SCANNER.nextInt();

		System.out.print("b:");
		int b = SCANNER.nextInt();
		
		int sum = 0;
		int startNum = a<b?a:b; 
		int endNum = a>b?a:b; 
		for(int i = startNum;i<=endNum ;i++) {
			sum += i;
		}
		
		System.out.printf("%d부터 %d까지의 합 : %d\n", a, b, sum);
		return sum;
	}
	
	/**
	 * 연습문제 10 : b-a 를 구하세요. 단, b > a
	 */
	static void subOf() {
		System.out.println("************** subOf");
		
		System.out.print("a: ");
		int a = SCANNER.nextInt();
		
		System.out.print("b: ");
		int b = SCANNER.nextInt();
		
		while (a> b) {
			System.out.println("a보다 큰 값을 입력하세요!");
			System.out.print("b: ");
			b = SCANNER.nextInt();
		}
		
		System.out.printf("b - a 는 %d입니다.\n", b-a);
		return;

	}
	
	/**
	 * 연습문제 Q11 : 양의 정수를 입력하고 자릿수를 출력하는 메소드
	 */
	static int numLength() {

		System.out.println("************** numLength");
		int num = 0;
		System.out.println("양의 정수를 입력하세요.");
		do {
			System.out.print("num:");
			num = SCANNER.nextInt();
		}while(num <= 0);
		
		int len = 1;
		while(num/10>0){
			num = num/10;
			len++;
		}
		System.out.printf("이 수의 자릿수는 %d입니다.\n",len);
		return len;
	}
	
	/**
	 * 연습문제 Q12 곱하기 테이블 출력하기
	 * */
	static void multiTable() {
		System.out.printf("\n\n**************multiTable\n   |");
		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("%3d|",i);
			for(int j=1; j<=9; j++) {
				System.out.printf("%3d", i*j);
			}
			System.out.println();
		}
	}
	
	/**
	 * 연습문제 Q13 더하기 테이블 출력하기
	 * */
	static void sumTable() {
		System.out.printf("\n\n**************sumTable\n   |");
		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("%3d|",i);
			for(int j=1; j<=9; j++) {
				System.out.printf("%3d", i+j);
			}
			System.out.println();
		}
	}
	
	/**
	 * 연습문제 Q14 단수를 입력받아 정사각형 출력하기
	 * */
	static void printSquare() {
		int num = 0;
		System.out.println("\n\n**************printSquare\n사각형을 출력합니다.");
		do {
			System.out.print("단수:");
			num = SCANNER.nextInt();
		}while(num <= 0);
		
		for (int i=0; i<num; i++) {
			for (int j=0; j<num; j++) 
				System.out.print("*");
			System.out.println();
		}
	}
    
    	/**
	 * 연습문제 Q15 : 직각 이등변 삼각형 출력
	 * */
	static void triangleLU() {
		int n;
		System.out.println("왼쪽 위가 직각인 이등변 삼각형을 출력합니다");
		
		do {
			System.out.print("몇단 삼각형 입니까? : ");
			n = SCANNER.nextInt();
		}while(n <= 0);
		
		for (int i=n; i>0; i--) {
			for(int j=0; j<i; j++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}
	
	static void triangleRU() {
		int n;
		System.out.println("오른쪽 위가 직각인 이등변 삼각형을 출력합니다");
		
		do {
			System.out.print("몇단 삼각형 입니까? : ");
			n = SCANNER.nextInt();
		}while(n <= 0);
		
		for (int i=n; i>0; i--) {
			for(int k=0; k<n-i; k++) {
				System.out.print(" ");
			}
			for(int j=i; j>0; j--) {
				System.out.print("*");
			}
			System.out.println();
		}	
	}
	
	static void triangleRB() {

		int n;
		System.out.println("오른쪽 아래가 직각인 이등변 삼각형을 출력합니다");
		
		do {
			System.out.print("몇단 삼각형 입니까? : ");
			n = SCANNER.nextInt();
		}while(n <= 0);
		
		for (int i=0; i<n; i++) {
			for(int k=n; k>i; k--) {
				System.out.print(" ");
			}
			for(int j=0; j<=i; j++) {
				System.out.print("*");
			}
			System.out.println();
		}	
		
	}
	
	/**
	 * 연습문제 Q16 : n단의 피라미드 출력
	 * */
	static void spira() {

		int n;
		System.out.println("n단의 피라미드 출력합니다");
		
		do {
			System.out.print("몇단 삼각형 입니까? : ");
			n = SCANNER.nextInt();
		}while(n <= 0);
		
		for (int i=n; i>0; i--) {
			for(int k=i; k>0; k--) {
				System.out.print(" ");
			}
			for(int j=0; j<2*(n-i)+1; j++) {
				System.out.printf("*");
			}
			System.out.println();
		}	
	}
	
	/**
	 * 연습문제 Q17 : n단의 숫자 피라미드 출력
	 * */
	static void npira() {

		int n;
		System.out.println("n단의 피라미드 출력합니다");
		
		do {
			System.out.print("몇단 삼각형 입니까? : ");
			n = SCANNER.nextInt();
		}while(n <= 0);
		
		for (int i=n; i>0; i--) {
			for(int k=i; k>0; k--) {
				System.out.print(" ");
			}
			for(int j=0; j<2*(n-i)+1; j++) {
				System.out.printf("%d",n-i+1);
			}
			System.out.println();
		}	
	}
    
	public static void main(String[] args) {
    
		sum7();
		sumGauss();
		sumOf();
		subOf();
		numLength();
		multiTable();
		sumTable();
		printSquare();
		triangleLU();
		triangleRU();
		triangleRB();
		spira();
		npira();
        
		SCANNER.close();
	}
}

연습문제 7~11 실행결과 

연습문제 12~14 실행결과 

연습문제 15~17 실행결과 

 

 

문제 출처는 Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편입니다.
연습문제 풀이는 직접 작성하였습니다. 잘못된 부분이 있다면 댓글 부탁드립니다.