sort, recursion

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

잇(IT)생 챌린지

목록 보기
55/90

알고리즘 카테고리 정리

1. 자료구조

  • List, Map, Set
  • 배열
  • 스택, 큐, 연결리스트
  • 그래프, 트리

2. 알고리즘

1) 탐색

  • 순차탐색
  • 이진탐색

2) 정렬 sort

[비효율적인 정렬]
비효율적이지만 구현은 단순

  • 버블정렬 (O(n2))-> 수행시간 가장 느림
  • 선택정렬 (O(n2))
  • 삽입정렬 (O(n2))

[효율적인 정렬]

  • 병합정렬(분할정복)
  • 합정렬
  • 기수정렬

3) 재귀 recursion

4) 문자열검색
5) 그리디 알고리즘
6) 깊이우선탐색(DFS : Depth-First Search)
: 그래프 완전 탐색 기법 (스택활용)

7) 너비우선탐색(BFS : Breadth-First Search)
: 그래프 완전 탐색 기번(Queue 활용)

실습

sort 정렬

211p

SelectionSortTest

선택정렬 알고리즘을 적용해서 구현하기

public class SelectionSortTest {
	public static void main(String[] args) {
		int[] arr = {77,19,22,23,7,4,5};
		System.out.println(Arrays.toString(arr));
		for(int i=0;i<arr.length;i++) {
			//순서대로 앞에서부터 작은값을 위치할 것이므로 i
			//작은 값을 만나는 경우 index를 저장
			int minIndex = i;//최초작업은 minIndex=0이라는 것
			for(int j=i+1;j<arr.length;j++) {
				if(arr[minIndex]>arr[j]) {//현재 작은 값보다 더 작은 값을 만나는 경우 index를 변경
					minIndex = j;
				}
			}//첫 번째 순회가 완료되면 minIndex가 제일 작은 요소가 저장된 index
			//swap
			int temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
			System.out.println(Arrays.toString(arr));
		}
		System.out.println("==================");
		System.out.println(Arrays.toString(arr));
	}
}

Baek_1427_sort

선택정렬로 내림차순 정렬하기

public class Baek_1427_sort {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String data = br.readLine();
		int[] myarr = new int[data.length()];
		for(int i=0;i<myarr.length;i++) {
			myarr[i] = Integer.parseInt(data.charAt(i)+"");
		}
		for(int i=0;i<myarr.length;i++) {
			int maxIndex = i;//가장 큰 값이 현재 맨 앞의 요소라고 가정하고 작업
			for(int j=i+1;j<myarr.length;j++) {
				if(myarr[maxIndex]<myarr[j]) {//max값보다 큰 값이 있는지 확인
					maxIndex = j;
				}
			}
			int temp = myarr[i];
			myarr[i] = myarr[maxIndex];
			myarr[maxIndex] = temp;
			System.out.println(Arrays.toString(myarr));
		}
	}
}

InsertionSortTest

삽입정렬을 이용해서 정렬하세요(오름차순)

public class InsertionSortTest {
	public static void main(String[] args) {
		int[] arr = {42,32,24,60,40};
		System.out.println(Arrays.toString(arr));
		//0번요소는 정렬된 값이라 판단하고 작업
		//정렬되지 않은 영역에서 첫번째 데이터
		for(int i=1;i<arr.length;i++) {
			//정렬된 영역의 마지막 데이터부터 역순(뒤에서부터 앞으로 가면서)으로 비교
			for(int j=i;j>0;j--) {
				System.out.println("i="+i+", j="+j+", arr[j]=>"+arr[j]+", arr[j-1]=>"+arr[j-1]);
				if(arr[j]<arr[j-1]) {
					//더 작은 값을 앞으로 이동 => 작은값을 비교 요소의 왼쪽 앞으로 삽입
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}else {
					//앞쪽에 있는 요소에서 작은 값을 만나면 이미 정렬되어 있으므로 더 비교할 필요가 없다.
					break;
				}
				System.out.println(Arrays.toString(arr));
			}
			System.out.println();
		}
		//최종완료
		System.out.println(Arrays.toString(arr));
	}
}

recursion 재귀

RecursionTest1

적어도 하나는 재귀에 빠지지 않는 경우의 수가 존재해야 한다.
빠져나오기 위한 조건이 있어야 한다. - base cases

public class RecursionTest1 {
	public void Test(int count) {
		if(count<=0) {
			return;//void메소드에서 return하면 메소드 실행을 종료하고 호출한 곳으로 되돌아간다.
		}
		System.out.println("재귀알고리즘");
		Test(count-1);
	}
	public static void main(String[] args) {
		RecursionTest1 obj = new RecursionTest1();
		obj.Test(5);
		System.out.println("end");
	}
}

RecursionExam1

public class RecursionExam1 {
	public static void main(String[] args) {
		//length 호출해서 "java"라는 문자열의 길이를 리턴할 수 있도록 처리하세요.
		int result = length("java");
		System.out.println("문자열의 길이="+result);
	}
	public static int length(String str) {
		//재귀를 이용해서 문자열의 길이를 구할 수 있도록 작업
		//System.out.println(str.substring(1));
		if(str.equals("")) {
			return 0;
		}else {
			return 1+length(str.substring(1));
		}
	}
}

RecursionExam2

  • subArr는 수정가능
  • 배열의 합을 구할 수 있도록 작업 - 매개변수는 알아서 정의(수정가능)
  • 배열의 합을 재귀를 이용해서 처리
  • input데이터가 점진적으로 변할 수 있도록 정의(대부분은 하나씩 줄어들도록 작업) - 재귀호출을 빠져나올 수 있는 조건
public class RecursionExam2 {
	public static void main(String[] args) {
		int[] arr = {55,88,77,99,100};
		System.out.println(sumArr(arr, arr.length));
	}
	public static int sumArr(int[] arr, int size) {
		if(size<=0) {
			return 0;
		}else {
			//System.out.println(arr[size-1]);
			return sumArr(arr, size-1)+arr[size-1];
		}
	}
}

FactorialTest

public class FactorialTest {
	public int factorial(int num) {
		int result = 0;
		if(num==0) {
			result = 1;
		}else {
			result = num * factorial(num-1);
		}
		return result;
	}
	public static void main(String[] args) {
		FactorialTest obj = new FactorialTest();
		System.out.println(obj.factorial(5));
		System.out.println("-------------");
		int sum = 1;
		for(int i=1;i<=5;i++) {
			sum = sum * i;
		}
		System.out.println(sum);
	}
}

Fibonacci_ArrayTest

  • 피보나치수열을 배열로 처리
  • 피보나치 : 첫째와 둘째항이 1로 표현 i-1,i-2의 합으로 구성
  • 5 -> 1 1 2 3 5
public class Fibonacci_ArrayTest {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int num = key.nextInt();
		
		int[] arr = new int[num];
		arr[0] = 1;
		arr[1] = 1;
		for(int i=2;i<num;i++) {
			arr[i] = arr[i-2]+arr[i-1];
		}
		System.out.println(Arrays.toString(arr));
	}
}

FibonacciRecursionTest

public class FibonacciRecursionTest {
	public static int getFibonacci(int count) {
		int result =0;
		if(count==1 | count==2) {
			result = 1;
		}else {
			result = getFibonacci(count-2)+getFibonacci(count-1);
		}
		return result;
	}
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int num = key.nextInt();
		for(int i=1;i<=num;i++) {
			System.out.print(getFibonacci(i)+"\t");
			if(i%5==0) {
				System.out.println();
			}
		}
	}
}

FibonacciRecursionTest_ver2

  • 배열에 저장하고 리턴
  • 배열에 저장된걸 꺼내서 출력할 수 있도록 작업
  • 배열은 static멤버변수로 정의
public class FibonacciRecursionTest_ver2 {
	static int myarr[];
	public static int getFibonacci(int count) {
		int result =0;
		if(count==1 | count==2) {
			return myarr[count] = 1 ;
		}else {
			return myarr[count] = getFibonacci(count-2)+getFibonacci(count-1);
		}
		//return result;
	}
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int num = key.nextInt();
		myarr = new int[num+1];
		getFibonacci(num);
		for(int i=1;i<=num;i++) {
			System.out.print(myarr[i]+"\t");
			if(i%5==0) {
				System.out.println();
			}
		}
	}
}

FibonacciRecursionTest_Memoization

  • 배열에 저장하고 리턴
  • 한 번 작업했던 내용은 기록해놓고 재사용하기 - 이미 저장된 것은 다시 메소드로 호출하지 않고 배열에 저장된 것을 꺼내서 리턴하는 코드로 수정하기
  • 코드추가
    => 얘가 가장 빠름
public class FibonacciRecursionTest_Memoization {
	static int myarr[];
	public static int getFibonacci(int count) {
		//이미 저장된 것은 다시 메소드를 호출하지 않고 배열에 저장된 것을 꺼내서 리턴하는 코드로 수정하기
		if(myarr[count]>0) return myarr[count];
		if(count==1 | count==2) {
			return myarr[count] = 1 ;
		}else {
			return myarr[count] = getFibonacci(count-2)+getFibonacci(count-1);
		}
		//return result;
	}
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int num = key.nextInt();
		myarr = new int[num+1];
		getFibonacci(num);
		for(int i=1;i<=num;i++) {
			System.out.print(myarr[i]+"\t");
			if(i%5==0) {
				System.out.println();
			}
		}
	}
}

기타

멘토링

  • 실무 관련한 질문을 해보기
  • 주요 이슈, 동향, 기술, 서비스 등
  • 어떤 질문할지 고민해보기

데이터 질문드림

  • 공공기관 제공 데이터 : data.go.kr
    (csv, json, xml, xls) => csv는 비버 이용해서 테이블로 변경 가능
  • 데이터가 원하는 내용이 아니라면 적절하게 가공하는 작업 거칠 수 있음
  • 협회, 데이터센터 등이 있으니 주제 관련하여 찾아보기
  • 데이터를 찾지 못하면 크롤링(jsoup)으로 벗기기

프로젝트 과정 조사하고 구성해보기

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

profile
brave_chicken
이전 포스트

search, sort

다음 포스트

제네릭, 연결리스트

0개의 댓글