정용이의 놀이동산

개요 JVM의 Runtime Data Areas에서 Heap은 객체를 저장합니다. 객체에 대한 참조 변수는 Stack에 있습니다. Oracle의 Hotspot VM의 Heap 구조 Young Generation Eden 객체가 최초로 할당되는 장소 Eden이 포화상태이면 참조중인 모든 객체를 Survior로 옮깁니다. Survivor로 참조중인 객체가 모두 옮겨지면 Garbage Collection(Minor GC) 수행합니다. Survivor Survivor 1, Survivor 2로 이뤄져 있습니다. 참조중인 객체들은 하나의 Survivor 영역만 사용합니다. Old Generation Survivor 에서 오랫동안 참조되고 있는 객체는 Tenured로 이동합니다. Tenured에 온 객체는 앞으로도..

개요 자바 프로그램이 실행되는 가상 환경 자바 개발자는 바이트 코드 파일을 배포하는 과정까지만 합니다. 사용자가 자바 프로그램을 실행하려면 JVM이 필요합니다. JVM은 바이트 코드가 각 OS에서 실행될 수 있도록 기계어로 변환하고 프로그램을 실행합니다. JVM을 통해서 플랫폼 독립적인 개발이 가능해집니다. JVM 구조 자바 프로그램은 각 OS에 최적화된 JVM 위에서 실행됩니다. Class Loader Loading : 클래스를 적재 Linking : 래퍼런스를 연결 Initialization : static 값 초기화 & 변수 할당 Memory Stack 스레드마다 런타임 스택 생성 메소드 호출을 스택 프레임으로 쌓음 스레드가 종료되면 런타임 스택도 사라짐 PC Registers 스레드마다 현재 실행..

개념 익명 함수를 의미합니다. 람다식으로 구현하는 방식을 함수형 프로그래밍이라고 합니다. 함수형 프로그래밍에서 개발자는 핵심 내용만 구현하고, 나머지는 Java에서 자동으로 처리합니다. 함수형 스타일은 서술형 스타일에 객체의 개념과 명령문을 추가하여 처리하는 스타일입니다. 인터페이스를 람다식으로 구현 람다식으로 구현하려는 인터페이스는 반드시 1개의 메서드만 선언되어야 합니다. 1개의 메서드만 구현된 인터페이스를 함수형 인터페이스라고 합니다. 기본 문법 명령문이 1개일 때 : () -> 명령문; 명령문이 여러 개일 때 : () -> {명령문1; 명령문2; ... 명령문n;} @FunctionalInterface 함수형 인터페이스를 구현할 때, 2개 이상의 추상 메서드 선언되는 오류를 방지하기 위해서 @Fu..

개요 펜윅 트리(Fenwick Tree)라고도 한다. 누적 합 배열의 동적 자료구조이다. 이름은 트리이지만 배열로 표현한다. 모든 배열의 인덱스가 1부터 시작한다고 가정한다. 그래야 구현하기가 좀 더 쉽다. 시간복잡도가 O(log n)인 2가지 연산을 제공한다. update(int k, int diff) : 배열의 원소 갱신 sum(int k) : 1번 원소부터 k번 원소까지의 구간 합 계산 p(k) : k의 약수 중에서 가장 큰 2의 거듭제곱. p(k) = sum(k - p(k) + 1, k) 위치 k에서 끝나면서 그 길이가 p(k)인 구간의 합 BIT를 사용하면 어떤 sum(1, k)의 값도 O(log n)에 구할 수 있다. 배열의 원소를 갱신하면 BIT에서 해당 원소가 포함되어 있는 값도 갱신해야 ..

개념 스트림 데이터는 처리 과정에서 임시로 존재합니다. 스트림은 필요한 작업을 수행한 후 자동으로 소멸합니다. 데이터 소스 원본을 변경하지 않고도 데이터를 처리할 수 있습니다. 구성 스트림 생성 중개 연산 스트림을 받아서 스트림을 반환합니다. 여러개의 중개 연산을 수행할 수 있습니다. 중개 연산은 일반적으로 지연 연산입니다. 최종 연산 스트림의 결과를 산출합니다. 이때 지연 연산으로 미뤄진 중개 연산을 수행합니다. 최종 연산 이후 스트림은 소멸합니다. 특징 스트림은 각 요소의 처리 방법에 관심을 두고 있습니다. 개발자가 반복문을 구현해서 요소에 접근 --> 외부 반복 스트림은 내부적으로 각 요소마다 접근 --> 내부 반복 파이프-필터 패턴 스트림은 데이터에 대해서 각종 중개 연산(필터) 후 최종 연산으로..

개요 그리디 기반의 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘 간선을 다 떼어내고 가중치 순으로 간선들을 조회하며, 사이클이 생기지 않으면 간선을 노드에 연결한다. 알고리즘 실행을 마친 후에는 모든 노드가 연결된 MST가 완성된다. 가중치를 오름차순으로 정렬하여 연결하면 최소 신장 트리, 가중치를 내림차순으로 정렬하여 연결하면 최대 신장 트리를 구할 수 있다. MST를 만들기 위해서는 반드시 최소 가중치 간선이 포함되어야 하므로, 크루스칼 알고리즘의 결과는 항상 MST이다. 구현 그래프를 간선 리스트 형태로 구현하는 게 편리하다. 간선이 사이클이 형성되는지 파악하고, 간선을 연결하기 위해서 유니온-파인드 자료구조를 사용한다. 노드가 n개, 간선이 m개일 때, 간선..

개요 집합의 묶음을 관리하는 자료구조이다. 집합은 서로소 집합(Disjoint Set)이고, 하나의 원소는 오직 하나의 집합에 속한다. 집합마다 하나의 원소가 해당 집합의 대푯값이 되고, 나머지 원소에서 대표 원소로 가는 경로가 존재한다. 유니온-파인드 자료구조는 O(Log n)의 시간복잡도를 가진 2가지 메서드를 제공한다. unite(a, b) : a와 b가 속한 각각의 집합을 하나로 합친다. find(x) : x원소가 속한 집합의 대푯값을 반환한다. 집합을 합칠 때, 원소가 더 적은 집합의 대푯값을 원소가 더 많은 집합의 대푯값으로 연결함으로써 효율적인 unite 연산을 수행할 수 있다. 구현 유니온-파인드는 배열을 사용해서 쉽게 구현할 수 있다. 배열은 각 원소에 대해서 경로상의 다음 원소를 저장하..

개요 모든 노드에서 모든 노드까지의 최단 경로를 계산하는 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 계산할 수 있다. 노드 간 거리를 저장하기 위해서 행렬을 사용한다. 행렬의 초깃값은 그래프의 인접 행렬과 같다. 매 라운드마다 각 경로에서 중간 노드로 사용할 노드를 선택하여 거리를 줄여나간다. 구현 3중 반복문으로 쉽게 구현할 수 있다. 가장 바깥쪽은 중간 노드이고, 2번째, 3번째는 경로를 계산할 대상 노드이다. 각 반복문은 그래프의 노드 개수만큼 수행되므로, 노드 개수 n에 대하여 시간복잡도는 O(n^3)이다. Java int INF = 무한, 알고리즘 구현 상 도출될 수 없는 큰 값으로 선언함. int [] [] adj; int [] [] dist; ... void fl..

개요 특정 노드에서 다른 모든 노드 간 최단 경로를 계산하는 알고리즘이다. 벨만-포드 알고리즘보다 효율적이다. 가중치에 음수가 없는 그래프에서만 사용할 수 있다. 벨만 포드처럼 각 노드까지의 거리를 INF로 초기화하고 탐색과정에서 값을 줄인다. 알고리즘의 각 단계에서는 아직 처리하지 않은 노드 중 거리가 가장 작은 노드를 먼저 선택하고, 해당 노드에서 시작하는 모든 간선을 보며 다른 노드까지의 거리를 줄일 수 있다면 줄인다. 음수 가중치가 없다고 전제하여 모든 간선을 단 한 번만 처리한다. 그래서 매우 효율적이다. 각 노드를 처리한 뒤에는 해당 노드까지의 거리가 절대 변하지 않는다. 음수 간선이 존재하면 사용할 수 없다. 구현 효율적인 구현을 위해서는 아직 처리하지 않은 노드 중 거리가 가장 짧은 노드를..

개요 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘이다. 길이가 '음수인 사이클'을 포함하지 않는 모든 그래프에서 최단 경로를 구할 수 있다. 음수인 사이클이 그래프에 존재하는지 파악할 수 있다. 구현 각 노드의 초깃값을 설정한다. 시작 노드는 0, 다른 모든 노드는 INF(무한대)이다. n-1번의 라운드를 돌며 매 라운드마다 모든 노드에 걸쳐 경로를 최소화한다. 라운드를 n회 돌아서 n회째에서도 경로 단축이 이뤄지면 음수 사이클이 존재한다고 판단한다. 해당 경로가 음수 사이클을 형성하고, 시작 노드가 INF이면 불가능한 경로의 계산이 진행되므로 주의해서 처리한다. n-1회의 라운드 동안 매회 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다. Java int INF = ..