1. 기본 알고리즘/자료구조 + 검색(탐색) 알고리즘

반복

• 불필요한 조건문 실행 횟수 줄이기

-  실습 1-10(식 마지막에 등호를 붙이기 위해 n번의 조건문 실행)

-  실습 1-11(+, - 번갈아 출력 시 홀수, 짝수 분별위해 n번의 조건문 실행)

 

위와 같은 실습의 경우, 반복할 때마다 조건문을 실행해야 한다는 부담이 있다.

등호를 마지막에 붙이고, +-를 붙여 출력하는 식으로 수정하면 조건문 실행횟수나 연산 횟수를 줄일 수 있다.

• 이중 반복문의 경우 외부 반복문이 행, 내부 반복문이 열

내부 반복문의 초기값 및 조건문을 i로 두어 조합 등을 처리할 수 있다.

---

배열/클래스

• 배열 길이 = arr.length / 배열 기본값 = 0
• 기수 변환
• 소수 판별 -> 정수 n의 소수여부 판별
  
  • 루트(n)(n 제곱근)이하의 어떤 수(소수)로도 나누어떨어지지 않는다.
  • n-1까지의 어떤 소수로도 나누어 떨어지지 않는다.
  • * 당연히 아닌 값은 제외해 반복문 실행횟수 줄이기 -> 소수판별 시 짝수 제외
• 클래스 선언 및 생성 -> 멤버(필드, 메서드, 중첩 클래스/인터페이스), 초기화, 생성자

생성자: 새로 생성하는 인스턴스 초기화 / final로 선언한 필드는 값을 한 번만 대입할 수 있다.

extends: 클래스 상속 / implements: 인터페이스 구현

class Person {
   int height;
   int age;
   String gender;
}

Person p; p = new Person();
Person p = new Person();

---

검색 알고리즘

1. 검색 알고리즘: 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘

• 배열 검색, 선형 리스트 검색, 이진검색트리 검색

2. 선형 검색: 무작위 데이터 집합에서 검색하는 방법 -> 비교횟수 평균 n/2

- 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소 검색

- 요소가 정렬되지 않은 배열에서 탐색하는 유일한 방법 

static int seqSearch(int x) {
    int[] arr = {1,4,35,745,834,23,1,6,1,32}; -> O(1)
    for(int i = 0; i<arr.length; i++) { -> O(n)
        if(arr[i] == x) -> O(n)
            return i; -> O(1) 
    }
    return -1; -> O(1)
}
// 시간 복잡도 = O(max(1, n, n, 1, 1))

• 종료조건: 검색할 값을 찾지 못하고 배열의 끝을 지나간 경우 / 검색값과 같은 요소를 발견한 경우
• 보초법: 종료조건 검색 비용을 반으로 줄이는 방법 -> 배열 마지막 값에 검색값을 넣어 1번 조건 없애기

3. 이진 검색: 정렬된 데이터 집합에서 빠르게 검색하는 방법 -> 비교횟수 평균 log n

- 검색을 한 단계씩 진행할 때마다 검색 범위가 반으로 줄어듦

static int binSearch(int x) {
    int[] arr = {1,2,3,4,5,6,7,8,9}; 
    int start = 0;					 
    int end = arr.length;			

    while (start < end){			
        int mid = (start + end) / 2; 
        if (arr[mid] > x) 			
            end = mid - 1;
        else if (arr[mid] < x) 		
            start = mid + 1;		
        else  // arr[mid] == x		
            return mid;				
    }
    return -1;						
}
    
// 시간 복잡도 = O(max(1, 1, 1, log n, log n, log n, log n, log n, 1, 1, 1)

• 종료조건: arr[mid]와 key가 일치 / 검색범위가 더 이상 없음
• 복잡도: 시간 복잡도 - 실행에 필요한 시간 평가 / 공간 복잡도 - 기억 영역과 파일 공간이 얼마나 필요한지 평가

코드마다 시간 복잡도 계산해 차수가 가장 높은 복잡도 선택

• 클래스 메서드(static, 정적 메서드), 인스턴스 메서드(비정적 메서드)

4. 해시 검색: 데이터 검색뿐만 아니라 추가나 삭제 등을 효율적으로 수행할 수 있는 방법

 

* 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러개이면 용도나 목적, 실행속도, 자료구조 등을 고려해야 함

예를 들어 빠르게 검색하는게 목적이면 이진 탐색을 사용하면 되지만, 값의 삭제와 추가가 잦다면 해시를 사용하는 것이 좋다.