**데이터 정렬 1. 정렬의 구분 1)오름차순(Ascending - 작은것에서 큰것 순으로 배치, 기본)과 내림차순(Descending - 큰것에서 작은것순으로 배치)
2) 알고리즘에 의한 분류 -selection sort(선택정렬) : 교재에서 많이 설명, 정렬이 무엇인지 설명하고 제어문 학습하는 용도로 주로 이용, 실무에서는 거의 사용하지 않음 (성능이 좋지않음) - bubble sort - insertion sort - quick sort-재귀함수
- shell sort - heap sort - radix sort 등
=> 면접이나 코딩 테스트에서는 quick sort를 많이 물어봄
2. Selection sort(선택정렬)
20 30 40 50 10:정열되지 않은 상태
=>첫번째 위치부터 마지막 바로 앞 위치까지 자신의 뒤에 있는 모든 데이터와 비교해서 더 작은 데이터를 자리 바꿈을 하는 방식으로 데이터를 정렬
1pass(0) 10 30 40 50 20 : 1,2,3,4
2pass(1) 10 20 40 50 30 : 2,3,4
3pass(2) 10 20 30 50 40 : 3,4
4pass(3) 10 20 30 40 50 : 4
끝나는 자리가 같다 시작 자리만 변한다.
int[] ar = [20 30 40 50 10]
//선택 정렬
for (int i = 0; i < 4; i++){
//비교 위치 반복문
for (j =i+1 ; j < 5 ; j++){
if(ar[i] > ar[j]){
//swap =>python빼고 대부분 언어는 이렇게 한다.
int temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
===>
int len = ar.length;
for (int i = 0; i < len-1i++){
//비교 위치 반복문
for (j =i+1 ; j < len ; j++){
if(ar[i] > ar[j]){
//swap =>python빼고 대부분 언어는 이렇게 한다.
int temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
python의 swap : (a,b) = (b,a)
오름 차순 내림차순 는 부등호 방향 바꾼다. < >
일반화 시킬 수 있어야 한다.
4,5 등 안고쳐도 되게끔 바꿔야 한다. MVC 데이터 LENGTH로 해야 한다.
int [] ar = {20,30,40,50,10};
//선택 정렬은 첫번째 부터 마지막 바로 앞 데이터 까지
//자신의 두에 있는 모든 우치의 데이터와 비교해서 정렬
//오륾차순이면 뒤의 데이터가 작을 때 swap
//내림찬순이면 뒤의 데이터가 클 때 swap
//첫번째 부터 마지막 바로 앞 자리까지
//상수를 이용하면 안좋은 점이 데이터가 늘어나면 마지막에는 sort가 안된다.
//상수를 이용하면 데이터가 줄거나 늘어나거나 하면 문제가 생긴다.
for (inti = 0; i < 4; i++) {
//기준의 뒤에 있는 모든 데이터와 비교해서
for (intj = i+1; j < 5; j++) {
//기준점의 데이터가 크면 swap
if(ar[i] > ar[j]) {
inttemp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
//이것으로 변경
intlen = ar.length;
for (inti = 0; i < len-1; i++) {
//기준의 뒤에 있는 모든 데이터와 비교해서
for (intj = i+1; j < len; j++) {
//기준점의 데이터가 크면 swap
if(ar[i] > ar[j]) {
inttemp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
//데이터 출력
for(inttemp : ar) {
System.out.println(temp + "\t");
}
lotto개선
//키보드로 부터 데이터를 입력받기 위한 객체를 생성
Scanner sc = new Scanner(System.in);
//1-45까지의 정수 6개를 저장할 자료구조를 생성
int[] lotto = newint[6];
//6번 반복
for (inti = 0; i < 6; i++) {
//정수를 입력받아서 su에 저장
System.out.print(i + "번째 숫자:");
intsu = sc.nextInt();
//1부터 45까지의 숫자만 저장하고 그 이외의 경우는 다시 입력하도록 하기
if (su< 1 || su > 45) {
System.out.println("1-45사이만 입력하세요");
//이번 입력은 무효화
//뒤로 왔다가 다시 한칸 가니깐 원래 자리로 된다.
i = i -1;
//아래로 내려가지 않고 다음 반복으로 넘어가기
continue;
}
//데이터 중복 검사
if(i > 0) {
booleanflag = false;
//현재것 이전 까지 비교한다.
//첫번째 데이터 부터 현재 입력할 데이터 앞까지 비교
for(intj = 0; j < i; j++) {
//현재 입력받은 데이터와 같은지 비교
if(lotto[j] == su) {
flag = true;
System.out.println("중복된 데이터입니다.");
//더이상 비교할 필요가 없음
break;
}
}
//이전 데이터와 동일한 데이터를 만나면 다시 입력받도록 작성
if(flag == true) {
i = i-1;
continue;
}
}
//입력받은 데이터를 배열에 저장
lotto[i] = su;
}
intlen = lotto.length;
for (inti = 0; i < len-1; i++) {
//기준의 뒤에 있는 모든 데이터와 비교해서
for (intj = i+1; j < len; j++) {
//기준점의 데이터가 크면 swap
if(lotto[i] > lotto[j]) {
inttemp = lotto[i];
lotto[i] = lotto[j];
lotto[j] = temp;
}
}
}
//입력받은 데이터 출력
for(inttemp: lotto) {
System.out.println(temp + "\t");
}
sc.close();
3.Bubble Sort
=>최대 n(데이터 개수)- 1회전 동안 맨 앞에서 부터 자신의 바로 뒤에 있는 데이터와만 비교해소 정렬하는 방식
20 30 40 50 10
20 30 , 30 40, 40 50, 50 10 이렇게 비교한다.
=>항상 1회전이 끝나면 가장 큰 데이터가 맨 뒤로 이동
=>1회전 동안 데이터의 이동이 없으면 정렬이 된 것ㅇ이므로 중단해도 됩니다.
a:90
b:100
c:70
selection sort : a>b a>c b와 c의 관계를 알 수없다.
bubble sort a>b, b>c 연속해서 비교 하기 때문에
sort quick sort 재귀를 사용해서 메모리 많이 사용한다.
for(int i = 0; i < len-1; i++){
//1회전
boolean flag = false; //이 함수 들어갔는지 안 들어갔는지 확인하는 방법
for(int j = 0; j < len- i-1; j++){
//위치 이동
if(ar[j] > ar[j+1]){
int temp = ar[j];
ar[j] = ar[j+1];
ar[j+1] = temp;
flag = true;
}
}
if(flag == false){
break;//위치 변경 있는 지 없는지
}
}
20 30 40 50 10
20 30
30 40
40 50
50 10 -> 20 30 40 10 50
20 30
30 40
40 10 -> 20 30 10 40 50
int[] ar = { 20, 30, 40, 50, 10 };
// 버블 정렬은 최대 n(데이터 개수)-1 회전 동안
// 자신의 바로 뒤에 있는 데이터와 비교해서 정렬
// 오름차순이면 뒤의 데이터가 작을 때 swap
// 내림차순이면 뒤의 데이터가 클 때 swap
// 버블 정렬은 가장 큰 데이터가 맨 뒤로 이동하므로 하나의 회전이 끝나면
// 맨 마지막 데이터와는 비교할 필요가 없습니다.
// 1회전 동안 데이터의 이동이 없으면 정렬 종룔
intlen = ar.length;
// 최대 n-1회전
for (inti = 0; i < len - 1; i++) {
// 1회전 동안의 데이터의 이동 여부를 판별하기 위한 변수
booleanflag = false; // 이 함수 들어갔는지 안 들어갔는지 확인하는 방법
// 자신의 인접한 데이터와 비교하기 위한 제어문
for (intj = 0; j < len - i - 1; j++) {
// 위치 이동
// 뒤의 데이터가 더 작으면 swap
if (ar[j] > ar[j + 1]) {
inttemp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
// 데이터 이동 여부 표시
flag = true;
}
}
// 데이터의 이동이 없으면 정렬 종료
if (flag == false) {
break;// 위치 변경 있는 지 없는지
}
}
//데이터 출력
for(inttemp : ar) {
System.out.println(temp + "\t");
}
**검색(search)
1.순차검색
=>데이터가 정렬되지 않았을 때 앞에서부터 순서대로 검색
=>첫번째 데이터와 마지막 데이터의 검색 시간이 차이가 많이 나고 데이터가 없는 경우 전체 데이터를 확인해야만 없다는 사실을 알 수 있습니다.
2.제어검색
=>데어터가 정렬된 경우 사용하는 검색 방법
1) 이분 검색(binary search):데이터의 중앙값고과 비교해서 작으면 왼쪽 크면 오른쪽에 가서 다시 중앙값과 비교하는 방식
1 2 3 4 5
가운데 간다. 3을 중앙값 기준으로 (4 5)
15개 데이터가 있으면 15번 가봐야 하는데 하나하나씩 확인해야 하는데 이분 검색을 사요앟면
27 있는지 확인
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
27이 8보다 크다. 그래서 오른쪽으로 간다.
9 10 11 12 13 14 15 -> 27
12 13 14 15 -> 27
14 15 ->27
4번으로 검색한다.
컴퓨터 프로그램에서는 많이 사용하는데
2)피보나치 검색: 피보나치 수열의 값을 이용해서 검색
1,1,2,3,5,8,13,,,(첫번째 와 두번째는 1 세번째 부터는 앞쪽 2개 항의 합)
spin으로 할때 간격으로 크진다.
3) 보간 검색
=>검색위치를 계산해서 검색=> 실생활에서 많이 사용한다.
프로그램에서는 피보나치나 이분 검색 많이 사용한다.
(검색값- 최소값)/(최대값 - 최소값) 을 계산한 후 데이터 개수와 곱해서 찾는 방식
데이터의 분포가 고르다면 제어검색 중에서 성는이 우수함
데어터의 분포를 컴퓨터가 잘 모르기 떄문에 binary search로 한다.
4)이진 트리 검색
=>데이터를 삽일할 때 정렬 하는 것 처럼 작으면 왼쪽 크면 오르쪽에 배치해서 검색
=>이진 트리는 만들다 보면 정확하게 반으로 분할 되지는 않습니다.
3.블록 검색=>서점 예: 알라딩
=>블록 단위는 정렬되어 있지만 블록 안은 정렬이 안된 상태에서 검색
4.해싱
=>데이터를 배치할 때 함수를 이용해서 배치하는 방식
=>모든 데이터의 검색 속도가 일정하고 가장 빠른 검색 방법
=>해싱 함수의 선택은 운영체제가 합니다.
dict등 은 순서를 모른다.
**객체 지향 프로그래밍(object oriented programming -OOP) =>3대 특징
1.객체지향 특징
1)Encapsulation(캡슐화): 관련있는 속성과 메소들 묶는 것
클래스를 만드는 방법
2)Inheritance(상속성):상위클래스의 모든 것을 하위 클래스가 물려 받는 것
3)Polymorphism(다향성):동일한 메시지에 대하여 다르게 반응하는 성질
=>동일한 코드가 호출하는 객체에 따라서 다른 메소드를 호출 하는 것
2.객체 지향의 장점
=>코드의 재사용성이 뛰어남
3.객체지향의 단점
=>함수형 프로그래밍 방식에 비해서 무겁다.
hbase-> java 안정적이다.
mongodb->c++
hbase가 mongodb보다 무겁다.
객체 지향은 감싸서 큰 것 만들때는 좋다.
함수형 프로그램이 가볍다.
빅데이터 처리는
빅데이터 분석 자바에서 함수형 프로그램하는 것이 생겼다. scalar,closure, kotalin등
r , python
java는 근본적인 객체지향
python는 선택가능하다.
c가 c++보다 쉽다.
4.클래스와 인스턴스(객체 - 예전에는 object)
=>최근에는 클래스도 오브젝트로 간주합니다.
=>클래스는 인스턴스들의 공통된 특징을 소유한 객체
=>클래스를 기반으로 해서 생성된 객체들을 인스턴스 라고 하기도 합니다.
클래스는 모델하우스 ->집의 최소가 된다.
객체는 집
모델하우스 보다 적으면 문제가 있다.
클래스는 설계도 같은 개념이여서 틀을 만들고 instance는 집이 된다.
설계도를 만들고 설계도를 참조하면 되니깐
객체를 component based
=>클래스는 정적(한 번 만들면 수정이 안됨)이고 인스턴스는 동적(만들고 수정하고 삭제 할 수 있습니다.)
=>클래스는 만들고 처음 사용할 때 메모리에 로드가 되서 프로그램이 종료될 때 까지 절대로 소멸되지 않습니다.
=>인스턴스는 만들어서 사용하다가 필요하면 언제든지 제거할 수 있습니다.
5.자바에서 클래스를 생성하는 방법
[접근 지정자] + [클래스 종류]+class+ 클래스 이름 +[extends 상위클래스이름] +[implements 인터페이스이름]{
클래스의 구성 요소 나열
}
6.클래스를 이용해서 인스턴스를 생성하는 기본 방법
new 생성자이름(매개변수 나열)
=>new는 생성자를 기반으로 메모리 할당(allocation)을 하고 초기화(initialize)를 한 후 그 참조를 리턴합니다.
=>자바는 생성자 이름이 클래스 이름이어야 합니다.
7.클래스의 구성 요소
=>속성(attribute-변수)
=>메소드(method) :클래스 안에 만들어져서 클래스 이름이나 인스턴스 이름으로 호출한느 함수를 메소드라고 합니다.
=>생성자(constructor)
8.클래스나 인스턴스를 가지고 자신의 멤버 접근
클래스 또는 인스턴스 , 속성이름 또는 메소드 이름(매개변수 나열) 의 형태로 접근 합니다.
**클래스 생성
1.클래스의 접근 지정자
=>생략(default, package - 디렉토리) : 현재 패키지에서는 마음대로 사용할 수 있지만 다른 패키지에서는 사용을 못함
=>public : 어디에서든지 이 클래스를 사용할 수 있습니다.
=>private :다른 클래스에서 이 클래스를 사용할 수 없도록 할 때 사용, 내부 클래스에만 적용
=>protected : 상속받은 클래스에서는 사용이 가능. 내부 클래스에만 적용 가능
불필요한 것 사용하지 말아라 private
self.__ =>private
2.자바에서는 클래스 별로 별도의 파일에 작성하는 것을 권장(python도 이부분은 같다.)
3.클래스를 생성하고 인스턴스 만들기
1) 클래스 만들기
=>src디렉토리 위에 마우스 포인터 올리고 마우스 오른쪽을 누른 후 [New] - [Class]를 선택하고 옵션을 작성
=>클래스 이름의 첫글자는 대문자로 시작하도록 권장
//main 메소드가 없는 클래스 - 실행할 수 없는 보조적인 역할을 수행하는 클래스
publicclass SampleClass {
}
2)실행 클래스를 만들고 위에서 만든 SampleClass의 인스턴스 만들기
publicstaticvoid main(String[] args) {
//SampleClass의 인스턴스 만들기
//new SampleClass();가 인스턴스를 만드는데
//위의 구문은 수행을 하고 인스턴스의 참조를 리턴합니다.
//이 인스턴스를 재사용할려면 인스턴스의 참조를 동일한 자료형의 변수에 대입을 해야 합니다.
SampleClassobj = new SampleClass();//모든 언어가 같다.
}
**속성 또는 변수
1.변수의 종류
=>동일한 영역에서 동일한 이름으로 변수를 2번 생성할 수 없습니다.
1)Local Variable(지역 변수)
=>메소드 안에서 만들어져서 메소드 안에서만 사용 가능한 변수
=>메소드 안에 존재하는 다른 블록 안에서 만들어지면 그 블록 안에서만 사용이 가능합니다.
=>동일한 영역에서 동일한 이름으로 변수를 2번 생성할 수 없습니다.
=>접근 지정자를 사용하지 않습니다.
=>생성
자료형 변수이름;
자료형 변수이름 = 값;
=>처음에 값을 대입하지 않으면 변수는 생성되지 않습니다.
지역변수는 처음 값을 대입할 때 생성됩니다.
2) Menber Variabl(멤버 변수)
=>클래스 내부에서 메소드 바깥에 선언된 변수로 static.이라는 키워드가 없이 만들어진 변수
=>클래스로부터 만들어지는 각 인스턴스가 자신의 특성을 표현하기 위해서 별도로 소유
=>생성할 때는 접근지정자와 함께 생성
=>변수를 만들 때 값을 대입하지 않아도 기본값으로 초기화가 됩니다.
=>false, 0, 0.0, null등으로 초기화
접근지정자 자료형 변수명으로 선언
3)static Variable(클래스 변수)
=>클래스 내부에서 메소드 바깥에 선언된 변수로 static.이라는 키워드와 함께 만들어진 변수
=>동일한 클래스로부터 생성된 모든 인스턴스가 공유하기 위한 변수
=>이 변수는 1개만 생성되고 소멸되지 않습니다.
=>생성할 때는 접근지정자와 함께 생성
=>변수를 만들 때 값을 대입하지 않아도 기본값으로 초기화가 됩니다.
=>false, 0, 0.0, null등으로 초기화
static 접근지정자 자료형 변수명으로 선언
2.final
=>변수 앞에 붙이면 변수의 값을 변경하지 못하도록 read only를 만들어주는 키워드
3.멤버 메소드나 멤버 변수의 접근 지정자
1)private :클래스 내부의 메소드에서만 사용할 수 있도록 해주는 지정자 ->내안에서만
2)default(package- 생략):동일한 패키지 내에서는 public이고 다른 패키지에서는 private
3)protected: default 에 상속받은 클래스에서도 사용할 수 있도록 해주는 지정자
4)public클래스 냅의 메소드에서 사용 가능하고 클래스 외부에서 인스턴스나 클래스를 이용해서 접근가능 ->밖에서도
4. static 변수는 클래스와 인스턴스 모두 접근 가능하지만 member variable은 인스턴스만 접근 가능
=>static은 공통된 내용을 저장할 때 사용하고 menmber variable은 각각의 특징을 저장할 때 사용
5.실습
1)final이 붙이면 변수의 값을 수정할 수 없습니다.
=>MainClass 의 main 메소드에 final 변수를 선언
//이럴 경우 에러가 난다.
//final int x;
//x = 10;
//final 변수는 생성과 동시에 값을 할당
//값을 변경할 수 없기 때문입니다.
//final 변수의 이름은 모두 대문자로 만드는 것이 관ㄱ례
//final int x = 10;
//x =20; //이문장은 에러
finalintTEN = 10;
=>fianl은 클래스 안에서 옵션을 만들 때 주로 사용
일반 정수 데이터를 의미있는 이름을 부여해서 이해하기 쉽게 할 목적
2) SampleClass에 변수를 선언
//main 메소드가 없는 클래스 - 실행할 수 없는 보조적인 역할을 수행하는 클래스
publicclass SampleClass {
//static변수 - 클래스로 접근 가능하고 인스턴스로도 접근 가능
//모든 인스턴스가 공유
staticintshare = 1;
//인스턴스 변수(멤버 변수)- 인스턴스만 접근이 가능하고 각 인스턴스가 별도로 소유
String name;
}
3)MainClass 클래스의 main 메소드에서 static이 붙은 것과 그렇지 않은 변수의 차이를 알아보는 코드 작성//SampleClass의 인스턴스를 2개 생성
SampleClass ob1 = new SampleClass();
SampleClass ob2 = new SampleClass();
//인스턴스 변수에 값 대입
ob1.name = "첫번째 인스턴스";
ob2.name = "두번째 인스턴스";
//static이 붙지 않은 멤버는 클래스는 호출 할 수 없습니다.
//SampleClass.name 은 안됨 항상 인스턴스로 호출해야 한다.
//인스턴스 변수의 값 출력 - 인스턴스 변수는 각각 소유하기 때문에 서로 다른 값 출력
System.out.println(ob1.name);
System.out.println(ob2.name);
//static변수에 값 대입
SampleClass.share = 200;
//static변수는 하나만 만들어서 공유
//출력을 해보면 동일한 값을 출력
System.out.println(ob1.share);
System.out.println(ob2.share);
System.out.println(SampleClass.share);
4)private과 public차이
=>클래스 안에서 private으로 만들어지면 클래스 안에서만 사용가능
=>public으로 만들어지면 클래스 외부에서 클래스 이름이나 인스턴스를 통해서 사용이 가능
=>클래스 안에서 사용을 할 때는 이름만 호출하면 됩니다.
SampleClass에서 share변수 선언문 앞에 private을 추가하고 저장을 하면 main 메소드가 에러가 발생합니다.
이 에러는 없다라고 에러 메시지가 뜨지 앟고 존재하지만 보이지 않는다는 에러 메시지가 출력
//main 메소드가 없는 클래스 - 실행할 수 없는 보조적인 역할을 수행하는 클래스
publicclass SampleClass {
//static변수 - 클래스로 접근 가능하고 인스턴스로도 접근 가능
//모든 인스턴스가 공유
privatestaticintshare = 1;
//인스턴스 변수(멤버 변수)- 인스턴스만 접근이 가능하고 각 인스턴스가 별도로 소유
String name;
}
private 하면 바깥쪽에는 사용이 불가하다.
5).static멤버를 인스턴스를 이용해서 접근하면 경고가 발생
=>static 멤버는 클래스 이름을 통해서 접근하는 것을 권장
\
메모리는 3개 영역이다.
MainClass -> public static void main(String[] args){ 수행:
SampleClass ob1 = new SampleClass();
static
Heap
stack
args
table
SampleClass ob1 = new SampleClass();이 명령에서
1). SampleClass 가 table에서 확인
SampleClass 이름 있는지 확인 table code에서 존재하는 지 확인
table code로 존재하는 것만 할당
static에 있는 것은 할당 안한다.
2).table없으면 static 확인후 등록
인스턴스는 자신이 할당 받은 메모리 공간에서 데이터를 찾지 못하면 클래스 영역에서 찾는다.
static 공간 주는 것이고 static없는 것은 코드 주고 공간만 준다.
3)ob1
4)new SampleClass()
==================>SampleClass ob2 = new SampleClass();
SampleClass확인
ob1.name ="첫번째"
ob1.name ="두번째"
SampleClass.share = 100;
SampleClass.name ->이렇게 하면 오류 난다. 없다. 안보이는 것이 아니라 없다.
ob1.share = 200 이것은 가능하다.
static 은 한번 만들면 그냥 나두고 static 아니면 계속 따로 만든다.
인스턴스는 자기한테 없으면 table에 가서 찾고 static에 가서 바꾼다.
static인스턴스나 class가나 결과는 같다.
메소드 끝나면 없어진다. stack없어지고 heap위 없어지고 하지만 없어지는 것이 아니라 사용불가하게 하고 사용가능으로 바꿀 수 있다. 할당 할수 도 있다.
1101->지우려면 0000 덮어씌우기
0에서 삭제된 데이터를 찾을 수 있다. 할당할 수 있어 자꾸 쓰고 삭제를 하면 복구가 힘들다.
java는 가르키는 겂이 없으면 소멸
java는 항상 누가 가르키는지
python a= 10 b =areatail cont
a = None -> retail count 가 하나씩 깍는다.
python는 retail count
프로그램으로 하는 것은 java가 빠르는데 데이터베이스는 썼다 삭제했다 해서 좀 느리다.
뱅뱅 돌아왔다. class 참조하면 되는데
6.static initializer
=>클래스 안에
static{
내용
}
=>을 작성하면 클래스가 메모리에 로드될 때 1번만{}안의 내용을 수행
=>여기에는 static변수는 사용할 수 있지만 member(instance)변수는 사용할 수 없음
=>주로 static변수의 초기화에 이용
=>여러 번 작성하면 작성 한 순서대로 실행
실습)
SampleClass에 static초기화 블럭을 작성하고 MainClass실행
=>가장 먼저 내용이 출력
//static 초기화 블럭
static {
System.out.println("클래스가 처음 호출될 때 1번만 수행");
}
**Method
=>전달받은 데이터를 이용해서 처리를 수행한 후 결과를 돌려주는 작은 프로그램
=>Function이라고도 하는데 보통은 Function 은 아무곳에서나 호출할 수 있는 것을 의미하고 Method는 클래스나 인스턴스를 통해서만 호출할 수 있는 것을 의미합니다.
