[자료구조&알고리즘] 기본 알고리즘(알고리즘, 반복)

728x90

기본 알고리즘

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

용어

순차적(concatenation) 구조 - 여러 문장(프로세스)이 순차적으로 실행되는 구조
선택(select) 구조 - 평가 결과에 따라 흐름을 변경하는 if문

매개변수 - 메서드를 정의할 때
실인수 - 메서드를 호출할 때

연산자(operator) - +, -, <, > 등의 연산 기호
피연산자(operand) - 연산의 대상이 되는 것

최댓값 구하기

package chap01_1;

import java.util.Scanner;

public class max {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.println("세 정수의 최댓값 구하기");
		System.out.print("a의 값: ");
		int a = scan.nextInt(); //a 값을 입력받음
		System.out.print("b의 값: ");
		int b = scan.nextInt(); //b 값을 입력받음
		System.out.print("c의 값: ");
		int c = scan.nextInt(); //c 값을 입력받음
		
		int max = a; //a를 max라는 변수에 넣음
		if(b > max) max = b;
		if(c > max) max = c;
		
		System.out.println("최댓값은 " + max + "입니다.");
	}
	
}

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

java.util 패키지 - Scanner 클래스 import (클래스 선언보다 앞에 작성)

Scanner scan = new Scanner(System.in);

위의 코드는 main메서드 맨 앞에 작성
scan.nextInt() 키보드로 입력한 정숫값 얻음
▶ nextBoolean(), next(), nextLine(), nextLong(), nextDouble() 등 자료형에 따라 구분 필요

표준 스트림(standard streams) *보충하기**

특정한 프로그래밍 언어 인터페이스뿐 아니라 유닉스 및 유닉스 계열 운영 체제(어느 정도까지는 윈도우에도 해당함)에서 컴퓨터 프로그램과 그 환경(일반적으로 단말기) 사이에 미리 연결된 입출력 통로
표준 입력 스트림 (System.in) - 문자와 숫자를 꺼내는 장치 역할
표준 출력 스트림 (System.out)

순서도

순서도의 기호

최댓값 만들기(1)

https://school.programmers.co.kr/learn/courses/30/lessons/120847

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

최솟값 구하기

package chap01_1;

import java.util.Scanner;

public class quiz3 {

	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) {
		Scanner scan = new Scanner(System.in); //scan으로 입력 받음
		
		System.out.print("a의 값: "); int a = scan.nextInt();
		System.out.print("b의 값: "); int b = scan.nextInt();
		System.out.print("c의 값: "); int c = scan.nextInt();
		System.out.print("d의 값: "); int d = scan.nextInt();
		
		int min = min4(a, b, c, d); //위에서 입력 받은 숫자를 min4메서드 안에 넣고 min 변수에 담아줌
		System.out.println("네 값 중 최솟값은: " + min); //min 출력
	}
}

세 값의 대소 관계와 중앙값

decision tree (결정 트리) - 구하는 관계의 조합을 나열한 모양이 나무 형태인 것
왼쪽 ▶ 오른쪽으로 이동
조건이 성립하면 윗가지로, 성립하지 않으면 아랫가지로 이동

static int med3(int a, int b, int c) {
		if(a >= b) //a가 b보다 크고
			if(b >= c) //b가 c보다 크면
				return b; //중앙값 b
			else if(a <= c)
				return a;
			else
				return c;
		
		else if(a > c) //a<b && a>c
			return a;
		
		else if(b > c) //a<b && a<=c && b>c
			return c;
		
		else
			return b;
	}

중앙값 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/120811

프로그래머스

programmers.co.kr

반복

while문

i의 값이 n을 초과할 때 while문의 반복이 종료되므로 최종 i = n+1

for문

하나의 변수 사용에는 for문이 더 적합

1. 1+2+3+4+...+n = sum (1부터 n까지의 합)

package chap01_2;

import java.util.Scanner;

public class Quiz7 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.print("n의 값: ");
		int n = scan.nextInt();
		
		int sum = 0; //합계
		
		for(int i = 1; i <= n; i++) { //반복문
			if(i < n) //i가 n보다 작으면
				System.out.print(i + "+"); //i에 + 붙임
			else //i가 n이면
				System.out.print(i); //마지막으로 i 붙임
			
			sum += i; //sum에 i를 더함
		}
		System.out.print(" = " + sum); //최종 sum 적기
	}
}

2. 가우스의 덧셈 (1부터 n까지의 합)

package chap01_2;

import java.util.Scanner;

public class Quiz8 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.println("1부터 n까지의 합");
		System.out.print("n의 값: ");
		int n = scan.nextInt();
		
		int sum = ((1 + n) / 2 )* n;
		System.out.println(sum);
	}
}

3. a ~ b 까지의 합

알고리즘 미사용 (효율↓)

static int sumof(int a, int b) {
		
		if(a+b % 2 == 0) { //a+b가 짝수이면
			if(a > b) { //a가 클 때라는 가정으로 같은 식을 반복하므로 효율이 떨어짐
				return (a+b)*(a-b)/2;				
			} else {
				return (a+b)*(b-a)/2;
			}
		} 
		else { //a+b가 홀수이면
			if(a > b) {				
				return (a+b)*(a-b+1)/2;
			}else {
				return (a+b)*(b-a+1)/2;
			}
		}

	}

알고리즘 사용 (최댓값, 최솟값, 정수의 합)

Math.max(a, b)
Math.min(a, b)

static int sumof(int a, int b) {
		
	int min; //a, b 중 작은 값
	int max; //a, b 중 큰 값

	if(a > b) {	//애초에 조건식으로 큰값, 작은값을 나누고
		min = b;
		max = a;
	} else {
		min = a;
		max = b;
	}
		
	int sum = 0; //합계
	for(int i = min; i <= max; i++) { //하나씩 더해가면서 합계를 구함
		sum += i;
	}
	
	return sum;
}

등차수열의 합 사용 (암기)

항의 수(개수) * (첫 항 + 끝 항) / 2;
(b - a + 1) * (a + b) / 2;

a1 ~ an 까지 항의 개수 = 마지막 값 - 첫번째 값 + 1

향상된 for문 + 3항 연산자 사용 (코드 간결)

for (int i = ((a < b) ? a : b); i <= ((a < b) ? b : a); i++) {
     sum += i;
}

가우스의 덧셈 사용

1~max 값 더한 합 - 1~min 값 더한 합

알고리즘 사용했지만 값이 커지면 시간이 오래 걸림

https://school.programmers.co.kr/learn/courses/30/lessons/12912

프로그래머스

programmers.co.kr

4. b - a 출력

package chap01_2;

import java.util.Scanner;

public class Quiz10 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a;
		int b;
		
		System.out.print("a의 값: "); a = scan.nextInt();
		do {
			System.out.print("b의 값: "); b = scan.nextInt();
		} while (a >= b);
		
		System.out.println("b - a는 " + (b-a) + "입니다");
	}
}

package chap01_2;

import java.util.Scanner;

public class Quiz10_answer {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a;
		int b = 0;
		
		System.out.print("a의 값: "); a = scan.nextInt();
		while(true) {			
			System.out.print("b의 값: "); b = scan.nextInt();
			
			//1. 첫번째 방법
			if(a >= b) {
				System.out.println("a보다 큰 값을 입력하세요");
			} else {
				break;
			}
			//2. 두번째 방법
//			if (b > a)
//				break;
//			System.out.println("a보다 큰 값을 입력하세요");
		}
	
		System.out.println("b - a는 " + (b-a) + "입니다");
	}
}

5. 양의 정수의 자릿수

=> 1의 자리, 2의 자리, 3의 자리...

package chap01_2;

import java.util.Scanner;

public class Quiz11 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n;
		int count = 0; //자리수 하나씩 세기
		
		do {
			System.out.print("양의 정수 입력: ");
			n = scan.nextInt();
		} while (n <= 0);
		
		while(n > 0) {
			n = n/10; //n을 10으로 나누고 다시 n에 넣음
			count++; //count 하나씩 증가
		} //n이 0보다 작거나 같으면 끝남
		
		System.out.println("자릿수는 "  + count + "입니다.");
	}
}

구조적 프로그래밍

Structured Programming
하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법
순차, 선택, 반복의 흐름 사용

1. 입력값을 2자리 양수로 제한

package chap01_2;

import java.util.Scanner;

public class Digits {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int num; //2자리의 양수(10~99)를 입력
		
		do { //무조건 한번은 실행 후 조건 확인 - 조건이 맞지 않으면 다시 실행			
			System.out.print("2자리의 정수 입력: "); num = scan.nextInt();
		} while (num < 10 ||  num > 99); //num >= 10 && num <= 99 하면 안되는 이유: 조건이 true이면 do~while 반복
		
		System.out.println("변수 num의 값은 " + num + "가(이) 되었습니다.");
	}
}

다중 루프

반복 안에서 다시 반복
반복 루트가 중첩되는 수준에 따라 이중 루프, 삼중 루프

1. 곱셈표 출력

맨 윗쪽은 for 사용 x

System.out.println("  |  1 2 3 4 5 6 7 8 9");
System.out.println("--+------------------------");
	for(int i = 1; i <= 9; i++) {
		System.out.print(i+" |");
		for(int j = 1; j <= 9; j++) {
			System.out.printf("%3d", i*j);
		}
		System.out.println();
	}

전부 반복(for) 사용

System.out.print("  |");
	for(int i=1; i <= 9; i++) {
		System.out.printf("%3d",i); //%3 정수에 대해 세칸의 넓이로 출력하라
	}
	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();
	}

2. 입력한 수를 한 변으로 하는 정사각형

package chap01_2;

import java.util.Scanner;

public class Quiz14 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int num;
		
		System.out.println("사각형을 출력합니다.");
		System.out.print("단 수: "); num = scan.nextInt();
		
		for(int i = 1; i <= num; i++) {
			for(int j = 1; j <= num; j++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}
}

직각 이등변 삼각형 출력

//왼쪽 아래
	static void triangleLB(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= i; j++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

	//왼쪽 위
	static void triangleLU(int n) {
		/*
		 * for(int i = 1; i <= n; i++) {
		 * 		for(int j = i; j <= n; j++) {
		 * 			System.out.print("*");
		 * 		}
		 * 		System.out.println();
		 * }
		 */
		for(int i = n; i >= 1; i--) {
			for(int j = i; j >= 1; j--) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

	//오른쪽 위
	static void triangleRU(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= i-1; j++) {				
				System.out.print(" ");
			}
			for(int j = n-1; j >= i-1; j--) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

	//오른쪽 아래
	static void triangleRB(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = i; j <= n-1; j++) {
				System.out.print(" ");
			}
			for(int j = i-1; j >= 0; j--) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

1. n단의 피라미드 (조건 암기)

package chap01_2;

import java.util.Scanner;

public class Quiz16 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n;
		
		do {
			System.out.print("n단의 피라미드: ");
			n = scan.nextInt();			
		} while (n <= 0);
		spira(n);
	}
	
	static void spira(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = i-1; j <= n-2; j++) { //앞 부분 띄우기, int j = 1; j <= n - i + 1; j++ 이렇게 해도 됨
				System.out.print(" ");
			}
			for(int j = 1; j <= (i-1)*2 +1; j++) {
				System.out.print("*");
			}
			System.out.println(); //한 줄 쓰면 다음줄로 이동
		}
	}
}

2. n단의 숫자 피라미드

package chap01_2;

import java.util.Scanner;

public class Quiz17 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n;
		
		do {
			System.out.print("n단의 숫자 피라미드: ");
			n = scan.nextInt();
		} while (n <= 0);
		npria(n);
	}
	
	static void npria(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n-i; j++) {
				System.out.print(" ");
			}
			for(int j = 1; j <= (i-1)*2+1; j++) {
				System.out.print(i%10);
			}
			System.out.println();
		}
	}
}

가우스의 덧셈

덧셈의 교환, 결합 법칙을 이용해 1~n까지의 합을 계산
자연수에서 덧셈으로 구성된 식은 수의 계산 순서나 배열을 바꿔서 계산해도 결과는 항상 같음

1+2+3+4+5+6+7+8+9
+9+8+7+6+5+4+3+2+1
= 10+10+10+10+10+10+10+10+10
= 90 = 45+45
* 1 ~ 9까지의 합: 45

1+2+3+4+5+6+7+8+9
= (1+9)+(2+8)+(3+7)+(4+6)+5
= 10+10+10+10+5
= 45

단축 평가

논리 연산자
1. 논리곱 - x && y, 둘 다 참이면 참
2. 논리합 - x || y, 둘 중 하나라도 참이면 참
논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우,
오른쪽 피연산자의 평가를 수행하지 않는 것

드모르간 법칙

각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다

x && y == !(x || y)
x || y == !(x && y)

728x90

'Study > Data Structure&Algorithm' 카테고리의 다른 글

[자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 ??? (0)	2023.05.08
[자료구조&알고리즘] stack(스택), queue(큐) (0)	2023.05.07
[알고리즘] 유클리드 호제법 (Euclidean algorithm), 약수, 배수 (0)	2023.04.25
[자료구조&알고리즘] 검색(검색 알고리즘, 선형검색, 이진검색) (0)	2023.04.25
[자료구조&알고리즘] 기본 자료구조(배열, 클래스) (0)	2023.04.18

기본 알고리즘

용어

최댓값 구하기

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

표준 스트림(standard streams) ***보충하기

순서도

순서도의 기호

최댓값 만들기(1)

최솟값 구하기

세 값의 대소 관계와 중앙값

중앙값 구하기

반복

while문

for문

1. 1+2+3+4+...+n = sum (1부터 n까지의 합)

2. 가우스의 덧셈 (1부터 n까지의 합)

3. a ~ b 까지의 합

4. b - a 출력

5. 양의 정수의 자릿수

구조적 프로그래밍

1. 입력값을 2자리 양수로 제한

다중 루프

1. 곱셈표 출력

2. 입력한 수를 한 변으로 하는 정사각형

직각 이등변 삼각형 출력

1. n단의 피라미드 (조건 암기)

2. n단의 숫자 피라미드

가우스의 덧셈

단축 평가

드모르간 법칙

'Study > Data Structure&Algorithm' 카테고리의 다른 글

검색 태그

최근 댓글

티스토리툴바

표준 스트림(standard streams) *보충하기**