신장 트리 (Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다. Kruskal 알고리즘 1. 최초, 모든 간선을 가중치 순으로 오름차순 정렬 1-1. 간선 리스트를 만든다. 1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다. 2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기..
LinkedList LinkedList는 리스트의 한 종류이다. 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만 노드가 다음 노드로 갈 수 있는 포인터를 가짐으로써 노드들이 논리적으로 연속되어 있다. 연결 리스트에서 하나의 원소를 노드라고 한다. 노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드는 리스트에 저장될 원소의 값을 저장하며 링크 필드는 다음 노드의 참조값을 저장한다. 연결리스트의 가장 큰 장점은 원소의 삽입, 삭제의 시간복잡도가 O(1)이다. 때문에 원소의 삽입, 삭제가 빈번하면 연결 리스트 사용을 고려할만하다. 단점은 특정 위치의 원소를 찾아가는 시간 복잡도가 O(N)이다. 배열(배열 기반 리스트)와 달리 랜덤 엑세스가 안되기 때문이다. 연결 리스트의 종류 연결 리스트는 총 세..
List 리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다. 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다. 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다. 또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다. 배열 기반 리스트 배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다..
브루트포스 문제를 풀 때 순열, 조합 등으로 원소 인덱스를 뽑는 과정이 필요하다. 그러면 인덱스가 이차원(x,y)일 경우 어떻게 선택할 수 있을까? 아래의 방법으로 쉽게 선택할 수 있다. 1. 4X3의 배열일경우 (0,0)은 0으로 (3,4)는 11로 표현할 수 있다. 즉 이차원 인덱스(x,y)를 하나의 정수로 표현할 수 있다. 이 정수로부터 컬럼 크기로 나눈 값이 row, 컬럼 크기로 나머지 연산을 한 값이 col이 된다. 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net import java.util.*; im..
인터페이스 인터페이스의 모든 메서드는 public abstract 메서드이다. (public abstract는 생략 가능) 인터페이스의 모든 멤버 변수는 public static abstract 멤버 변수이다. (public static abstract는 생략 가능) 생략한 제한자는 컴파일러가 자동으로 추가함 default method JDK 1.8부터 인터페이스에 구현부가 있는 default method 또는 static method를 넣어 줄 수 있다. 왜 default method가 추가되었을까? 기존의 인터페이스에 기능의 확장을 위해 메서드를 추가할 때가 있다. 이때 abstract 메서드로 추가한다면 해당 인터페이스를 구현한 모든 구현체에서 추가한 abstract 메서드를 반드시 구현해야 된다는..
enum (열거형) 열거형이란 상수를 정의한 타입이다. 예를 들어 계절이라는 열거형 타입은 SPRING, SUMMER, FALL, WINTER라는 4개의 상수와 그 상수에 해당하는 값을 정의한다. 계절 외에도 성별, 트럼프 카드, 결제 수단 등 제한된 범위의 상수를 표현할 데이터 타입을 찾고 있다면 enum을 사용하도록 하자. 열거형의 장점으로 다음 2가지가 있다. 상수의 의미가 바로 와닿는다. 코드 상의 Gender.MALE, Gender.FEMALE이라는 상수는 각각 성별의 남자와 여자를 나타낸다는 것을 쉽게 알 수 있다. 상수 값을 쉽게 바꿀 수 있다. 열거형의 정의만 바꿔주면 되어 코드는 변하지 않는다. enum 정의와 사용 아래는 열거형을 정의하는 기본 코드다. enum Direction { E..
자바의 에러 프로그램 실행 중 어떤 원인으로 프로그램이 오작동하거나 비정상적으로 종료되는 경우가 있다. 이러한 결과를 초래하는 원인을 에러 또는 오류라고 한다. 에러의 종류는 두 가지로 나눌 수 있다. 컴파일 에러 : 컴파일 시 발생하는 에러. (잘못된 구문, 오타, 자료형 문제 등) 런타임 에러 : 실행 시 발생할 수 있는 에러. 예외 계층 자바의 런타임 에러. 즉 예외의 계층은 아래와 같다. Object : 모든 객체의 부모는 Object이다. 예외도 객체이므로 Object를 상속한다. Throwable : 최상위 예외이다. Error, Exception : 자바는 예외를 크게 Error와 Exception 객체로 구분한다. Error 타입 예외가 발생하면 매우 심각한 오류이므로 프로그램의 비정상 종..
트랜잭션 도입 시 문제점 애플리케이션 구조에는 여러 가지가 있지만 가장 단순하고 많이 사용되는 방법은 아래와 같이 3개의 계층으로 나누는 것이다. 프레젠테이션 계층 : UI 관련 처리 담당, UI 관련 기술에 종속적 서비스 계층 : 비즈니스 로직 담당, 특정 기술에 종속적이지 않고 가급적 자바 순수 코드로 작성 데이터 접근 계층 : DB 접근 담당, DB 기술에 종속적 이렇게 3개의 계층으로 나누는 이유는 애플리케이션에서 가장 중요한, 핵심 비즈니스 로직을 담고 있는 서비스 계층이 특정 기술에 종속되지 않도록, 순수 자바 코드로 구성된 비즈니스 로직만 들어가도록 하기 위함이다. 이럼으로써 시간이 지나 기술이 변해도 서비스 계층은 변경 없이 유지될 수 있으며 순수 비즈니스 로직만 있기에 유지보수도 쉬워지고..
