많은양의 데이터를 어떻게 컴퓨터가 효율적으로 처리하는 지 알기 위해선 자료구조에 대한 이해가 필요합니다.
자료구조의 종류와 정의는 무엇인지 알아보겠습니다.
데이터를 효율적으로 관리하기위해서 효율적이라는 것의 기준이 필요합니다. 프로그램의 복잡도를 계산하면 알고리즘을 비교하여 사용할 수 있습니다.
시간복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다.
다음은 알고리즘을 비교할 때 고려해야하는 몇가지 규칙을 나열했습니다.
1. 입력값(n)은 항상 0보다 크다.
2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 된다.
3. 시간 복잡도에서는 모든 상수를 삭제한다.
만약 어떤 알고리즘의 복잡도가 이라면 3은 고려하지 않고 복잡도는 이 됩니다. , , 모두 복잡도가 인 알고리즘입니다.
4. 낮은 차수의 항들은 무시한다.
++이라는 함수가 있고 ,는 알고리즘의 시간 복잡도에 영향을 미치지 않고 입력값이 무한이 될때 고려해야할 부분은 입니다.
5.시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시한다.
모든 로그는 배수관계이므로 로그의 밑에 대해서는 고려하지 않아도 됩니다.
복잡도가 인경우에는 보통 무언가를 반으로 나누거나 2를 곱한경우에 사용됩니다. 그래서 for문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됩니다. 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 복잡도를 가진다고 표현합니다.6.등호를 사용하여 표현한다.
은 과 같습니다. 즉 은 이 어떤 함수의 집함에 속한다는 의미를 가집니다.
빅오표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 이 표기법을 통해 알고리즘을 비교해 표현할 수 있습니다.
위 그래프는 복잡도가 인 알고리즘에 빅 오 표기법을 적용한 결과입니다. x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미합니다.
알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있습니다.
- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. (=<)
- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.(==)
- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.(>=)
- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.(<)
- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.(>)
자료구조를 이해하기위해 객체지향에 대해서 알고있어야합니다.
특히 객체지향의 상속과 클래스에 대해 짚고넘어가겠습니다.
int i = 10
int는 자바에서 4바이트를 필요로 하므로 이 코드에서는 i에 4바이트의 메모리가 할당되었을겁니다.
이와 같이 short는 2바이트, long은 8바이트를 할당합니다.
Student s = new Student();
여기서 s는 얼마의 메모리를 사용하게 될까요?
JVM은 이와같이 객체(인스턴스)가 만들어지면 코드를 읽고 얼마의 메모리가 필요할지 계산하고 그 공간을 힙에 힐당합니다.
그리고 그 힙을 가르치는 4바이트의 포인터를 만듭니다.
JVM이 이 공간을 할당해 주기위해선 이 Student 객체가 무엇인지 알아야합니다.
이를 위해 상속을 활용합니다.
Person은 사람입니다.
Student는 학생입니다.
Undergraduate는 학부생입니다.
아래처럼 클래스를 구성하면 학생이 사람에 속하게 되고 학부생이 학생에 속하게 되면 학부생도 사람에 속하게 됩니다.
이러한 관계를 상속이라고 합니다.
public class Person{
}
public class Student extends Person{
}
public class Undergraduate extends Student{
}
Student라는 객체가 생성되면 JVM은 person을 상속한다는 것을 알아채고 person의 변수와 메소드를 가져옵니다.
java 상속의 특징
1. Java에서 각각의 클래스는 하나의 클래스만 상속받을 수 있습니다.
2. 상속받는 클래스의 정보만 갖고 있습니다.
3. 상속받는 클래스의 공간을 함께 할당합니다.Person u = new Student();이라 정의하였을 때, 컴파일이될까요? -> Student에는 Person이 가지고 있는 만큼의 공간의 힙에 할당되어있으므로 컴파일이 가능합니다.
객체에서 숫자, 문자열 비교를 할땐 객체의 비교 방법인 Comparable 인터페이스를 사용합니다.
String one = "hello world";
String two = "hello world";
// 문자열 비교
if(one.equals(two))
System.out.println("they are the same")
Object one = "hello world";
Object two = "hello world";
// 객체 비교
if(one.equals(two))
System.out.println("they are the same");
위 코드는 문자열과 객체를 equals함수를 사용해 비교한 것입니다.
문자열을 비교한 경우 참이 출력될것입니다.
그러나 객체를 비교한 경우 equals함수는 객체의 메모리 주소값을 비교할 것입니다
결국 두 객체는 같지 않다고 나올것입니다.
이걸 각각 call by vaule, call by references라고 합니다.
Comparable 인터페이스를 사용하면 객체를 자료형으로 비교하여 사용 할 수있습니다.
if(((Comparable) data).compareTo(obj)==0)
위 compareTo 함수는 a.compareTo(b)는 a가 b보다 작을 때는 0보다 작은 수, a와 b가 같으면 0, a가 b보다 크면 0보다 큰 수를 반환합니다.
if(((Comparable) data).compareTo(obj)==0)
앞서 본 위 코드는 객체를 자료형으로 바꾸어 준다고 했습니다.
그럼 객체의 무슨 자료형으로 바꾸어 줘야할지 어떻게 알까요?
T는 Type을 뜻합니다.
그리고 이 Type에는 다양한 자료형이 들어갈 수 있습니다.
이는 코드를 재사용한다는 객체지향의 기법 중 하나입니다.
위처럼 제네릭은 <>안에 Type Parameter를 넣어 컴파일시 구체적인 타입이 정해집니다.
// 클래스
public class LinkedList
public class LinkedLilst<E> // 매개변수화 타입사용
// 함수
public void addFirst(String S)
public void addFirst(E obj) // 매개변수화 타입사용
public String removeFirst()
public E removeFirst() // 매개변수화 타입사용
위는 객체를 사용한 방식과 매개변수화 타입을 사용한 방법입니다.
byte, short, int, char 등의 기본 자료형에 대해서 Java 가상 머신은 정확하게 필요한 만큼의 메모리를 할당합니다. 하지만 객체에 대해서는 이 객체를 가리키는 4바이트짜리 포인터와 힙의 공간을 할당합니다.
즉 기본 자료형은 객체가 아니고이것들은 객체 메소드를 상속받지 않습니다.
하지만 Wrapper Class를 이용해 기본자료형을 객체버전으로 사용할 수 있습니다.
byte -> Byte
short -> Short
int -> Integer
char -> Char
// Exception 클래스 상속
public class FileFormatException extends Exception{
public FileFormatException (){
// super 호출
super();
}
public FileFormatException (String s){
super(s);
}
}
// 예외 상황이 발생하면 throw
throw new FileFormatException("Your file is not well formatted")
위 코드에서와 같이 Exception 클래스를 상속받고 생성자를 만든 후, 생성자 안에서 super를 호출하면 예외 상황에 대한 클래스를 만들 수 있습니다. (super는 만약 어떤 것을 상속받았을 때 상속받은 클래스의 생성자를 호출한다는 의미입니다.)
이후 예외 상황이 발생하였을 때 throw를 사용하면, 그 예외 상황의 이름으로 에러가 발생하게 됩니다.