출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.
4-1
Brute Force
맨처음 0번째 부터 차례로 해당 값과 동일한지 확인합니다.
Binary Search
빠르게 찾을 수 있지만 정렬이 되어 있어야만 합니다.
중간값과 비교하며 1/2씩 범위를 줄여나가는 탐색법입니다.
- 1~11 까지의 중앙값은
6입니다. - 7~11 까지의 중앙값은
9입니다. - 7~8 까지의 중앙값은
7입니다. - 8 의 중앙값은
8입니다.
찾고자 하는 값이 중앙값보다 작으면 중앙값의 왼쪽만, 크면 오른쪽만, 동일하면 해당값을 찾는 탐색법입니다.
4-2
객체의 출력, 해당 객체 여부 확인
해당 객체인지, 또 해당 객체가 맞다면 단순히 주소 값이 아닌 내용물은 어떤건지 출력하기 위해서 Object의 메서드를 오버라이딩 할 피요가 있습니다.
객체 출력 : toString()메서드를 오버라이딩 하여 객체의 필드를 출력하면 확인할 수 있습니다.
객체 인지 여부 : 해당 객체가 동일한 값을 갖는지 확인하기 위해선 boolean equals(Object o)메서드를 오버라이딩 해야 합니다.
객체간의 값 비교
객체간의 값을 비교하는 방법은 여러가지가 존재하지만, Collections 클래스를 이용하여 객체간 대소 비교를 해보겠습니다.
객체간 비교하기 위해선 우선 비교할 객체가 Compaarable<클래스> 를 구현하여 추상메서드인 compareTo(클래스)를 구현하여야 합니다.
Class MyData implements Comparable<MyData>{
...
public int compareTo(MyData o){
return v - o. v;
}
}int 타입의 정수를 반환하는 것을 확인할 수 있습니다.
컴퓨터는 대소간의 비교를 두수의 차가 0보다 큰지, 작은지, 같은지를 비교하여 대소를 비교합니다.
// 1 ? 2 : 1 - 2 == 0 : 같다
// < 0 : 오른쪽이 크다
// > 0 : 왼족이 크다
Collections.binarySearch(collection, Object) 는 collection내에 존재하는 object를 이진탐색으로 찾아 인덱스를 반환합니다.
List<MyData> list = new LinkedList<>();
for(int i = 1; i<=100; i++){
list.add(new MyData(i));
}
System.out.println(list);
int index = Collections.binarySearch(list, new MyData(63));
System.out.println(index);
System.out.println(list.get(index));
//출력값
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,..,100] //1부터 100까지
62 // 값이 63인 객체의 인덱스
63 // 62번째 인덱스 객체의 값이진 탐색은 시간복잡도가 O(log n)으로 성능이 준수하나 미리 정렬 되어 있어야 사용할 수 있습니다.
소스코드
package LinearSearch;
import java.util.*;
// search는 indexOf, contains, remove 같은 곳에서 이미 구현되어 있습니다. : 완전탐색
// equals가 제공될 필요가 있다.
//
// 이진탐색 : Collections.binarySearch
// Comparable가 구현되어 있어야 한다.
// 순서대로 정렬되어 있어야 한다.
class MyData implements Comparable<MyData>{
int v;
public MyData(int v) {
this.v = v;
}
@Override
public String toString() {
return "" + v;
}
@Override
public boolean equals(Object o) {
if(this==o)return true;
if(o==null || getClass() != o.getClass()) return false;
MyData myData = (MyData) o;
return v == myData.v;
}
@Override
public int hashCode() {
return Objects.hash(v);
}
public int compareTo(MyData o){
// 1 ? 2 : 1 - 2 == 0 : 같다
// < 0 : 오른쪽이 크다
// > 0 : 왼족이 크다
return v - o.v;
}
}
public class Object의비교 {
public static void main(String[] args) {
// List<Integer> list = new LinkedList<>();
// for(int i =1; i<= 100; i++) list.add(i);
// System.out.println(list);
// int index = list.indexOf(63);
// System.out.println(index);
List<MyData> list = new LinkedList<>();
// for(int i = 1; i<= 100;i++)list.add(new MyData(i));
//
// System.out.println(list);
// int index = list.indexOf(new MyData(63));
// System.out.println(index);
Random r= new Random();
for(int i = 1; i<=100; i++){
list.add(new MyData(i));
}
System.out.println(list);
int index = Collections.binarySearch(list, new MyData(63));
//정렬한다 -> sort 한다.
// int index = list.indexOf(new MyData(63));
System.out.println(index);
System.out.println(list.get(index));
}
}GitHub
