데브카이브 데브카이브

서론최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘에 대해 알아보고 관련된 백준 1197 문제를 풀어보자.최소 신장 트리에대한 설명은 아래 글을 참고하자.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 크루스칼 알고리즘최소 신장 트리(이하 MST)를 구하는 크루스칼 알고리즘은 다음과 같은 순서를 가진다.간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다현재 선택한 간선이 정점 U,V를 연결하는 간선이라고 할 때, 만약 U..

Mutable 과 Immutable Java에는 가변(mutable)객체와 불변(immutable)객체가 존재한다. 가변 객체는 힙 영역에 생성된 객체를 변경할 수 있는 객체이고 불변 객체는 반대로 힙 영역에 생성된 객체를 변경할 수 없는 객체이다. 대표적인 불변 객체인 String 으로 예시를 보면 다음과 같다. String val1 = "abc"; System.out.println("val1 initial " + System.identityHashCode(val1)); val1 += "xyz"; System.out.println("val1 after "+System.identityHashCode(val1)); // output val1 initial 1435804085 val1 after 179828..

일급함수 프로그래밍 언어는 해당 언어의 함수들이 다른 변수처럼 다루어질 때 일급 함수를 가진다고 합니다. 예를 들어, 일급 함수를 가진 언어에서 함수는 다른 함수들에 전달인자로 제공되고, 다른 함수에 의해 반환될 수 있으며, 변수에 값으로서 할당될 수 있습니다. 일급 객체가 되기위한 충족 조건은 세가지가 있다. 변수나 데이터에 할당 할 수 있어야 한다. 객체의 인자로 넘길 수 있어야 한다. 객체의 리턴값으로 리턴 할 수 있어야 한다. Java 에서는 위의 조건을 충족하지 않지만, 람다식을 이용하여 함수의 매개변수로 전달 할 수 있다. 함수형 인터페이와 람다 구현해야 할 abstract method를 하나만 갖고 있는 인터페이스를 함수형 인터페이스라고 한다. @FunctionalInterface 어노테이션..

Java 의 Generic Java에는 Generic이라는 이라는 기능이 있다. Generic 이라는 기능은 JDK 1.5 부터 도입된 기능인데 이전 자바 버전의 코드와의 호환성은 어떤식으로 유지하는걸까? 이를 위해 Type Erasure라는 기능으로 컴파일 시에는 Generic type을 제거하게 된다. 이와 관련하여 간단하게 확인해 보자. Reifiable 과 Non-Reifiable Refiable Type (구체화 타입) 타입 정보를 런타임시에 알고 구체화 하는것. 컴파일 단계에서 Type Erasure에 의해 지워지지 않는다. 일반적인 타입과 unbound wildecard type 등이 포함된다. Non-Reifiable Type (비구체화 타입) 타입 정보가 런타임때 사라지는것. 컴파일 단계..

JVM Architecture Class Loader JVM 내로 .class 파일들을 Load 하여 Loading된 클래스들을 Runtime Data Area에 배치한다. JVM Memory Runtime Data Area 라고도 하며 JVM이 OS에서 할당 받은 메모리 공간이다 Execution Engine Runtime Data Area에 할당됭 ByteCode 를 실행하는 역할을 한다. Interpreter, JIT compiler, Garbage Collector 로 구성되어있다. Native Method Libraries 실행에 필요한 C,C++로 이루어진 Native Libraries 이다. Native Method Interface (JNI) JVM이 Native Method Librari..

Singleton 패턴 생성자가 여러 차례 호출되더라도 실제로 생성되는 객체는 하나이고 최초 생성 이후에 호출된 생성자는 최초의 생성자가 생성한 객체를 리턴한다. 기본적인 Singleton 패턴 public class Singleton { private static Singleton instance; private Singleton(){} public static Singleton getInstance(){ if(instance == null){ instance = new Singleton(); } return instance; } } Singleton의 getInstance를 호출할때 instance가 없다면 만들어주고 있다면 만들어둔 instance를 return 해준다. 이 코드는 스레드가 여러개일..

격리 수준에따라 발생할 수 있는 문제점 Dirty Read 특정 트랜잭션이 데이터를 변경하고 아직 COMMIT 하지 않은 상태에서 다른 트랜잭셔인 변경 내용을 조회할 수 있는 문제 Non-Repeatable Read 같은 트랜잭션 내에서 같은 데이터를 반복적으로 조회했을 때 읽어온 데이터가 다른 문제 Phantom Read Non-Repeatable Read의 한 종류로 조회해온 결과의 행이 새로 생기거나 없어지는 문제 Transaction Isolation Level 트랜잭션 격리수준은 동시에 여러 트랜잭션이 진행될 때 현재 트랜잭션의 작업을 다른 트랜잭션에게 어떻게 적용 시킬지를 결정한다. 트랜잭션 격리 수준은 아래와같이 크게 4개로 나뉜다. 아래로 갈 수록 트랜잭션간 고립 정도가 높아지며, 성능이 ..

위상 정렬 알고리즘 위상 정렬(Topology Sort)은 순서가 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 위상 정렬을 하기 위해서는 사이클이 없는 방향 그래프 DAG(Directed Acyclic Graph)이여야 한다. 위상정렬은 큐와 각 노드의 진입차수(Indegree)를 이용하여 구현할 수 있다. 1. 각 Node 별로 Indegree를 구해준다. 2. Indegree가 0인 Node를 Queue에 넣어준다. 3. Queue에서 Node를 가져와 해당 Node에서 방문 가능한 Node의 Indegree를 감소시킨다. 4. 감소된 Node의 Indegree가 0 이라면 Queue에 넣어준다. 5. Queue가 빌때까지 3,4 작업을 반복한다. 위와같은 순서로 동작한다면 Queue..