객체 정렬은 Comparable, Comparator 인터페이스를 적용해 구현할 수 있다.
두 인터페이스는 객체를 비교한다는 점은 같지만, 어떤 대상을 비교하는지가 다르다.
byte, char, double, short, long, int, float 와 같은 Primitive Type 배열에는 적용이 불가능하기 때문에, Wrapper Class를 이용해야 한다.
Comparable의 compareTo 메서드는 자기 자신과 매개변수 객체(o)를 비교한다.
public class ComparableExample implements Comparable<Type> {
@Override
public int compareTo(Type o) {
return this.member - o.member; // 정렬 기준이 되는 맴버 변수 지정
}
}
Arrays.sort(array)
Collections.sort(list)
Comparator의 compare 메서드는 두 매개변수 객체(o1과 o2)를 비교한다.
public class ComparatorExample {
public static void main(String[] args) {
// 익명 Comparator 객체 구현
public static Comparator<Type> comparator1 = new Comparator<Type>() {
@Override
public int compare(Type o1, Type o2) {
return o1.member - o2.member; // 정렬 기준이 되는 맴버 변수 지정
}
}
}
Arrays.sort(array, myComparator)
Collections.sort(list, myComparator)
반환값이 0 또는 음수이면 자리가 그대로 유지되며, 양수인 경우에는 두 객체의 자리가 바뀐다.
현재 객체
< 파라미터로 넘어온 객체
→ 음수 리턴현재 객체
== 파라미터로 넘어온 객체
→ 0 리턴현재 객체
> 파라미터로 넘어온 객체
→ 양수 리턴현재 객체
- 파라미터로 넘어온 객체
nPr의 의미는 n개의 숫자에서 r개를 뽑아 정렬하는 가짓수이다.
순열은 중복을 허락하지 않기 때문에, visited
배열을 통해 방문 여부를 확인한다.
/*
순열 구현 코드
- r: 뽑고자 하는 개수
- temp: r개를 뽑은 결과값을 저장해놓은 배열
- current: 현재 개수를 저장해 놓는 값
- visited: 방문 여부를 확인하는 배열
*/
public static void makePermutation(int r, int[] temp, int current, boolean[] visited){
if(r == current){
// r개의 수를 선택했다면 출력
System.out.println(Arrays.toString(temp));
}else{
for(int i = 0; i < arr.length; i++){
if(!visited[i]){
visited[i] = true; // 아직 방문하지 않았다면 방문 처리
temp[current] = arr[i]; // 방문한 숫자를 결과에 추가
makePermutation(r, temp, current + 1, visited); // 다음에 방문할 숫자 탐색
visited[i] = false; // 방문 처리 해제
}
}
}
}
makePermutation
함수는 재귀적으로 동작하며, 1개의 숫자를 뽑아 방문 처리를 한 후 결과 리스트에 추가하는 과정을 반복한다.
makePermutation
을 호출한다.nCr의 의미는 n개의 숫자에서 r개를 뽑는 경우의 수이다.
조합에서는 순서가 중요하지 않기 때문에 visited
배열이 필요하지 않다. 하지만 이미 선택한 숫자는 선택하지 않기 때문에, 다음 숫자를 start 인덱스를 계속 증가시키며 start 이후의 값들 중에서 뽑을 수 있도록 범위를 제한한다.
/*
조합 구현 코드
- r: 뽑고자 하는 개수
- temp: r개를 뽑은 결과값을 저장해놓은 배열
- current: 현재 개수를 저장해 놓는 값
- start: 그 다음 반복문을 시작하는 값
*/
public static void makeCombination(int r, int[] temp, int current, int start){
if(r == current){
// r개의 수를 선택했다면 출력
System.out.println(Arrays.toString(temp));
}else{
for (int i = start; i < arr.length; i++){ // 이미 선택한 대상을 제외하기 위해 start 인덱스 부터 순회
temp[current] = arr[i];
makeCombination(r, temp, current + 1, i + 1);
}
}
}
makeCombination
함수는 재귀적으로 동작하며, start 인덱스 이후의 범위에서 1개의 숫자를 뽑아 결과 리스트에 추가하는 과정을 반복한다. start 인덱스는 이미 뽑은 값을 제외하기 위해 계속 증가한다.
makeCombination
을 호출한다.중복 순열은 숫자가 중복되어도 되기 때문에 visited 배열이 필요 없다.
/*
중복순열 소스코드
- r: 뽑고자 하는 개수
- temp: r개를 뽑은 결과값을 저장해놓은 배열
- current: 현재 개수를 저장해 놓는 값
*/
public static void makeOverlapPermutation(int r, int[] temp, int current){
if(r == current){
System.out.println(Arrays.toString(temp));
}else{
for(int i = 0; i < arr.length; i++){
// 중복 순열은 숫자가 중복되어도 되기 때문에 visited 배열이 필요 없다
temp[current] = arr[i];
makeOverlapPermutation(r, temp, current + 1);
}
}
}
중복 조합이므로 현재 선택한 값이 또 나올 수 있게 start 인덱스를 유지한다.
/*
중복조합 소스코드
- r: 뽑고자 하는 개수
- temp: r개를 뽑은 결과값을 저장해놓은 배열
- current: 현재 개수를 저장해 놓는 값
- start: 그 다음 반복문을 시작하는 값
*/
public static void makeOverlapCombination(int r, int[] temp, int current, int start){
if(r == current){
System.out.println(Arrays.toString(temp));
}else{
for(int i = start; i < arr.length; i++){
temp[current] = arr[i];
makeOverlapCombination(r, temp, current + 1, i); // 중복 조합이므로 현재 선택한 값이 또 나올 수 있게 start 인덱스를 유지
}
}
}
BFS와 DFS는 그래프를 탐색하는 방법 중 하나로 탐색 시 어떤 노드(정점)를 우선적으로 방문하느냐에 따라 나뉜다.
출처: https://velog.io/@lucky-korma/DFS-BFS의-설명-차이점
BFS는 큐를 이용해 구현한다.
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// BFS 함수 정의
public static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드를 방문처리
visited[start] = true;
// 큐가 빌때까지 반복
while(!q.isEmpty()){
// 큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
System.out.println(x + " ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++){
int y = graph.get(x).get(i);
if(!visited[y]){
q.offer(y);
visited[y] = true;
}
}
}
}
offer
)하고 방문 처리를 한다.poll
) → 이때 큐에서 노드를 꺼낸 순서가 BFS 탐색 순서이다.offer
)하고 방문 처리를 한다.출처: https://velog.io/@lucky-korma/DFS-BFS의-설명-차이점
DFS는 재귀함수와 스택을 이용해 구현한다.
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// DFS 함수 정의
public static void dfs(int x){ // x: 노드 번호
// 현재 노드를 방문 처리
visited[x] = true;
System.out.println(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for(int i = 0; i < graph.get(x).size(); i++){
int y = graph.get(x).get(i);
if(!visited[y]) dfs(y);
}
}
dfs
함수에 전달하여, 다음 시퀀스를 반복한다.dfs
를 재귀적으로 호출한다.이진 탐색은 정렬된 리스트에서 원하는 값을 고속으로 탐색하는 방법이다.
**O(logn)**
과 같다고 볼 수 있다.리스트에 특정 값이 있는지 빠르게 확인하는 방법이다.
start
)과 끝점(end
)가 만나지 않는 동안, 탐색 범위를 반으로 줄이는 과정을 반복한다.start
)이 끝점(end
)보다 크면 종료한다.// 이진 탐색 소스코드 구현(재귀함수)
public static int binarySearch(int[] arr, int target, int start, int end){
if(start > end) return -1;
int mid = (start + end) / 2;
if(arr[mid] == target){
// 찾은 경우 중간점 인덱스 반환
return mid;
}else if(arr[mid] > target){
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
return binarySearch(arr, target, start, mid-1);
}else{
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
return binarySearch(arr, target, mid+1, end);
}
}
start
)이 끝점(end
)보다 작거나 같은 동안 반복한다. // 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end){
while(start <= end){
int mid = (start + end) / 2;
if(arr[mid] == target){
// 찾은 경우 중간점 인덱스 반환
return mid;
}else if(arr[mid] > target){
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
end = mid - 1;
}else{
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
start = mid + 1;
}
}
return -1;
}
int[] arr = {3, 4, 1, 2, 5};
Arrays.sort(arr); // 이진 탐색 전 배열 정렬
int index = Arrays.binarySearch(arr, 4);
이진 탐색의 원리를 이용해 최적화 문제를 결정 문제로 바꾸는 방법이다.
cf. 개인적으로 최적화 문제에서 결정 문제를 만드는 것은 조건과 결과를 뒤집는 것이라고 생각한다. 리스트를 정렬했기 때문에, 최적값은 조건을 만족하는지 여부로 결정짓는 문제로 변경할 수 있다.
동적 계획법은 복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하는 방법이다.
// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
public static long[] d = new long[100];
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
public static long fibo(int x) {
// 종료 조건(1 혹은 2일 때 1을 반환)
if (x == 1 || x == 2) {
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
public static void fibo(){
public static long[] d = new long[100];
// 첫번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수를 계산
// 피보나치 함수(Fibonnacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for (int i = 3; i <= n; i++){
d[i] = d[i-1] + d[i-2];
}
}
아래 두 가지 조건을 만족하는 문제는 DP를 이용해 해결할 수 있다.