[JAVA] 코딩테스트 '공부'

참고자료:

[취업준비] 신입 개발자 취업 준비 시작하는법 - MangKyu's Diary (tistory.com)

[취업준비] 신입 개발자 취업 준비 시작하는법

 

선택 프로그래밍 언어: JAVA

이유: Spring 백엔드 개발자가 되기 위해서 JAVA를 코딩테스트 언어로 선택하여 공부하는 것이 좋을 것 같다.

 

자바 튜토리얼 총 59회 - 스무디코딩 (smoothiecoding.kr)

자바 튜토리얼 총 59회 - 스무디코딩

 

- 빈출 유형 파악

• 알고리즘 코딩 테스트에서 자주 출제되는 유형은 크게 다음과 같다.
• 구현/ 시뮬레이션: 문제의 요구사항을 주고 이를 구현하거나 시뮬레이션 하는 문제
• 그래프 이론: DFS/ BFS와 관련된 알고리즘 문제
• 자료구조: 다양한 자료구조를 사용하여 문제 해결
• 완전탐색: 모든 경우를 탐색하여 문제 해결

이 외에 다른 부분도 충분히 나올 수 있다.

 

- JAVA 알고리즘 최적화 팁

• 입력을 받기 위해서는 Scanner 보다 BufferedReader를 사용하는 것이 좋음
• 한 줄 입력이 여러 번 들어오는 경우에는 split보다 String Tokenizer를 사용하여 파싱하는 것이 좋음
• 여러 번 출력해야 하는 경우에는 String Builder를 사용해 한번에 출력하는 것이 좋음
• Array를 사용한느 것보다 ArrayList를 사용하는 것이 좋음
• ArrayList를 정렬하기 위해서는 Collections.sort()를 사용하는 것이 좋음
• 배열을 초기화하기 위해서는 java.util.Arrays의 Arrays.fill(배열, 초기화값)을 사용하는 것이 좋음 

 

- 추천 공부 순서

1. 기본 문법 100제
2. 그리디 알고리즘
3. 탐색 알고리즘
4. 기본 동적 프로그래밍
5. 그래프이론, 중-고급 동적 프로그래밍, 문자열 처리

*코스포스 블루레벨 or 삼성 역량 테스트 B형 정도 수준까지 끌어올리기, 컴퓨터 사고력이 중요, 어려운 수학문제 X

 

탐욕 알고리즘: 

탐욕 알고리즘은 최적해를 구하는 상황에서 사용하는 방법, 여러 경우 중 하나를 선택할 때 그것이 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식으로 진행하여 답을 구한다. 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식이기 때문에 가장 좋은 결과를 얻는 것이 보장되는 것은 아니다.

 

다음 알고리즘이 사용되는 예제 문제:

지불해야 하는 값이 1260원 일 때 500원, 100원, 50원,10원 짜리 동전으로 동전의 수가 가장 적게 지불하시오.

public class Example{
	public static void main (String[] args) {
		int[] coin = {500,100,50,10};
		int value = 1260;
		int answer[] = coin(value, coin);
		for(int item: answer) {
			System.out.print(item + " ");
		}
	}
	public static int[] coin(int value, int[] coin) {
		int [] answer = new int[coin.length];
		for(int i=0; i<coin.length; i++) {
			answer[i] = value/coin[i];
			value = value%coin[i];
		}
		return answer;
	}
}

 

재귀 알고리즘:

재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한루프를 방지할 수 있다.

구구단 예제:

public class Example{
	public static void main (String[] args) {
		gugudan2(9);
	}
	public static int gugudan2(int num) {
		if(num == 0) {
			System.out.println("end");
			return 1;
		}
		else {
				System.out.println(2 + " X" + num + " = " + 2*num);
				return gugudan2(num-1);
			}
		}
}

 

탐색 알고리즘:

1. 순차 탐색: 가장 간단하며 누구나 사용하는 탐색 방법이다. 배열에서 찾고자하는 값이 있으면 배열의 첫 번째부터 하나하나 탐색해가는 방법이다. 비효율적이라는 단점이 있다.

public class Example{
	public static void main (String[] args) {
		int [] data = {1,2,3,4,5};
		int a = 6;
		boolean chk = false;
		for(int i: data) {
			if(a == i) {
				chk = true;
				break;
			}
		}
		System.out.println(chk);
	}
}

 

2. 이진 탐색: 이진 탐색이란 탐색 알고리즘 중 아주 직관적이고 간단한 알고리즘이다. 한번 비교할 때마다 검색할 데이터의 양이 반씩 줄어드는 형태로 검색을 진행하기 때문이다.

public class Example {
	static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100};

	public static void main(String[] args) {
		System.out.println("1. 순환 호출을 이용한 이진 탐색");
		System.out.println(binarySearch1(5, 0, arr.length-1)); // 2
		
		System.out.println("\n2. 반복을 이용한 이진 탐색");
		System.out.println(binarySearch2(20, 0, arr.length-1)); // 6
		
	}
	
	// 재귀적 탐색
	static int binarySearch1(int key, int low, int high) {
		int mid;
		
		if(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) { // 탐색 성공 
				return mid;
			} else if(key < arr[mid]) {
				return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
			} else {
				return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
			}
		}
		
		return -1; // 탐색 실패 
	}
	
	// 반복적 탐색
	static int binarySearch2(int key, int low, int high) {
		int mid;
		
		while(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) {
				return mid;
			} else if(key < arr[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		
		return -1; // 탐색 실패 
	}

}

 

정렬 알고리즘:

1. 선택 정렬: 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식, 각 위치에 최소값을 차례대로 넣어간다.

public class Example{
	public static void main (String[] args) {
		int [] arr = {5,3,1,2,4};
	
		for(int i=0; i<arr.length; i++) {
			for(int j=i+1; j<arr.length; j++) {
				if(arr[i]>arr[j]) { //>일 경우 오름차순, <일 경우 내림차순
					int temp = arr[i]; // 임시 저장
					arr[i] = arr[j]; // i에 제일 작은 값이 올 수 있도록
					arr[j] = temp;
				}
			}
		}
		for(int item: arr) {
			System.out.print(item + " ");
		}
	}
}

 

2. 삽입 정렬: 삽입 정렬이란 앞의 숫자들을 정렬된 상태라고 가정한 뒤 정렬되지 않은 숫자들을 하나씩 빼서 정렬되어 있는 숫자 사이의 올바른 위치에 삽입하는 정렬 방법, 2번째부터 기준이 되어 시작하고 알고리즘의 특성상, 기준의 왼쪽 값들은 모두 정렬되어 있다.

public class Example{
	public static void main (String[] args) {
		int[] a = {10,2,6,4,3,7,5};
		int temp;
		
		for(int i=1; i<a.length; i++) {
			int standard = a[i]; //기준
			int aux = i-1; //비교할 대상
			
			while(aux>=0 && standard < a[aux]) {
				a[aux+1] = a[aux]; //비교대상이 큰 경우 오른쪽으로 밀어냄
				
				aux--;
			}
			a[aux+1] = standard; //기준값 저장
		}
		
		for(int item: a) {
			System.out.print(item + " ");
		}
	}
}

* 처음부터 끝까지 돌아보며 비교하여 올바론 위치에 넣어주는 반복문이나 재귀를 사용할 수 있다.

 

3. 버블정렬: 버블 정렬은 두 인접한 값들을 검사하여 정렬하는 방법이다. 시간이 매우 오래 걸리는 알고리즘 중 하나지만 코드가 단순하기 때문에 자주 사용되는 방법이다.

*버블 정렬을 간단히 구현하면 for loop 문 2개로 간단하게 구현할 수 있다는 점이 장점이다. 다만 모든 수들을 계산해야 하기 때문에 오래 걸리는 부분이 단점이다.

public class Example{
	public static void main (String[] args) {
		int[] a = {3,2,4,1};
		int temp;
		
		for(int i=0; i<a.length-1; i++) {
			for (int j=0; j<a.length-1-i;j++) {
				if(a[j] > a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		for(int item: a) {
			System.out.print(item);
		}
	}
}

 

최단거리 알고리즘:

최단거리 알고리즘은 한 지점에서 다른 지점까지의 최단거리를 구할때 사용하는 알고리즘이다. 이 알고리즘은 가장 적은 비용으로 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용할 수 있다.

 

다음 알고리즘이 사용되는 예제 문제:

집에서 학교까지의 최단거리는 얼마인지 구하시오.

 

몬테 카를로 알고리즘: 

몬테 카를로 알고리즘은 난수 생성과 그에 따른 확률 계산을 기반으로 하는 알고리즘인데 알고리즘의 개발자인 스타니스와프 울람이 난수와 확률 계산을 도박에서 연상시켜 알골지므 이름을 몬테 카를로 알고리즘으로 명명했다.

무작위로 난수를 생성하고 생성된 난수를 기반으로 사용해서 구하고자 하는 정보의 확률을 계산한다. 난수 생성이 무한에 가까워 질 경우 우리가 원하는 정보의 실제 값으로 근사한다.

 

기본 동적 프로그래밍(DP):

동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. 

 

- DP의 특성1: 중복되는 부분 문제(Overlapping Subproblem)

분할 정복과 동적 프로그래밍의 가장 큰 차이이다. 분할 정복은 "큰 문제"가 "유니크한 부분 문제"로 나뉘지만 동적 프로그래밍은 "부분 문제"가 반복적으로 등장한다.

- DP의 특성2: 최적 부분 구조(Optimal Substructure)

"큰 문제"의 해를 찾기 위한 연산과 "부분 문제"의 해를 찾기 위한 연산이 동일해야 하며 "부분 문제"의 해를 조합해 "큰 문제"의 해를 찾을 수 있는 구조를 "최적 부문 구조"라고 한다.