본 문서는 작성이 중단되었습니다.
개요
자바는 싫다. 일단 메소드 이름이 너무 길다. 작명 규칙을 따르다 보면 변수명도 길다.
프로그램을 실행하기 위해선 사용자 디바이스에 자바가 꼭 필요하다. 이를 통해 원활한 크로스 플랫폼 생태계를 만든 건 좋은데, 윈도우나 리눅스 배포판에 기본으로 설치해 주면 어디가 덧나나.
나는 종속성을 싫어한다. 그래서 자바도 싫다.
그러나 학교에서 자바를 가르치기 시작했다. 별다른 수가 없군. 두 눈 꼭 감고 하루만에 끝내 버리자.
개념 정리 노트조차 블로그 포스팅에 이용할 생각을 하다니. 잡동사니만 쌓여가는 블로그 모습이 안쓰럽기까지 하다. 미안해 블로그야.
자바로 만드는 첫 프로그램
모든 것에 앞서 세상에 인사를 건네는 것은 불문율이다.
public class HelloWorld {
public static void main(String[] args){
System.out.println("Hello, world!");
}
}
기본 자료형
자바의 자료형은 기본형과 참조형으로 나뉘는데, 참조형은 C++의 레퍼런스같은 녀석이고 찐 근본 자료형은 기본형(primitive type)이 되시겠다.
| 분류 | 이름 | 바이트 수 | 비고 |
|---|---|---|---|
| 정수 | byte | 1 | |
| short | 2 | ||
| int | 4 | ||
| long | 8 | ||
| 실수 | float | 4 | |
| double | 8 | ||
| 문자 | char | 2 | 유니코드 사용 |
| 불리언 | boolean | 1 | true, false |
+참조 자료형
기본 자료형을 제외한 나머지는 전부 참조 자료형이다. 세상에 포인터가 없다니.
몇 가지 종류가 있지만 지금은 String, Class, Array, Interface 정도만 알고 넘어가자.
이중 String은 유일하게 언어 자체에 완전히 정의되어 있는 참조 자료형이다.
특징
-
new 키워드를 이용해 생성 후 할당하며, 힙 영역에 데이터가 저장되지만 가비지 콜렉터 덕분에
free같은 함수가 필요하지 않다. -
null을 할당할 수 있다.
표준 입출력
출력은 그렇다 치더라도 입력 방식이 상당히 특이하다.
input stream을 분석하는 다양한 메소드를 가진 클래스 Scanner에, 표준 입력과 연결된 객체 System.in를 넘겨줘야 한다.
import java.util.*;
public class UseInput {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String first_name = input.next();
String last_name = input.next();
System.out.print("Your name is");
System.out.println(first_name+" "+last_name);
}
}
final 한정자
final double PI = 3.14159;
C의 const와 같은 역할이다.
형변환
자동 형변환
- 문자열과 숫자의
+연산: 숫자가 문자열로 변환 - 서로 다른 숫자 자료형의 연산: 정확도 손실이 없는 쪽으로 변환
함수 호출
함수의 입력 자료형과 출력 자료형이 다른 경우…도 형변환으로 볼 수 있으려나.
Integer.parseInt("123")
명시적 형변환(Explicit case)
(int) 3.14 // 3
(int) Math.round(3.14) // 3
11 * (int) 0.25 // 0
If, while, do-while, for, switch
C언어와 동일하게 사용 가능하다.
function
접근 한정자와 static에 대해 고려해야 한다. 나머지는 C++과 동일하게 사용 가능하다.
OOP
객체 지향 프로그래밍은 추상화, 캡슐화, 모듈화를 핵심 개념으로 한다.
-
추상화(Abstraction)
어떤 대상의 구현과 사용의 중간 위치에서 둘을 분리하는 것. 그 대상이 가져야 할 필수 요소를 선언함으로써 이루어진다.
구현 측면에서는 실제로 어떤 기능을 만들어야 하는지에 대한 specification,
사용 측면에서는 구현 방식을 몰라도 모델을 보고 사용할 수 있는 interface 또는 API 역할을 한다.
자바에서는 abstract data types(ADT)라는 개념으로 자료형에 대한 추상화를 실현한다.
-
캡슐화(Encapsulation)
객체의 구현 일부를 은닉하는 것. 추상화화 비슷한 맥락이 있는데, 의도하지 않은 데이터 조작을 방지하는 측면에 초점을 둔다.
-
모듈화
라이브러리를 통해 코드 재사용성을 높인다.
ADT 만들기
- API 명세를 작성하기
- API를 보고 자바 클래스를 구현하기
- API를 보고 테스트 클라이언트를 개발하기
배열(Array)
동일 자료형 데이터의 순서 있는 나열.
자바에서 배열은 포인터와 다르다. 애초에 포인터가 없지 않은가.
대신 자바 배열은 참조형(reference type)으로서, 객체 비슷하게 다뤄진다. 따라서 new 키워드를 통해 힙 영역에 할당한다.
double[] a = new double[n]; // 0으로 초기화
double[] x = { 0.3, 0.6, 0.1}; // 리터럴 초기화
a.length
java.utils.Arrays에는 배열을 조작하는 유용한 메서드가 정의되어 있다.
import java.util.Arrays;
public class ArrayMethods {
public static void main(String[] args){
int[] list1 = {100, 50, 20, 30, 80};
int[] list2 = {100, 50, 20, 30, 80};
System.out.println(Arrays.toString(list1));
System.out.println(Arrays.equals(list1,list2));
}
}
문자열을 문자 배열로 바꿀 수도 있다.
String s = "computer";
char[] arr1 = s.toCharArray();
for(int i=0;i<arr1.length;i++)
System.out.print(arr1[i]+" ");
객체 배열
배열 원소로 임의의 자료형을 지정할 수 있다.
-
기본 자료형
char[] input = {'d','a','t','a'}; -
참조형 변수
String fruits = {"Apple","Orange","Lemon","Cherry"}
2차원 배열
자바의 2차원 배열은 C언어의 그것보다 훨씬 직관적이다. 그냥 배열의 배열이라고 생각하면 된다.
double[][] a = new double[m][n];
a.length // 행 개수
a[0].length // 열 개수
double[][] p = { {.1, .2}, {.3, .4}, {.5, .6} }; // 리터럴 초기화
+ragged array
이러한 배열의 특성 때문에 각 행 별로 열의 수를 다르게 할당할 수도 있다. C언어를 사용하는 입장에선 그저 신기할 따름.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int column;
char[][] data = new char[5][];
for(int i=0; i<5;i++) {
column = input.nextInt();
data[i] = new char[column];
for(int j=0;j<column;j++) {
data[i][j] = '*';
}
}
for(int i=0; i<data.length;i++) {
for(int j=0; j<data[i].length;j++) {
System.out.print(data[i][j]+" ");
}
System.out.println();
}
}
마지 C++의 vector를 사용하는 것 같다. 생각해 보니 비슷한 것 같기도.
연결 리스트
배열 다음에는 리스트가 나오는 게 인지상정. 더 이상의 자세한 설명은 생략한다.
제네릭
C++의 템플릿 메타프로그래밍과 같은 문법, 용도를 가지는 개념이다.
그러나 내부적으로는 좀 다른데, 제네릭은 메타프로그래밍과는 거리가 멀고, 레퍼런스 타입만을 가진다.
제네릭을 사용해서 연결 리스트를 구현하면 임의의 객체 타입에 대한 연결 리스트를 만들 수 있다.
public class Pair<A,B> {
A first;
B second;
public Pair(A a, B b) {first = a; second = b;}
public A getFirst() {return first;}
public B getSecond() {return second;}
}
public static void main(String[] args) {
Pair<String, Double> p1 = new Pair<>("Alice", 28.35); // 타입 추측
Pair<String, Double> p2 = new Pair<String, Double>("Bob", 45.00); // 타입 명시
System.out.println(p1.getFirst());
System.out.println(p2.getFirst());
}
}
public class SinglyLinkedList<E> {
추가 바람
}
알고리즘 분석 방법
시간 복잡도 분석
Big-O 표기법을 이용한다. 일반적으로 알려진 방법과 다르지 않다.
공간 복잡도 분석
자바의 데이터 저장 구조를 알아볼 필요가 있다.
기본 자료형의 크기
| type | bytes |
|---|---|
| boolean | 1 |
| byte | 1 |
| char | 2 |
| int | 4 |
| float | 4 |
| long | 8 |
| double | 8 |
객체의 크기
-
객체 오버헤드: 16bytes
객체 클래스 참조, 가비지 콜렉션, 정보 동기화에 대한 정보를 저장한다.
-
레퍼런스: 8bytes
객체 변수에 실제로 저장되는 객체 주소값.
-
패딩: 각 object는 8바이트의 배수로 맞춰진다.
메모리 접근과 가비지 콜렉터 속도를 최적화하기 위해 필요하다.
//Example
public class Data
{
private int day;
private int month;
private int year;
}
// overhead(16) + int(4) + int(4) + int(4) + padding(4) = 32 bytes
배열의 크기
배열은 객체의 한 종류지만, 길이 정보를 저장하기 위해 추가적인 오버헤드를 필요로 한다.
기본 자료형 배열
기본 자료형 배열은 다음과 같이 24바이트의 헤더 정보를 가진다.
object overhead(16) + length(4) + padding(4) = 24 bytes
따라서 각 타입에 대한 실제 크기는 다음과 같다.
| type | bytes |
|---|---|
| char[] | 2N + 24 |
| int[] | 4N + 24 |
| double[] | 8N + 24 |
객체 자료형 배열
객체 배열에는 객체의 레퍼런스가 저장되며, 각각의 객체는 또한 고유의 크기를 가지고 있다.
따라서 **32 bytes **인 Data 배열의 실제 크기는
Array overhead(24) + References(8N) + Real Objects(32N) = 24 + 40N bytes
재귀 함수
다른 언어와 동일하게 사용 가능하다.
스택
이제부터 진짜 Java의 시작이다. 앞의 내용에서는 Java가 다른 언어에 비해 나은 점이 딱히 없어 보이지 않았는가. 가비지 콜렉터 빼고. 가비지 콜렉터는 굉장하고 엄청나다. 입력할 때마다 손발이 벌벌 떨리던 new 키워드를 두 줄 건너 하나씩 쓰게 될 줄이야.
아무튼 간에 여기서부터 ADT의 위력이 발휘된다.
알다시피 스택은 LIFO 구조로 요약된다. 우리는 추상화를 좋아하기 때문에 스택이 데이터를 어떻게 저장하는지는 신경쓰지 말자.
아래의 메서드 집합은 스택 구조의 추상적 특징, 다른 말로 model, 또 다른 말로 명세, 또또 다른 말로 인터페이스, 또또또 다른 말로 API(…)를 정의한다.
API
- void push(E item)
- E pop()
- E top()
- boolean isEmpty()
- int size()
구현: 배열 기반 스택
위의 API를 실제로 구현하기 위해 배열을 이용할 수 있다.
필드와 생성자를 포함한 기본 구조는 다음과 같다.
public class ArrayStack<E> implements Stack<E> {
public static final int CAPACITY=1000;
private E[] data;
private int t = -1;
public ArrayStack() { this(CAPACITY); }
public ArrayStack(int capacity) {
data = (E[]) new Object[capacity];
}
}
여기서 주의해야 하는 부분은, 자바는 제네릭 배열의 생성을 허용하지 않는다는 점이다.
전문가들 사이에서도 논쟁이 되는 부분이라나 뭐라나. 자세한 내막을 찾아 볼 의향은 없으나 해결 방법은 알아 둬야겠지.
private E[] data = new E[capacity]; // ERROR
private E[] data = (E[])new Object[capacity]; // OK
모든 객체의 조상님쯤 되는 Object 타입으로 배열을 만들고 제네릭 타입으로 캐스팅해주면 된다.
분석: 배열 기반 스택
- 모든 연산이 상수 시간에 이루어지는가? -> O
- 저장되는 데이터 수와 메모리 사용이 비례하는가? -> X
- 데이터 개수 제한이 없는가? -> X
평가: 데이터 개수의 상한이 정해져 있는 경우에 사용할 수 있겠다. 그러나 앞서 정의한 API의 구현으로는 부적합하다.
구현: 연결 리스트 기반 스택
public class LinkedStack<E> implements Stack<E> {
private SinglyLinkedList<E> list = new SinglyLinkedList<>();
public LinkedStack() { }
...
}
분석: 연결 리스트 기반 스택
- 모든 연산이 상수 시간에 이루어지는가? -> O
- 저장되는 데이터 수와 메모리 사용이 비례하는가? -> O
- 데이터 개수 제한이 없는가? -> O
큐
스택 다음에 큐가 등장하는 것은 불문율.
API
- void enqueue(E item)
- E dequeue()
- E first()
- boolean isEmpty()
- int size()
구현: 연결 리스트 기반 큐
리스트
앞서 연결 리스트를 구현한 바가 있다. 그러나 Java는 리스트에 대한 ADT를 제공한다.
요구사항은 크게 보면 데이터가 선형적 순서관계를 가져야 하고, 인덱스 기반 접근이 가능해야 한다.
트리
그래프 이론에서의 트리와 달리 데이터 구조로서의 트리는 노드 간의 계층 구조로 정의된다.
루트 노트, 내부 노드, 말단 노드, 노드의 깊이, 트리의 높이, 부분 트리 등을 함께 정의할 수 있다.
- Root: 부모가 없는(!) 노드
- Internal node: 적어도 하나의 자식을 가지는 노드
- External node: 자식을 가지지 않는 노드
- Depth of a node: 루트와 해당 노드를 연결하는 path의 길이
- Height of a tree: 각 말단 노드의 깊이 중 최댓값
- Subtree: 특정 노드와, 그 노드의 모든 descendants를 포함하는 트리
single node tree의 높이는 0이라고 할 수 있으며, 관습적으로 empty tree의 높이는 -1로 정의한다.
additional terminology
한편 각 노드의 자식 수가 2이하이면 이진 트리라고 하며 left child와 right child를 구분하여 표기한다.
각 노드의 자식 수가 0또는 2이면 포화 이진 트리(full binary tree)라고 한다.
BST
이진 트리의 각 노드에 값이 대응되어 각 노드의 값이
- 왼쪽 subtree의 임의의 노드의 값보다 크고
- 오른쪽 subtree의 임의의 노드의 값보다 작으면
이를 이진 탐색 트리(binary search tree)라고 한다.
Comparable Interface
비교 가능한 클래스를 구현하는 자바 인터페이스로, compareTo(w) 메서드를 선언한다.
Integer v = new Integer(5);
Integer w = new Integer(10);
Integer z = new Integer(10);
System.out.println(v.compareTo(w)); // -1
System.out.println(w.compareTo(z)); // 0
System.out.println(w.compareTo(null)); // exception
우선순위 큐와 힙 정렬
스택이 가장 마지막에 추가한 원소를 반환하고, 큐가 가장 먼저 추가한 원소를 반환하는 것처럼 우선순위 큐는 가장 큰 원소(또는 가장 작은 원소)를 반환한다.
이는 ADT로 다양한 방법을 이용해 구현할 수 있지만, 사실상 이진 힙을 이용한 구현이 가장 효율적이다.
이진 힙
다음 두 가지 특성을 만족하는 트리를 이진 힙이라고 한다.
구조적 특성: 완전 이진 트리의 형태를 유지
관계적 특성: 각 노드는 그 자식들보다 크거나 같은 값을 가짐
원소를 추가하거나 제거하면 이진 힙 조건에서 벗어난다. 따라서 다시 이진 힙으로 만들어 주는 조작이 필요하다.
Bottom-up reheapify (swim up)
어떤 child가 parent보다 큰 값을 가질 때, parent와 자리를 바꾸면서 올라가게 한다. 해당 노드가 제자리를 찾아갈 때까지 이를 반복한다. 트리에서 child가 헤엄쳐 올라가는 것처럼 보인다.
Top-down reheapify (sink)
어떤 parent가 child보다 작은 값을 가질 때, 두 child 중 더 큰 노드와 자리를 바꾸면서 내려가게 한다. 해당 노드가 제자리를 찾아갈 때까지 이를 반복한다. 트리에서 parent가 가라앉는 것처럼 보인다.
힙 연산
insert(x): 노드를 가장 마지막에 추가하고 swim up을 수행한다.
delMax(): 루트 노드와 가장 마지막 노드를 교환하고 새로 바뀐 루트에 대해 sink를 수행한다. 원래 루트였던 노드를 제거하면서 반환한다.
분석: 이진 힙 기반 우선순위 큐
삽입: O(log N)
최댓값 삭제: O(log N)
최댓값 반환: O(1)
힙 정렬
우선순위 큐를 이용해 원소 정렬을 수행할 수도 있다.
힙 정렬은 다음 두 단계로 나뉜다.
- Heap construction: N개의 키값으로 최대 힙을 구성한다.
- Sortdown: 반복적으로 최대 키값을 삭제한다.
추가 바람
맵과 해시 테이블
Map ADT
key-value 쌍의 추상화. 특정 키와 함께 값을 넣으면, 이후에 키를 통해 값에 접근할 수 있다.
symbol tables, dictionaries, associative arrays 등으로 불리기도 한다.
맵에 대한 한 가지 재미있는 해석은 배열(array)에 대한 일반화라는 것이다. 배열은 키값이 {0, 1, … n-1}인 Map으로 생각할 수 있다.
물론 실제 구현은 전혀 다르거나 오히려 배열을 이용해 맵을 구현하기도 한다. 추상적인 기능이 그렇다는 의미다.
관습
- 중복 키 없음
- null key 없음
- null value 없음
- key는 비교 가능함
- key-value 쌍의 개수에 제한이 없음
java.util package 내부의 Map ADT 구현
java.util.HashMap, java.util.LinkedHashMap, java.util.TreeMap은 모두 Map ADT를 구현하고 있으며 내부 구현 방식은 각각 다르다.
집합(set)
2-3 trees
각 노드가 두 개 혹은 세 개의 자식을 가지는 탐색 트리이다(null child 포함).
Symmetric order와 Perfect balance를 특징으로 한다.
insertion이 독특한 방식으로 이루어지는데, 말단 노드까지 탐색 후 그 자식이 아닌 해당 노드 자체에 키를 추가한다. 4-node가 되면 가운데 키를 위쪽으로 올려버린다.
때문에 실질적으로 트리의 높이가 증가하는 순간은 root node의 split이 일어나는 때밖에 없다. 따라서 루트로부터 각 말단 노드까지의 거리는 모두 동일하다.
그러나 이진 트리를 개선하기 위한 방법임에도 불구하고 2-3 tree는 이진 트리가 아니기 때문에 구현이 복잡해진다는 단점이 있다.
2-3 tree와 매우 유사하면서 이진 트리로 구현 가능한 다른 방법이 있는데 바로 LLRB라고 한다.
LLRB
2-3 tree에서 3-node를 두 개의 2-node 결합으로 생각할 수 있다.
이때 두 개의 노드를 연결하는 edge를 왼쪽으로 향하는 빨간색 edge로, 나머지를 검은색 edge로 그리기 때문에 Left-Leaning Red-Black BST, 줄여서 LLRB라고 한다.
2-3 tree와 대응시켜 생각해 보면 다음과 같은 특징을 가진다.
- Symmetric order(BST)
- Red link는 두 개 연속으로 연결될 수 없다
- Red link는 왼쪽 방향으로 향해 있어야 한다
- 루트에서 각 말단 노드(또는 null node)까지의 경로를 구성하는 검은색 link의 개수는 항상 동일해야 한다
각 노드는 부모와 연결된 링크의 색깔을 나타내는 color 프로퍼티를 추가로 가진다.
이진 탐색 트리
그럼 다음에,
Gabriel-Dropout
at 04:43
