1일차 정리(순서도, 클래스, 선형 검색, 이진검색)

1. 순서도의 기호

데이터(data)의 입력과 출력을 나타낸다.

처리(process)는 여러 종류의 처리 기능을 수행. 즉, 정보의 값, 자료형, 위치를 바꾸도록 정의한 연산이나 연산집합의 실행 또는 연속적인 몇 가지 흐름 가운데 하나의 방향을 결정하는 연산집합이나 연산군의 실행을 나타낸다.

미리 정의한 처리(predefined process)는 서브 루틴 및 모듈 등 다른 곳에서 이미 정의한 하나 이상의 연산 또는 명령어들로 이루어진 처리를 나타낸다.

판단(decision)은 하나의 입구와 하나 이상을 선택할 수 있는 출구가 있고, 기호에서 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능(스위치형 기능)을 나타냅니다. 주로 예상되는 평가 결과의 경로를 선 가까이에 쓴다.

 

루프범위(loop limit)는 오른쪽 그림과 같이 두 부분으로 구성되어 루프의 시작과 종료를 나타낸다.

선(line)은 제어의 흐름을 나타낸다. 주로 흐름의 방향을 분명히 나타내고자 할 때 화살표를 붙이는데, 순서도에 작성할 때도 보기 쉽게 화살표를 붙이기도 한다.

단말(teminator)은 외부 환경으로 나가거나 외부 환경에서 들어오는것을 나타낸다.

2. 클래스

- 임의의 데이터형을 자유로이 조합하여 만들 수 있는 자료구조

- 클래스 본체와 멤버)

 가. 클래스 본체에서는 다음과 같은 내용을 선언할 수 있다.

  a) 멤버(필드/메서드/중첩(nested) 클래스/중첩(nested) 인터페이스)

  b) 클래스 초기화 / 인스턴스 초기화

  c) 생성자

 나. 필드/메서드/생성자를 선언할 때 public/protected/private을 지정할 수 있다.

 다. 메서드/생성자는 다중으로 정의(오버로드)할 수 있다.

 라. final로 선언한 필드는 한 번만 값을 대입할 수 있다.

 마. 생성자는 새로 생성한 인스턴스의 초기화를 위해 사용된다.

- 공개 클래스 : 클래스 접근 제한자 public을 붙여 선언한 클래스로, 다른 패키지에서 사용할 수 있는 공개 클래스(public class)입니다.

- final 클래스 : 클래스 접근 제한자 final을 붙여 선언한 클래스로, 서브 클래스를 가질 수 없습니다.(새로운 클래스를 상속할 수 없습니다). final class가 된다.

- 파생 클래스 : 클래스 A를 직접 상위 클래스(direct superclass)로 하려면 선언할 때 extends A를 추가해야 한다. 이때 선언한 클래스는 클래스 A의 직접 서브 클래스(direct subclass0가 된다.

ex) java.lang 패키지에 있는 Object <- A class <- C class

- 인터페이스 구현 : 인터페이스 X를 구현하려면 선언에 implements X를 추가해야 한다.

- 추상 클래스 : 클래스 접근 제한자 abstract를 붙여 클래스를 선언하면 추상 메서드를 가질 수 있는 추상 클래스(abstract class)가 된다. 추상 클래스형은 불완전한 클래스이므로 인스턴스를 만들 수 없다.

- 중첩 클래스 : 클래스 또는 인터페이스 안에 선언한 클래스는 중첩 클래스(nested class0가 된다.

 가. 멤버 클래스(member class) : 그 선언이 다른 클래스 또는 인터페이스 선언에 둘러싸인 클래스

 나. 내부 클래스(inner class) : 명시적으로도 암묵적으로도 정적(static)으로 선언되지 않는 중첩 클래스이다. 정적 초기화나 멤버 인터페이스 선언을 할수 없다. 그리고 컴파일을 할 때 상수 필드가 아닌 한 정적 멤버를 선언할 수 없다.

 다. 지역 클래스(local class)는 이름이 주어진 중첩 클래스인 내부 클래스이다. 어떤 클래스의 멤버도 될 수 없다.

3. 선형 검색

- 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear serch) 또는 순차 검색(sequential search)이라는 알고리즘입니다.

- 다음 조건중 하나라도 성립하면 검색을 종료합니다.

 가. 검색할 값을 발견하지 모샇고 배열의 끝을 지나간 경우

 나. 검색할 값과 같은 요소를 발견한 경우

- 보초법 : 선형 검색은 반복할 때 마다 종료 조건 2가지 모두 판단합니다. 종료 조건을 검사하는 비용은 결코 무시할 수 없으므로 이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel method)입니다.

방법은 간단합니다.

검색하고자 하는 데이터를 원래 데이터 끝에 추가합니다. 이 데이터를 보초 데이터라고 부릅니다.

그리고 선형 검색을 하면 검색조건중 조건 나번이 만나면 결국 원래 데이터에 원하는 데이터가 없다는것을 알수 있으므로 2번 검색할 필요가 없습니다. 즉, 조건 가번이 필요없어지게 되며 비용이 반(50%)으로 줄어든 결과를 볼 수 있습니다.

3. 이진검색

- 이 알고리즘을 적용하는 전제조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것입니다.

- 검색범위 맨앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정

- 1. key값이 pc보다 큰경우 범위를 pl+1 부터 ~ pr까지 다시 검색범위를 줄입니다. 이런식으로 원하는 값을 찾습니다.

- 이진 검색 알고리즘의 종료 조건

 가. 검색도중 원하는 값이 나온경우

 나. 검색 범위가 더 이상 없는 경우

- 복잡도 : 프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.

복잡도는 아래의 두 가지 요소를 가지고 있다.

 가. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한것.

 나. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한것.

---

- 선형 검색의 시간 복잡도

2,5,7번줄은 한번만 실행하기 때문에 복잡도는 O(1)로 표시

배열의 맨 끝에 도달했는지를 판단하는 3번줄과 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지 판단하는 4번줄은 평균 실행횟수는 n/2 이다. 이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기

그런데 n이 점점 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다.

이와 달리 O(1)에 필요한 계산 시간은 변하지 않습니다.

- max(a, b)는 a와 b가운데 큰 쪽을 나타내는 메서드입니다.

순서(코드 위치)	실행횟수	복잡도
2	1	O(1)
3	n/2	O(n)
4	n/2	O(n)
5	1	O(1)
6	n/2	O(n)
8	1	O(1)

$O(f(n))+O(g(n))=O(max(f(n),g(n))$

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시합니다.

$O(1)+O(n)+O(n)+O(1)+O(n)+O(1)=O(max(1,n,n,1,n,1))=O(n)$

그러므로 선형 검색 알고리즘의 복잡도를 구하면 O(n)이 됩니다.

---

- 이진 검색의 시간 복잡도

순서(코드 위치)	실행횟수	복잡도
2	1	O(1)
3	1	O(1)
6	log n	O(log n)
7	log n	O(log n)
8	1	O(1)
9	log n	O(log n)
10	log n	O(log n)
12	log n	O(log n)
13	log n	O(log n)
15	1	O(1)

$O(1)+O(1)+O(logN)+...+O(1)=O(logN)$

- $O(log _{2} N)$ 인 이유)

첫 시행후 반으로 갈라져서 n/2

두번째 실행후 1/2 * n/2

....

K번 시행후 $\frac{1}{2} ^{K} N$

남은 자료가 1개 남을때까지 진행되니 $ \frac{1}{2} ^{K} N \approx 1 $

이것을 정리하면 

$2 ^{K} *\frac{1}{2} ^{K} N \approx 2 ^{K} *1$

$N \approx 2 ^{K}$

$log _{2} 2 ^{K} \approx log _{2} N$

따라서 $K \approx log _{2} N$ 시간 복잡도 Big O 표기법으로 $O(log _{2} N)$ 으로 나타납니다.