주어진 단어들을 가지고 DAG를 만들어 위상 정렬 하는 문제이다. 임의의 알파벳 a, b에 대해서 a가 b보다 사전 순으로 앞선다면 a에서 b로 가는 간선이 존재하도록 DAG를 만든다. DFS()가 종료될때마다 리스트에 정점을 넣고 모든 DFS가 끝난 후 리스트를 역순으로 정렬하면 위상 정렬 결과를 얻을 수 있다. DAG에 사이클이 존재한다면 모순이 발생한다. 사이클 발생 여부를 직접 체크할수도 있지만 어차피 위상 정렬을 해야 되기에 간단하게 위상 정렬 후 결과에서 오른쪽에서 왼쪽으로 가는 간선이 있다면 DAG에 사이클이 존재한다는 걸 알 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(Strin..
컴퓨터 컴퓨터는 정보(information)를 처리하는 기계라고 한다. 정보는 뭘까? 정보의 최소 단위는 두 가지 상태(0, 1)을 나타내는 bit이다. 이 bit가 모인 이진 데이터가 정보이다. 그렇다면 정보를 어떻게 처리할까? 정보를 처리는 비트의 상태 변환(0에서 1로, 1에서 0으로)과 같다. 정보를 처리하려면 비트의 상태 변환을 할 수 있는 물리적인 장치가 필요하고 이 장치가 논리 회로가 된다. 논리 회로 논리 게이트는 불 대수를(Boolean algebra) 구현한 물리적인 장치다. NOT, AND, OR, XOR, NAND, NOR 게이트가 있다. 불 대수는 수의 범위가 오직 0 또는 1인 수의 논리적 계산을 수학적으로 표현한 것이다. 현대 수학의 수가 실수와 허수로 이루어져 매우 복잡하다면..
DFS 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘을 그래프의 탐색 알고리즘이라 한다. 대표적인 알고리즘으로 DFS(depth-first search)와 BFS(breadth-first search)가 있다. DFS는 그래프를 더 나아갈 길이 없을 때까지 깊이 들어가 탐색하며 더 나아갈 수 없다면 되돌아가는 방식이다. 즉 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가고 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 아래는 인접 행렬을 탐색하는 DFS 코드이다. static void DFS(int v, int[][] graph, boolean visit[]) { Syste..
그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는 자료 구조, 즉 정점(vertext)의 집합 V와 간선(edge)의 집합 E로 구성된 자료 구조이다. 도로망, 네트워크 망 부터 먹이 사슬, 사람들 간의 짝사랑 관계, 하루 동안의 도시 간 인구 이동 관계 등을 그래프로 표현할 수 있다. 그래프의 종류 그래프가 가지는 특징과 형태에 따라 여러 종류로 나눌 수 있다. 방향 그래프 (directed graph) : 각 간선이 방향을 가지는 그래프, 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다. 무향 그래프 (undirected graph) : 각 간선이 방향을 가지고 있지 않은 그래프 가중치 그래프 (weighted graph) : 각 ..
ClassLoader 자바 소스 코드가 컴파일된 클래스 파일(.class)은 JVM에 탑재 되어 실행되면서 자바 프로그램이 실행된다. 그러면 어떻게 클래스 파일을 JVM에 탑재시킬까? 자바의 기본적인 클래스 파일은 $JAVA_HOME 내부 경로에 있으며 자신이 만든, 또는 다른 사람이 만든 클래스 파일은 여러 디렉터리에 흩어져 있다. 흩어져 있는 클래스 파일을 찾아 JVM에 탑재(load) 시키는 역할을 하는 것이 ClassLoader이다. ClassLoader는 크게 Loading, Linking, Initialization 3가지 단계로 클래스 파일을 JVM에 탑재한다. Loading은 클래스 파일을 JVM에 탑재하는 과정, Linking은 클래스 파일을 검증하고 기본 값으로 초기화하는 과정, Ini..
분할 정복 문제를 더 이상 나눌 수 없을 때까지 나누고 (분할), 나누어진 부분 문제를 품으로써 (정복) 전체 문제의 답을 얻는 방식의 알고리즘 패러다임. 이진 탐색, 퀵 정렬 등이 대표적인 알고리즘이다. [동작 방식] 분할 : 문제를 더 이상 나눌 수 없을 때까지 2개 이상의 부분 문제로 나눈다. 나눠진 문제들은 서로 독립적이다. 정복 : 부분 문제를 푼다. 결합 : 정복된 답을 취합한다.
병행 제어 DBMS는 여러 사용자가 동시에 데이터베이스를 이용할 수 있도록 병행 수행 기능을 제공한다. 병행 수행은 실제로 여러 트랜잭션이 차례로 번갈아 수행되는 인터리빙(interleaving) 방식으로 지원한다. 하지만 아무런 제어 없이 병행 수행을 할 경우 갱신 분실, 모순성, 연쇄 복귀 등의 문제가 발생할 수 있다. 때문에 트랜잭션을 병행 수행 하면서도 정확한 수행 결과를 얻을 수 있도록 트랜잭션의 병행 수행을 제어하는 병행 제어(동시성 제어)가 필요하다. 병행 제어 기법 병행 제어의 핵심 목표는 트랜잭션을 번갈아 가면서 수행하면서도 트랜잭션을 순차적으로 실행하는 것과 같은 결과를 내는 것이다. 트랜잭션을 순차적으로 실행한 결과는 항상 정확하고 일관되기 때문이다. 가장 많이 사용하는 병행 제어 기..
이미 비슷한 문제를 푼 적이 있다. LIS 문제를 풀어보았다. 비슷한 형태의 문제들은 비슷한 부분 문제 정의를 사용해 풀 수 있는 경우가 많다. 기존 LIS를 푸는 문제 f는 다음과 같았다. f(start_idx) : start_idx 위치의 수에서 시작하는 LIS 개수 리턴 합친 LIS를 푸는 문제 f의 정의를 다음과 같이 정의한다. f(indexA, indexB) : indexA와 indexB 위치의 수에서 시작하는 합친 LIS 개수 리턴 indexA와 indexB위치의 수에서 시작하므로 다음에 오는 수는 indexA, indexB 위치의 수들보다 더 커야한다. 따라서 아래의 점화식이 만족한다. nextA는 다음에 올 수 있는 A의 수들의 인덱스이며 nextB도 다음에 올 수 있는 B의 수들의 인덱스..
