S E P H ' S

MST(Minimum Spanning Tree) 최소 신장 트리 그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘 간선 중심으로 최소 신장 트리를 구하는 알고리즘. 간선이 적을때 프림 알고리즘보다 유리하다. 내부적으로 union-find 알고리즘을 사용 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다. 모든 간선에 대해 반복한다. 프림 알고리즘 정점 중심으로 최소 신장 트리를 구하는 알고리즘 정점이 적을때 크루스칼 알고리즘보다 유리 임의의 정점 선택 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택..

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다. 예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 ..

자바 프로그램의 실행 C나 다른 언어의 실행 방식과 Java 실행 방식을 비교한 간단한 그림이다. JDK가 운영체제에 맞게 존재하고 그 안에 자바 컴파일러(javac.exe)가 자바 코드를 해석하면 바이트 코드(.class 형태의 파일)가 되고 그를 JRE이 지니고 있는 자바 프로그램 실행기(java.exe)를 포함하고 있고 JVM이 중재자로서 각 플랫폼에서 프로그램을 구동하는 데 문제 없게끔 만들어준다. 자바 프로그램의 메모리 사용 방식 프로그램이 실행될때 메모리는 보통 다음과 같이 영역이 나눠서 사용된다. 자바와 같이 객체 지향 프로그램에서는 데이터 저장 영역을 다시 세 개의 영역으로 분할해서 사용한다. 위의 그림을 다시 더 상세한 설명을 덧붙인다면 스태틱 영역은 클래스가 위치하고 스택 영역은 메소드..