Coding Diary

1. 개념 그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다. 2. 특징 음수 가중치 에지가 있어도 수행할 수 있다 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다 시간 복잡도가 O(VE)이다. V는 노드수, E는 에지수. 에지 리스트를 사용하는 것이 간단하다. 3. 원리 에지 리스트를 만든다 최단 거리 배열을 만든다 출발 노드는 0으로 설정하고, 이외의 노드는 적당히 큰 값으로 설정한다. 에지 리스트를 순회하면서 [출발 노드로부터 해당 에지의 출발..

1. 개념 그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다. 2. 특징 간선의 가중치가 양수다. 시간 복잡도가 O(에지수log노드수) 이다. 우선순위 큐를 사용하여 시간복잡도를 시간 복잡도를 줄인다 우선순위 큐를 사용하면 현재 위치로부터 최소 비용으로 갈 수 있는 다음 노드를 먼저 탐색하여서 불필요한 경로를 탐색하지 않아도 된다. 즉, 모든 노드를 탐색해보지 않아도 된다. 인접 리스트를 사용하는 것이 간단하다. 3. 원리 인접 리스트를 만든다 최단 거리 배열..

1. 개념 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 이렇게 구한 노드 순서는 해당 순서의 노드가 처리되기 위해서는 그 노드보다 앞에 있는 노드가 처리되어야 함을 의미한다. 즉, 반약 위상 정렬의 결과가 1 2 3 4 5 일 때, 2가 처리되기 위해서는 무조건 1이 처리되어야 하는 것이고, 5가 처리되기 위해서는 무조건 1234가 처리 되어 있어야 하는 것이다. 2. 특징 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드 수 + 에지 수) 이다. 3. 원리 진입 차수를 이용한다 진입 차수는 자기 자신을 가리키는 에지의 개수를 의미한다. 진입 차수가 0이라는 것은 해당 노드는 아무 것에도 의지하지 않는다는 것을 의미한다. 그래서 진입 차수가 0인 것을 먼저 정렬한다. -- 1..

스프링에는 Service 계층이 있다. 이러한 Service 계층을 구현할 때는 그냥 기능별 Service 클래스를 만들어 구현을 하는 방법이 있고, 기능별로 ServiceInterface를 만들고 해당 Interface를 구현하는 ServiceImpl을 구현하는 방법이 있다. 이 두 방법에 대해 살펴보고 나의 프로젝트에 맞는 방법에 대해 고찰해보고자 한다. 1. ServiceImpl을 사용하는 방법 1) 개념 Service 별로 interface를 만들고, 해당 interface를 구현한 실제 serviceImpl를 만든다. BoardServiceInterface를 만들어서 create라는 메서드를 명시하고 BoardServiceImpl을 만들어서 create 메서드를 실제로 구현하는 것. 2) 장점 ..

1. 개념 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과, 특정 원소가 속한 집합의 대표 원소를 반환하는 find 연산. 2. 연산 1) union 원소 a가 집합 A에 속해있고, 원소 b가 집합 B에 속해 있을 때 a와 b를 union한다는 것은 A와 B의 합집합을 구하는 것과 같다. 2) find 집합 A에는 다양한 원소들이 있고, 그 중에 a도 있다. find(a)는 a가 속한 집합에 있는 다양한 원소 중 대표 원소를 구하는 연산이다. 3. 원리 1차원 배열을 선언한다. 그 배열의 인덱스는 원소를 의미하고, 인덱스에 있는 값은 해당 원소가 속한 집합을 의미한다. 1) find 1 2 3 4 5 6 1 2 3 4 5 6 find(1)은 1이 속한 집합의 대표 ..

1. 개념 어떤 그래프에 있는 노드를 두 집합으로 나눴을 때, 같은 집합 내의 노드끼리는 간선으로 연결되어 있지 않고, 다른 집합의 노드끼리는 간선으로 연결되어 있는 그래프. 이분그래프가 되려면 서로 다른 그룹의 노드끼리는 모두 연결이 가능해야한다. 2. 이분 그래프 판별 BFS나 DFS로 탐색하면서 정점을 방문할 때, 그 정점에 특정 색을 칠한다. 위에서 방문한 정점과 인접한 정점을 방문할 때는 위에서 칠한 색과 다른 색을 칠한다. 특정 정점을 방문해서 색을 칠한 후 그 정점과 인접한 정점의 색을 보는데 색이 같다는 것이 드러나면 이분 그래프가 아니다. 3. 코드 public static void dfs(int nodeIndex){ visited[nodeIndex] = true; for(int n : ..

1. 개념 정점(노드)과 간선(에지)으로 이루어진 자료구조. 정점은 고유한 식별자를 가지고 있고, 간선은 정점들끼리의 관계를 나타낸다. 2. 종류 1) 방향 그래프 간선에 방향성이 있는 그래프를 의미한다. A에서 출발해서 B로 가는 간선이 존재한다면 이는 A에서 B로 가는 방향을 가진 간선이고, 이러한 정점과 간선을 모아 놓으면 방향 그래프이다. A에서 B로는 갈 수 있지만, B에서 A로 가는 길은 없다. 2) 무방향 그래프 간선에 방향이 없다. A에서 B가 연결되어 있으면 출발과 도착이 없고 그냥 둘이 연결 된 거다. A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다. 3) 가중치 그래프 A와 B가 연결이 되어 있는데 그 연결된 간선에 가중치가 부여된 것이다. 이러한 가중치는 두 정점 사이의 거리,..

1. 서론 어떤 클래스를 만들고 해당 클래스를 사용해서 속성 값을 가지고 있는 인스턴스를 만드려고 할 때 흔히 사용하는 방식에는 생성자를 사용하는 방식, setter로 속성 값을 설정해서 생성하는 방식, builder를 사용하는 방식이 있다. 예전에 get과 set 메서드만 알고 있을 때는 set으로 값을 설정하는 방법을 사용했는데 @builder 어노테이션이 있다는 것을 알게 되고 난 후, 각 방식에 대해 궁금해졌다. 각 방식의 특징은 무엇이고 어떤 방법이 이번 내 프로젝트에 적당할까? 2. 각 방식에 대해 알아보기 1) 생성자 사용 ① 사용 방법 public class Car { private int price; private String owner; public Car(int price, Strin..

1. 에지 리스트 1) 개념 에지 리스트는 에지를 중심으로 그래프를 표현한다. 2차원 배열에 각 에지의 출발 노드와 도착 노드를 저장한다. 만약 가중치가 있는 에지일 경우 각 에지의 출발 노드, 도착 노드, 가중치를 저장한다. 2) 종류 ⓛ 가중치가 없는 에지 int[2][6] edgeList = {{1,2},{1,3},{2,5},{2,4},{3,4},{4,5}}; ② 가중치가 있는 에지 int[2][6] edgeList = {{1,2,4},{1,3,1},{2,5,2},{2,4,1},{3,4,7},{4,5,4}}; + 만약 방향이 없는 에지면 {1,2}와 {2,1}은 같은 것이니 둘 중 하나만 저장하면 된다. 3) 특징 구현하기가 쉽다 에지만 딱 나와있기 때문에 특정 노드가 어떤 에지와 연결되어 있는지,..

1. 개념 방정식의 해를 구하기 위해 사용하는 알고리즘이다. 2. 원리 ax+by=c(a,b,c,x,y는 정수) 와 같은 방정식이 있을 때, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. ax+by=c가 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)이다. 3. 방법 5x + 9y = 2 일때, 이 식을 만족하는 정수 x와 y를 찾아보자. 식이 정수해를 갖게 하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 식을 다시 놓는다. 5x + 9y = 1 5와 9로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 되면 반복을 중단한다. 유클리드 호제법 실행 나머지 몫 5%9 5 0 9%5 4 1 5%4 1 1 4%1 0 4 위에서 구한 나머지와 몫을 이용하여 x와 ..