알고리즘
클래스
- 자바에서 클래스는 객체 지향 프로그래밍의 핵심 구성 요소
- 객체는 클래스에 정의된 속성과 동작을 가지며, 클래스에서 생성된다.
- 클래스를 사용하면 코드의 재사용성, 확장성 및 관리 용이성이 향상된다.
정의 방법
class ClassName {
// 필드(변수)
// 메서드(함수)
}ClassName은 클래스의 이름으로, Java의 네이밍 컨벤션에 따라 각 단어의 첫 글자는 대문자로 시작한다.
주요 구성 요소
- 필드(Fields)
- 클래스 내에서 정의된 변수로, 객체의 상태를 나타낸다. 필드는 객체의 속성, 특성을 저장하기 위해 사용한다.
- 메서드(Methods)
- 객체가 수행할 수 있는 동작을 정의한 코드 블록이다. 메서드는 특정 작업을 수행하고, 결과를 반환하거나, 단순히 작업을 수행할 수 있다.
- 생성자(Constructor)
- 클래스 이름과 동일하며, 객체가 생성될 때 자동으로 호출되는 특별한 메서드이다. 생성자는 객체 초기화에 주로 사용된다.
- 명시적으로 생성자를 정의하지 않으면, 자바 컴파일러는 기본 생성자를 제공한다.
ex. 자바 클래스
public class Dog {
// 필드
String breed;
int age;
String color;
// 메서드
// 접근제한자 리턴타입 메소드명 (매개변수들..) {..구현..}
void bark() {
System.out.println("Woof!");
}
void displayInfo() {
System.out.println("Breed: " + breed + ", Age: " + age + ", Color: " + color);
}
}ex. 객체 생성 및 사용
- 클래스를 정의한 후, new 키워드를 사용하여 클래스의 인스턴스(객체)를 생성할 수 있다
public class DogTest {
public static void main(String[] args) {
Dog myDog = new Dog();
myDog.breed = "Labrador";
myDog.age = 5;
myDog.color = "Brown";
myDog.bark();
myDog.displayInfo();
}
}소수
- 입력한 정수까지 모두 체킹을 하며 소수를 찾는 방식
import java.util.Scanner;
public class ListPrimes {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요: ");
int num = sc.nextInt();
int cnt = 0;
for (int i = 2; i <= num; i++){
boolean isPrime = true;
for (int j = 2; j < i ; j++){
cnt++;
if (i % j == 0){
isPrime = false;
break;
}
}
if(isPrime == true){
System.out.println(i);
}
}
System.out.println(cnt);
}
}설명
입력한 정수까지의 모든 수를 2부터 체킹하는 수-1까지의 모든 수로 나누어 소수인지 판별을 한다.
이러한 방식은 시간이 오래걸리는 단점이 있음.
입력한 정수까지 홀수만 체킹하며 소수를 찾는 방식
import java.util.Scanner;
public class ListPrimes2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요: ");
int num = sc.nextInt();
int cnt = 0;
int arrCnt = 0;
int[] primes = new int[500];
primes[arrCnt++] = 2; // 2를 먼저 소수의 배열에 넣어준다.
for (int i = 3; i <= num; i+=2){
boolean isPrime = true;
for (int j = 3; j < i ; j++){
cnt++;
if (i % j == 0){
isPrime = false;
break;
}
}
if(isPrime == true){
System.out.println(i);
}
}
System.out.println(cnt);
}
}설명
2를 먼저 소수의 배열 primes에 넣어준다.
3부터 입력한 정수까지 홀수만 체킹을 하며 그 사이의 수로 모두 나누며 소수인지 판별한다.
위의 코드와 다르게 prime배열에 3을 먼저 넣어주고 5부터 판별해도 된다. (2, 3 모두 소수이기 때문)
다차원 배열
다차원 배열의 초기화
1번째 방법
int[][] scores = new int[3][4];2번째 방법
int[][] scores = {
{90, 80, 77, 60}, // 첫 번째 학생의 점수
{80, 70, 60, 50}, // 두 번째 학생의 점수
{70, 60, 50, 40} // 세 번째 학생의 점수
};클래스
클래스는 기본적으로 도면이라고 생각하면된다.
클래스를 인스턴스화 하면 객체가 되는 것이다.
클래스 → 자동차를 만드는 도면
객체 → 도면을 가지고 만든 나의 자동차
public class Dog {
String breed;
int age;
String color;
public Dog() {
//기본 생성자
}
public Dog(String breed, int age, String color) {
this.breed = breed;
this.age = age;
this.color = color;
}
public Dog(String breed, String color) {
this.breed = breed;
this.color = color;
}
//메소드
//접근제한자 리턴타입 메소드명 (매개변수들...)
static void bark(){
System.out.println("Woof!");
}
void displayInfo(){
System.out.println("Breed: " + breed + " Age: " + age + " Color: " + color);
}
//getter, settter
public String getBreed() {
return breed;
}
public int getAge() {
return age;
}
public String getColor() {
return color;
}
public void setBreed(String breed) {
this.breed = breed;
}
public void setAge(int age) {
this.age = age;
}
public void setColor(String color) {
this.color = color;
}
}설명
강아지 클래스이다.
즉, 강아지를 만들 수 있는 도면을 만든 것이라고 생각하면 된다.
기본적으로 생성자를 만들지 않으면 자바에서는 기본 생성자를 제공해준다.
위의 코드에서는 “기본생성자”, “품종과 나이, 색깔이 모두 들어간 생성자”, “품종과 색깔만 들아간 생성자” 3 종류가 있다.
위의 메소드를 보면 bark()와 displayInfo()가 있다.
bark()는 static이 붙은 클래스 메소드이다.
displayInfo()는 static이 붙지 않은 인스턴스 메소드이다.
static이 붙은 클래스 메소드는 객체를 생성하지 않아도 사용이 가능하다.
하지만 static이 붙지 않은 인스턴스 메소드는 객체를 생성해야만 사용이 가능하다.
ex. 객체 생성 코드
public class DogTest {
public static void main(String[] args) {
Dog.bark();
Dog myDog = new Dog(); //Dog 타입의 myDog를 인스턴스화
myDog.setAge(3);
myDog.setBreed("말티즈");
myDog.setColor("흰색");
myDog.age=6;
myDog.displayInfo();
Dog myDog2 = new Dog("포메", 4, "검정색");
myDog2.displayInfo();
Dog myDog3 = new Dog("포메", "흰색");
myDog3.displayInfo();
}
}설명
위의 코드는 Dog클래스의 객체를 생성해서 사용하는 DogTest클래스이다.
bark() 메소드를 보면 객체를 생성하지 않고 Dog클래스에 바로 접근해서 사용이 가능하다.
위에서 언급했듯이 static 키워드가 붙은 클래스 메소드이기 때문이다.
하지만 displayInfo() 메소드는 객세를 생성한 후 객체에 접근해서 사용이 가능하다.
static이 붙지 않은 인스턴스 메소드이기 때문이다.
선형 검색(Linear Search)
선형검색
원하는 값을 찾기 위해서 배열의 첫번째 요소부터 마지막 요소까지 차례대로 모두 확인하는 방법
import java.util.Scanner;
public class SearchExam {
static int sequentialSearch(int[] arr, int key){
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key)
return i; // 키와 일치하는 요소의 인덱스 반환
}
return -1; // 검색 실패 시 -1 반환
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("찾고자하는 정수를 입력하세요: ");
int key = sc.nextInt();
int[] arr = {1,3,5,33,56,2,44};
int index = sequentialSearch(arr, key);
if (index != -1){
System.out.println("당신이 찾는 데이터는 " +index+"번째 인덱스에 있습니다.");
}else {
System.out.println("당신이 찾는 데이터가 존재하지 않습니다.");
}
}
}설명
찾고자 하는 값을 입력하면 sequentialSearch() 메소드에서 배열의 첫번째 요소부터 마지막 요소까지 순차적으로 확인을 한다. 도중에 원하는 값을 찾으면 값이 위치하는 요소의 인덱스를 반환한다.
선형 검색(보초법)
-
선형 검색 알고리즘을 개선한 방법
-
보초법(Sentinel Method)은 선형 검색에서 조건 검사의 횟수를 줄이기 위해 배열의 마지막에 검색하고자 하는 값을 “보초”로 추가하는 기법이다.
-
보초는 검색하고자 하는 키 값과 동일한 값을 배열의 맨 끝에 추가함으로써, 배열을 순회하는 동안 매번 배열의 끝에 도달했는지 확인하는 조건 검사를 생략할 수 있게 해준다.
-
선형 검색(보초법)의 작동 원리
- 검색하고자 하는 키 값을 배열의 마지막에 추가한다(보초).
- 배열의 첫 번째 요소부터 시작하여 키 값과 일치하는 요소를 찾는다.
- 배열 내에 키 값과 일치하는 요소가 있으면 그 위치를 반환한다.
- 보초 덕분에, 배열의 끝에 도달했는지 확인할 필요 없이 보초 값에 도달할 때까지 반복할 수 있다.
- 배열 내에 키 값과 일치하는 원래의 요소가 없는 경우, 반복은 보초에 의해 종료된다. 이 때, 보초의 위치(즉, 배열의 맨 끝)가 반환되므로, 이를 통해 검색 실패를 판단할 수 있다.
-
장점
- 배열의 끝을 체크하는 조건 검사가 불필요하여, 약간의 성능 향상을 기대할 수 있다.
- 코드가 더 간결해지고 이해하기 쉬워진다.
-
단점
- 배열 수정
- 원래의 배열을 수정해 보초 값을 추가해야 한다.
→ 배열의 크기를 변경하거나 추가적인 메모리 공간을 사용해야 할 수 있다.
- 원래의 배열을 수정해 보초 값을 추가해야 한다.
- 검색 대상 제한
- 검색하려는 키 값이 배열 내에 존재하지 않을 때 효율적이다.
- 그러나 배열 내에 키 값과 일치하는 요소가 여러 개 있는 경우, 보초법을 사용해도 첫 번쨰 일치하는 요소를 찾은 후 검색을 멈추므로, 모든 일치하는 요소를 찾는 데에는 추가적인 로직이 필요하다.
- 특정 상황에서의 성능 이점 부족
- 보초 값의 선택
- 보초 값을 배열에 추가하기 위해서는 보초 값이 원래 배열 내의 어떤 값과도 중복되지 않아야 한다.
- 찾고자 하는 값(key)를 마지막 배열 요소에 추가
-> 배열의 크기를 벗어났는지 체크하지 않다도 됨 - 즉, for문을 사용하지 않고 while문을 사용하여 구현 가능
import java.util.Scanner;
public class LinearSearchSentinel {
// 배열 arr에서 key와 일치하는 요소를 보초법을 사용하여 선형 검색
static int linearSearchSentinel(int[] arr, int size, int key) {
int i = 0;
arr[size] = key; // 보초 추가
while (true) {
if (arr[i] == key)
break;
i++;
}
return i == size ? -1 : i;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요소 개수: ");
int num = stdIn.nextInt();
int[] array = new int[num + 1]; // 요소 개수가 num + 1인 배열로, 마지막은 보초용
for (int i = 0; i < num; i++) {
System.out.print("array[" + i + "]: ");
array[i] = stdIn.nextInt();
}
System.out.print("찾을 값: "); // 찾고자 하는 값 입력
int key = stdIn.nextInt();
int index =linearSearchSentinel(array, num, key); // 배열 array에서 key를 검색
if (index == -1)
System.out.println("찾는 값의 요소가 없습니다.");
else
System.out.println("찾는 값은 array[" + index + "]에 있습니다.");
}
}
이진 검색(Binary Search)
- 이진 검색은 “분할 정복(Divide and Conquer)” 전략을 사용하여, 데이터가 정렬되어 있는 배열에서 중간 지점의 값을 키와 비교하여 검색 범위를 반으로 줄이면서 검색하는 방법이다.
- 이진 검색은 순차 검색에 비해 훨씬 빠른 검색 속도를 제공하지만, 검색 전에 배열이 정렬되어 있어야 한다.
- 작동원리
1. 배열의 중간 요소을 기준으로 원하는 키값이랑 같은지 확인한다.
2. 중간 요소보다 키값이 크면 중간 요소와 마지막 요소의 중간 요소를 찾는다.
3. 중간 요소보다 키값이 작으면 처음 요소와 중간 요소의 중간 요소를 찾는다.
4. 이를 start 변수와 end 변수를 이용하여 start 변수가 end보다 커지면 탐색을 종료하고 그 전에 원하는 키값을 찾으면 키값이 들어있는 배열 요소의 인덱스를 반환한다.
5. 이는 순차 탐색보다 빠르며 시간복잡도는logN이다.
6. 이진 탐색은 배열이 무조건 정렬이 되어있어야된다.
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearchExam {
public static int binarySearch(int[] arr, int key){
int start = 0;
int end = arr.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if (key == arr[mid]){
return mid;
} else if (key > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("찾고자하는 정수를 입력하세요: ");
int key = sc.nextInt();
int[] arr = {1,3,5,33,56,2,44};
Arrays.sort(arr); //Arrays의 sort메소드를 사용하여 정렬
System.out.println(Arrays.toString(arr));
int index =binarySearch(arr, key);
if (index != -1){
System.out.println("당신이 찾는 데이터는 " +index+"번째 인덱스에 있습니다.");
}else {
System.out.println("당신이 찾는 데이터가 존재하지 않습니다.");
}
}
}- 장점
- 효율성
O(log n)의 시간 복잡도를 가지며, 큰 데이터 집합에서도 빠른 검색 속도를 보장한다.
- 정렬된 데이터에 최적화
- 효율성
- 단점
- 데이터 정렬 필요
- 동적 배열에서 비효율적
- 배열에 자주 삽입이나 삭제가 발생하는 경우, 배열을 정렬된 상태로 유지하는 데 추가 비용이 발생할 수 있다.
안녕하세요, 박경서입니다.