최단 경로 알고리즘 최단 경로 알고리즘이란 가중 그래프 상의 두 정점을 연결하는 가장 짧은 경로를 찾는 방법입니다. 이러한 최단 경로 알고리즘은 지도로 최단 경로를 찾거나 , 네트워크 구축 시 비용을 최소화하는 데 사용되곤 합니다. 다양한 사용처가 있는 만큼 알아두면 좋은 알고리즘입니다. 최단 경로 알고리즘 종류 📌 다익스트라 (Dijkstra) 에츠허르 다익스트라가 고안한 유명한 알고리즘입니다. 다익스트라 알고리즘은 그래프의 방향 유무와 상관없이 하나의 정점으로부터 다른 모든 정점으로의 최단 경로를 구할 수 있습니다. 다만, 간선에 음의 가중치가 존재하면 사용할 수 없기 때문에 음의 가중치를 이용해야 한다면 다익스트라 외의 다른 알고리즘을 사용하면 됩니다. 🔨 구현 그리디와 DP가 혼합된 형태이며, 인..

💡 이 게시글에선 기본 정렬 알고리즘에 대해 다룰 것 입니다. 시간 복잡도 O(n²) 정렬 시간이 정렬할 자료의 제곱에 비례해서 늘어납니다. 이러한 이유로 잘 사용되지 않는 정렬 방식들 입니다. 버블 정렬 (Bubble Sort) 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 반복하는 방식으로 두 개의 인접한 요소를 비교하며 정렬하는 것을 버블 정렬이라고 합니다. 쉽게 구현할 수 있지만 시간복잡도가 O(N^2)이기 때문에 잘 사용되지 않습니다. 동일 값에 대한 원래 순서를 보장하는 안정(Stable) 정렬입니다. public class Bubble { public static void sort(int[] arr) { for (i..

💡 JdbcTemplate은 엄밀히 말하자면 Spring Data가 아닌 Spring에서 제공되고 있습니다. 그러나, 이를 기반으로 더욱 편리하게 사용하도록 만든 것이 Spring Data JDBC이므로 이 항목에서 JdbcTemplate을 이야기하도록 하겠습니다. JDBC JDBC란 Java Database Connectivity의 약어로, 자바와 데이터베이스를 연결해 주는 자바 API입니다. JDBC가 나오기 이전에는 데이터베이스 벤더(Oracle, MySQL 등) 별로 문법이 상이하여 사용하던 데이터베이스를 다른 벤더로 바꾸는 경우, 코드로 작성한 SQL 문을 벤더 문법에 맞게 하나하나 수정해주어야 하는 불편함이 있었습니다. 이러한 프로그램이 데이터베이스에 의존하는 문제를 해결하고자 탄생한 것이 J..

Spring Data Spring Data는 데이터베이스의 특수성을 그대로 유지하면서 데이터 접근를 위한 Spring 기반 프로그래밍 모델을 제공하는 프로젝트 입니다. 스프링 프레임워크 사용자가 데이터 액세스 기술, 관계형 및 비관계형 데이터베이스, map-reduce 프레임워크, 클라우드 기반 데이터 서비스를 쉽게 사용할 수 있도록 도와줍니다. 특징 Spring Data는 다음과 같은 특징을 가지고 있습니다. 강력한 repository 및 custom obeject-mapping 추상화 repository method name으로 동적 쿼리 만들기 기본 속성을 제공하는 Implementation domain 기본 클래스 생성되거나 마지막 변경이 언제인지 알 수 있는 투명한 auditing 지원 cust..

우선순위 큐 (Priority Queue) 일반적인 큐의 방식(First In, First Out)과 다르게, 데이터에 우선순위를 부여하고 우선순위가 높은 데이터가 먼저 나오는 자료형을 우선순위 큐라고 합니다. 우선순위 큐 구현 우선 순위 큐는 배열, 연결 리스트, 힙을 통해 구현할 수 있습니다. 자료구조별 시간복잡도는 다음과 같습니다. enqueue 연산 dequeue 연산 정렬된 배열 O(N) O(1) 정렬된 연결 리스트 O(N) O(1) 힙 O(logN) O(logN) 일반적으로 시간복잡도 때문에 우선순위 큐는 힙으로 구현하는 편입니다. 프로그래밍 언어로 구현 Java 자바에선 기본적으로 제공하고 있습니다. PriorityQueue pq = new PriorityQueue();

힙 (Heap) 힙(Heap)이란 여러 개의 값 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내는 완전 이진트리를 의미합니다. 이러한 형태의 완전 이진트리 자료구조에 Heap이라는 이름이 붙은 이유는 해당 단어가 차곡차곡 쌓아 올린 것을 의미하는데, 자료구조의 형태와 흡사하기 때문에 붙여진 이름입니다. 힙 특징 힙의 특징은 다음과 같습니다. 항상 완전 이진 트리 상태를 유지 중복 값을 허용 반 정렬 상태 (모든 노드들이 힙 종류에 따라 자식 노드보단 크거나 작지만, 형제 노드 간의 우선순위는 보장하지 못하는 상태) 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 작음 힙 종류 최소 힙 (Min Heap) 부모의 값이 항상 자식들의 값보다 작거나 같은 힙을 최소 힙이라 합니다. 최대 힙 (Max He..

Union-Find (합집합 찾기) 유니온 파인드는 여러 노드가 있을 때 특정한 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘입니다. Disjoint-Set 알고리즘이라고도 불리며, 크루스칼 알고리즘에서 해당 간선이 사이클을 형성하는지 체크하는 데 사용됩니다. 🎈 연산 종류 유니언 파인드는 위에서 언급했듯이 이름 그대로 union 과 find 연산으로 이루어져 있습니다. union 연산은 각 노드가 속한 집합을 1개로 합치는 연산으로, 노드 a,b가 a ∈ A , b ∈ B일 때 union(a,b) = A∪B 를 의미합니다. find 연산은 특정 노드 a에 관해 a가 속한 집합의 대표 노드(최상위 부모)를 반환..

신장 트리 (Spanning Tree) 신장 트리란 그래프에서 모든 정점이 최소한으로 연결되어 있는 그래프를 의미합니다. 신장 트리 특징 신장 트리의 특징은 다음과 같습니다. 하나의 그래프에 여러 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있으며, 사이클이 존재하지 않는다. n개의 정점을 가진 신장 트리는 n-1개의 간선을 가지고 있다. 최소 비용 신장 트리 (MST) 최소 비용 신장 트리(Minimum Spanning Tree)란 신장 트리 중에 사용된 간선들의 가중치 합이 가장 작은 트리를 의미합니다. 쉽게 말해, 모든 노드들을 가장 적은 비용으로 연결시킨 그래프라고 생각하면 됩니다. 두 가지의 그리디 알고리즘으로 최소 비용 신장 트리를 구할 수 있습니다. 크루스칼 알고리즘 (Kruskal..

💡 Real MySQL 8.0을 정리한 글입니다. 버전별로 상이할 수 있으니 정확한 내용은 공식 메뉴얼을 확인해주세요. 1. 사용자 식별 MySQL은 사용자의 계정 뿐만 아니라 클라이언트가 실행된 호스트명이나 IP 주소 같은 사용자의 접속 지점까지 계정의 일부로 식별합니다. 그러므도 계정을 언급할 때는 다음과 같이 항상 아이디와 호스트를 함께 명시해야합니다. -- ` 나 ' 로 아이디와 호스트를 감쌉니다. 'dokuny' @ '127.0.0.1' 위의 예시는 127.0.0.1의 주소에서 dokuny 아이디로 접속할 때만 사용가능한 계정입니다. 다른 주소에서 해당 아이디로 접속할 수 없습니다. 모든 주소에서 접속이 가능한 사용자 계정을 생성하고 싶다면 아래와 같이 호스트 부분을 '%'로 변경해주면 됩니다...

배낭 문제 (Knapsack Problem) 알고리즘 문제 중에 다음과 같은 문제들이 나올 때가 있습니다. 어떤 가방에 담을 수 있는 무게가 한정되어있을 경우, 가방에 담을 수 있는 아이템들의 가치의 최대 합은? 최대로 담을 수 있는 무게가 주어진 배낭과 무게와 가치를 지닌 물건들이 각각 한 개씩 주어졌을 때, 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제를 배낭 문제라고 합니다. 이런 문제는 다음과 같은 유형으로 나눠집니다. 분할 가능한 배낭 문제 (Fractional Knapsack Problem) 분할 가능한 배낭 문제는 주어진 아이템들을 분할해서 배낭에 담을 수 있는 문제들을 뜻합니다. 분할이 가능하다면, 무게당 가치를 계산해서 배낭에 넣으면 되는데, 이는 그리디 알고리즘으로 풀 수 있습니다...

최장 증가 부분 수열 최장 증가 부분 수열(Longest Increasing Subsequence)이란 어떤 수열이 주어졌을 때, 해당 수열의 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미합니다. 예를 들어 다음과 같은 수열이 주어졌다고 가정해봅시다. 3, 1, 4, 5, 9, 2, 6, 5, 3, 5 그럼 해당 수열에서 수많은 부분 수열이 나올 수 있습니다. (3) (1) (4) .... (3,1) (3, 4) ... (3,1,4) (3,1,5) ... 이러한 부분 수열 중에 오름차순으로 정렬된 가장 긴 수열(LIS)은 다음과 같습니다. (1, 4, 5, 9) (1, 4, 5, 6) (1, 2, 3, 5) (3, 4, 5, 9) (3, 4, 5, 6) 최장 증가 부분 수열 길이 구하기 보통 알..

그래프 (Graph) 그래프는 정점(Vertex)와 간선(Edge)로 이루어진 순환(Cycle) 형태의 자료구조입니다. 트리도 노드와 간선으로 이루어져있는 일종의 그래프이며, 그래프와 트리의 차이점은 순환(Cycle)이 있느냐 없느냐의 차이입니다. 이 글에서는 정점과 노드를 같은 뜻으로 사용하도록 하겠습니다. 그래프의 구조 정점 (Vertext) : 각각의 노드들 간선 (Edge) : 노드와 노드를 연결하는 선 인접 정점 (Adjacent Vertext) : 간선 하나를 두고 바로 연결된 정점 정점의 차수 (Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-degree) : 방향 그래프에서 ..