알고리즘

brave_chicken·2024년 5월 21일
algorithm잇(IT)생 챌린지

잇(IT)생 챌린지

목록 보기
52/90

알고리즘 참고사이트

배열

빅오표기법

[Big-O](Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell (bigocheatsheet.com))
빅오표기법(Big-O 표기법)은 알고리즘의 성능을 분석하는 데 사용되는 수학적 표기법으로, 주로 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 데 사용됩니다. 이 표기법은 입력 크기(n)가 커질 때 알고리즘의 실행 시간이나 사용되는 메모리가 어떻게 변하는지를 설명합니다. 빅오표기법은 알고리즘의 성능을 최악의 경우를 기준으로 평가하기 때문에, 최악의 시나리오에서도 알고리즘이 얼마나 효율적인지 파악할 수 있습니다.

빅오표기법의 주요 종류

  • O(1) - 상수 시간: 입력 크기에 상관없이 실행 시간이 일정한 경우입니다.
    ex. 배열의 첫 번째 요소에 접근하기.

  • O(log n) - 로그 시간: 입력 크기가 커짐에 따라 실행 시간이 로그 형태로 증가하는 경우입니다.
    ex. 이진 탐색.

  • O(n) - 선형 시간: 입력 크기에 비례하여 실행 시간이 증가하는 경우입니다.
    ex. 배열의 모든 요소를 한 번씩 순회하는 경우.

  • O(n log n): 실행 시간이 입력 크기와 그 로그 값의 곱에 비례하는 경우입니다.
    ex. 효율적인 정렬 알고리즘들(병합 정렬, 퀵 정렬 등).

  • O(n^2) - 이차 시간: 실행 시간이 입력 크기의 제곱에 비례하여 증가하는 경우입니다.
    ex. 이중 루프를 사용하는 알고리즘(버블 정렬 등).

  • O(2^n) - 지수 시간: 실행 시간이 입력 크기의 지수 함수로 증가하는 경우입니다.
    ex. 피보나치 수열을 단순 재귀로 계산하는 경우.

  • O(n!) - 팩토리얼 시간: 실행 시간이 입력 크기의 팩토리얼에 비례하여 증가하는 경우입니다.
    ex. 순열을 생성하는 알고리즘.

빅오표기법은 알고리즘의 효율성을 비교하고 최적의 알고리즘을 선택하는 데 중요한 역할을 합니다. 각 표기법은 알고리즘이 커지는 입력 값에 대해 어떻게 성능이 변하는지를 직관적으로 보여줍니다.

SearchNumber

시간복잡도 테스트 - 빅오표기법

빅오표기법은 최악의 경우를 체크하는 표기법으로 불필요한 연산을 제거해서 알고리즘 분석을 쉽게 하기 위한 목적으로 사용

  • 시간복잡도 - 실행되는 연산의 횟수(cpu의 처리속도)
  • 공간복잡도 - 실행될때 사용하는 메모리
public class SearchNumber {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int[] numArr = {20,40,60,70,90};
		System.out.println("숫자입력:");
		int searchNum = key.nextInt();
        
		//searchNum을 찾는 코드를 구현하세요 - searchNum이 몇번만에 찾아지는지 테스트
		//[출력형태]
		//숫자 입력:20
		//1회에 찾기 성공!! O(n)
		for(int i=0;i<numArr.length;i++) {
			if(numArr[i]==searchNum) {
				System.out.println((i+1)+"회에 찾기 성공~~");
			}
		}
	}
}

Hello World 출력 -> main메소드로 변경

Baek_10950_Scanner

  • 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.
    첫째 줄에 테스트 케이스의 개수 T가 주어진다.
    각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10) 각 테스트 케이스마다 A+B를 출력한다.
    5
1 1
2 3
3 4
9 8
5 2

[출력값]
2
5
7
17
7

1. 테스트케이스 갯수가 정해진 경우
2. Scanner를 이용
public class Baek_10950_Scanner {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int count = key.nextInt();//테스트케이스 갯수
		for(int i=1; i<=count; i++) {
			System.out.println(key.nextInt()+key.nextInt());
		}
	}
}

Baek_10950_BufferedReader로 변경

public class Baek_10950_BufferedReader {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int count = Integer.parseInt(br.readLine()) ;//테스트케이스 갯수
		for(int i=1; i<=count; i++) {
			String line = br.readLine();
			String[] resultArr = line.split(" ");
			System.out.println(Integer.parseInt(resultArr[0])+Integer.parseInt(resultArr[1]));
		}
	}
}

스캐너보다 버퍼드리더가 빠름

시간 절반됨

Baek_10951_Scanner

  • 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.
  1. 테스트케이스 갯수가 정해지지않은 경우 - EOF를 체크(마지막줄?)
  2. Scanner를 이용 
public class Baek_10951_Scanner {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		while(key.hasNextInt()) {
			System.out.println(key.nextInt()+key.nextInt());
		}
	}
}

Baek_10951_BufferedReader

public class Baek_10951_BufferedReader {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			String line = br.readLine();
			if(line==null) {
				break;
			}
			String[] resultArr = line.split(" ");
			System.out.println(Integer.parseInt(resultArr[0])+Integer.parseInt(resultArr[1]));
		}
	}
}

Baek_10951_BufferedReader_ver2

public class Baek_10951_BufferedReader_ver2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		while((line = br.readLine())!=null) {
			String[] resultArr = line.split(" ");
			System.out.println(Integer.parseInt(resultArr[0])+Integer.parseInt(resultArr[1]));
		}
	}
}

Baek_10951_BufferedReader_ver3

public class Baek_10951_BufferedReader_ver3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		while((line = br.readLine())!=null) {
			String[] resultArr = line.split(" ");
			run(resultArr);
		}
	}
	public static void run(String[] resultArr) {
		System.out.println(Integer.parseInt(resultArr[0])+Integer.parseInt(resultArr[1]));
	}
}

ArrayTest1

  • 배열과 관련된 메소드
  • Arrays클래스는 배열을 다루는데 필요한 기능을 지원하는 클래스
public class ArrayTest1 {
	public static void main(String[] args) {
		//배열의 배교
		int[] myarr = {100,20,40,88,99,78};
		
		//int[] myarr2 = myarr;//얕은복사
		int[] myarr2 = myarr.clone();//깊은복사 - 독립적인 배열을 생성
		
		myarr2[2]=70;
		
		System.out.println("myarr=>"+Arrays.toString(myarr));
		System.out.println("myarr2=>"+Arrays.toString(myarr2));
		
		//배열의 주소비교
		System.out.println(myarr==myarr2);
		//배열의 값을 비교
		System.out.println(Arrays.equals(myarr, myarr2));
		
		Arrays.sort(myarr);//원본이 변경
		System.out.println("myarr=>"+Arrays.toString(myarr));
		
		//배열의 값을 복사
		//특정 배열에서 index사이의 배열요소를 복사해서 다른 배열로 리턴
		//myarr에서 1번인덱스에서 4번-1 인덱스 사이의 배열요소를 새로운 배열로 리턴
		int[] otherArr = Arrays.copyOfRange(myarr, 1, 4);
		System.out.println("otherArr=>"+Arrays.toString(otherArr));
		
		//binarySearch : 매개변수로 전달받은 배열에서 특정 값의 위치값을 반환 
		//=> 내부적으로 이진 검색 알고리즘을 사용해서 검색
		//=> 이진검색 알고리즘을 내부에서 사용하므로 사용전에 정렬이 되어있어야 제대로 동작
		System.out.println(Arrays.binarySearch(myarr, 88));
	}
}

얕은복사

얕은복사 설명


깊은복사

깊은복사 설명

Test

public class Test {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		System.out.println("숫자 3개 입력");
		System.out.print("숫자1: ");
		int num1 = key.nextInt();
		System.out.print("숫자2: ");
		int num2 = key.nextInt();
		System.out.print("숫자3: ");
		int num3 = key.nextInt();
		
		//num1, num2, num3 중 최대값을 구해서 출력하기
		int max = num1;
		if(num2>max) {
			max = num2;
		}
		if(num3>max) {
			max=num3;
		}
		System.out.println("최대값=>"+max);
	}
}

미션. ArrayExam

랜덤값 1000개를 발생시켜 배열에 저장
1. 1부터 1000까지 랜덤값을 배열에 1000개 저장하기(1~1000)
2. 최대값을 구하기
3. 최대값의 갯수를 구하기

public class ArrayExam {
	public static void main(String[] args) {
		int[] myarr = new int[1000];//1000개의 랜덤값
		Random random = new Random();
		
		for(int i=0; i<myarr.length; i++) {
			myarr[i] = random.nextInt(1000)+1;//1000까지의 숫자
		}
		System.out.println(Arrays.toString(myarr));

		int max = myarr[0];
		for(int num:myarr) {
			if(num>max) {
				max = num;
			}
		}
		System.out.println("max=>"+max);
		
		int count = 0;
		for(int num:myarr) {
			if(num==max) {
				count++;
			}
		}
		System.out.println("최대값의 갯수=>"+count);
	}
}

StackTest01

자바에서 stack을 사용하기 위해서 알아야 할 문법

public class StackTest01 {
	public static void main(String[] args) {
		Stack<String> stack = new Stack<>();
		
		//스택에 데이터를 저장하기
		stack.push("java");
		stack.push("servlet");
		stack.push("jsp");
		stack.push("spring");
		
		System.out.println("스택에 저장된 요소의 갯수 : "+stack.size());
		System.out.println("스택에 저장된 요소가 있는지 확인 : "+stack.empty());//스택에 저장된 요소가 없을때 true를 리턴
		System.out.println("스택에 마지막으로 저장된 요소를 확인 : "+stack.peek());
		System.out.println("스택에서 데이터 꺼내기 : "+stack.pop());//팝은 데이터가 꺼내지는것
		System.out.println("스택에 저장된 요소의 갯수 : "+stack.size());
	}
}

미션

Stack클래스를 구현해보세요 - 10828문제

본 포스팅은 멀티캠퍼스의 멀티잇 백엔드 개발(Java)의 교육을 수강하고 작성되었습니다.

profile
brave_chicken
이전 포스트

과제풀이

다음 포스트

Stack, Queue

0개의 댓글