bfs
- 목적: 큐사용해서 구현해보기
public static void BFS(int start){
Queue<Integer> q = new LinkedList<>();
q.add(start);
isVisited[start] = true;
while(!q.isEmpty()){
int x = q.poll();//이위치
start = x;//이위치
for(int i=1;i<arr.length;i++){
if(!isVisited[i]&&arr[start][i]) {
isVisited[i] = true;
q.add(i);
}
}
System.out.print(x + " ");
}
System.out.println();
}dfs
- stack사용해서 구현해보기
public static void dfs(int v){
// 현재 노드 방문 처리
visited[v] = true;
// 방문 노드 출력
System.out.print(v + "");
// 인접 노드 탐색
for (int i : graph[v]){
// 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
if (visited[i]==false){
dfs(i);
}
}
}정렬
- 퀵정렬, 계수정렬 구현법 알아와오기
- 퀵정렬
private static void quickSort(int[] arr, int start, int end) {
// start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
if (start >= end)
return;
// 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
int pivot = start;
int lo = start + 1;
int hi = end;
// lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
// 서로 엇갈리게 될 경우 while문 종료
while (lo <= hi) {
while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
lo++;
while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
hi--;
if (lo > hi) // 엇갈리면 피벗과 교체
swap(arr, hi, pivot);
else
swap(arr, lo, hi); // 엇갈리지 않으면 lo, hi 값 교체
}
// 엇갈렸을 경우,
// 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
quickSort(arr, start, hi - 1);
quickSort(arr, hi + 1, end);
}이진탐색
- 내가 구해야하는 최소값을 mid의 기준값으로 잡는다
- 대략 이런느낌의 코드가 나온다
int l=1;
int r=sum;
int min = Integer.MAX_VALUE;
while(l<=r){
int mid = 500;
int my = 0;
int count = m;
for(int i=0;i<n;i++){
if(cost[i]+my >= mid){
count--;
my -= cost[i];
}
else my+=cost[i];
}
if(count>m){
l = mid-1;
}
else r = mid+1;
}다익스트라
한노드~다른 모든 노드까지의 최소비용을 결정하는 알고리즘- 전체적인 코드 흐름
- node의 idx와 cost를 Node라는 class로 표현한다 그래서 graph라는 중첩 list에 저장을 해둔다
- dist라는 배열을 만든다. 이때 출발지점만 0으로 setting하고 나머지는 inf로 설정
- 반복은 전체노드의 개수만큼 진행한다
- 현재 모든 거리 비용중 방문안한 노드고 가장최소 dist를 찾아서 idx를 찾는다.
- 해당 node를 방문처리한다
- 방문한 node의 인접노드들에 대해서
node dist값,현재노드~인접노드값을 비교해서 더 작은 값으로 갱신한다
//1,2번처리되었다고 가정
for (int i = 0; i < V; i++) {
// 현재 거리 비용 중 최소인 지점을 선택한다.
// 해당 노드가 가지고 있는 현재 비용.
int nodeValue = Integer.MAX_VALUE;
// 해당 노드의 인덱스(번호).
int nodeIdx = 0;
// 인덱스 0은 생각하지 않기 때문에 0부터 반복을 진행한다.
for (int j = 1; j < V + 1; j++) {
// 해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다.
if (!visited[j] && dist[j] < nodeValue) {
nodeValue = dist[j];
nodeIdx = j;
}
}
// 최종 선택된 노드를 방문처리 한다.
visited[nodeIdx] = true;
// 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신한다.
for (int j = 0; j < graph.get(nodeIdx).size(); j++) {
// 인접 노드를 선택한다.
Node adjNode = graph.get(nodeIdx).get(j);
// 인접 노드가 현재 가지는 최소 비용과
// 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신한다.
if (dist[adjNode.idx] > dist[nodeIdx] + adjNode.cost) {
dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
}
}
}- 우선순위 큐 이용
- node의 idx와 cost를 Node라는 class로 표현한다 그래서 graph라는 중첩 list에 저장을 해둔다
- dist라는 배열을 만든다. 이때 출발지점만 0으로 setting하고 나머지는 inf로 설정
- 우선순위 큐를 사용하는데 시작점에 대한 노드를 추가하고 dist값도 0으로 초기화한다
- 큐에서 최소비용을 갖는 노드를 꺼낸다 근데 이때 해당 노드의 비용이 dist배열보다 크다면 고려할 필요가 없다(더작아져야 갱신할건데..그럴일이 발생하지않을테니 고려할 필요 없음)
- 큐에서 꺼낸 노드의 인접노드들을 방문해서 이웃노드의 거리가 현재 노드를 거쳐간게 더 빠르면 갱신된 내요을 큐에 넣는다
//1,2번 처리되었다고 가정
PriorityQueue<Node> q = new PriorityQueue<Node>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
// 시작 노드에서, 시작 노드로 가는 값이 초기에 가장 짧은 비용을 갖는 노드이다.
// 즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것이다.
q.offer(new Node(start, 0));
// 해당 노드를 선택한 것이나 마찬가지 이므로, dist[start] = 0으로 갱신.
dist[start] = 0;
while (!q.isEmpty()) {
Node curNode = q.poll();
// 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
// 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
// 주의점 2 : 중복노드 방지1 : 만일, 이 코드를 생략한다면, 언급한 내용대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
// 만일 그렇다면, 큐에 있는 모든 다음 노드에대하여 인접노드에 대한 탐색을 다시 진행하게 된다.
// 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것 만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다.
if (dist[curNode.idx] < curNode.cost) {
continue;
}
for (int i = 0; i < graph.get(curNode.idx).size(); i++) {
Node nxtNode = graph.get(curNode.idx).get(i);
if (dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
// 갱신된 경우에만 큐에 넣는다.
q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
}
}벨만포드
- 다익스트라 음수가중치 버전
- 음수가중치로 인한 사이클이 발생시 알려줄 수 있음
// 정점의 수만큼 반복
for (int i = 1; i <= N; ++i) {
// 모든 간선을 돌면서
for (int j = 0; j < edgeList.size(); ++j) {
int from = edgeList.get(j).from;
int to = edgeList.get(j).to;
int cost = edgeList.get(j).cost;
// from까지 갈수 없다면 갱신 x
if (dist[from] == INF) continue;
// to까지 가는 비용보다 from까지 가는 비용 + from에서 to까지 가는 비용이 더 저렴하다면 갱신
if (dist[to] > dist[from] + cost) {
// v번째 횟수에 갱신이 된다면 음의 사이클이 존재하기 때문에 최단 경로를 구할 수 없음.
if (i == N) {
System.out.println("음의 사이클 존재");
return;
}
dist[to] = dist[from] + cost;
}
}
}크루스칼
- 최소신장트리(MST)
- 그래프의
모든 정점을 포함하는 트리 - 그래프의 최소 연결 부분 그래프로
사이클X - 정점의 개수 n개면 간선의 개수 n-1개 가짐
- 하나의 그래프에 많은 신장 트리 존재
- 그래프의
- 초기 상태로 정점은 서로 연결되어 있지 않다. 간선을 하나씩 추가하면서 MST를 만든다. 크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.
- 구현방법
- 간선은 가중치를 기준으로 오름차순 정렬한다.
- 간선을 하나씩 살핀다. 간선을 MST에 추가했을 때 MST에 사이클이 생기지 않으면 추가한다. 사이클이 생긴다면 다음 간선으로 넘어간다.
// 유니온
public static void union(int[] parent, int x, int y) {
x = find(parent, x);
y = find(parent, y);
if(x < y) parent[y] = x;
else parent[x] = y;
}
// 파인드
public static int find(int[] parent, int x) {
if(parent[x] == x) return x;
else return find(parent, parent[x]);
}
public static void kruskal(int[][] graph, int[] parent) {
int cost = 0;
for(int i = 0; i < graph.length;i++) {
if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
cost += graph[i][2];
union(parent, graph[i][0], graph[i][1]);
}
}
System.out.println(cost);
}
unionfind(디스조인트 셋)
- Union Find: 공통 원소가 없는 부분 집합을 효과적으로 표현하기 위한 자료구조를 표현할때 사용하는 알고리즘
- Disjoint Set: 위의 알고리즘으로 표현된 자료구조
- Union(a, b)
- 합치기 ( a와 b가 속한 집합을 합친다 )
- Find ( a )
- a가 속한 집합 번호를 찾는다
- parent[i]는 '부모 노드 번호'를 의미한다 ( 자신이 어떠한 부모에 포함되어있는지를 나타냄)
private void union(int a, int b, int[] parents) {
int aParent = find(a, parents);
int bParent = find(b, parents);
if (aParent == bParent) return;
parents[aParent] = bParent;
}
public static int find(int parent[], int node){
if(node != parent[node]){
parent[node]= find(parent, parent[node]);
}
return parent[node];
}
플로이드워셜
- 모든 정점간의 최소비용을 계산하고 싶을때 사용
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}위상정렬
- 순서를 일부를 정해줬을때 전체순서를 정하는 알고리즘
- 가령 A->B라고 하자.
- 알고리즘순서
- edgeCount라는 자기에게 화살표하는 (A)의 경우 COUNT값이 1이고 B는 아무도 화살표가 출발하지 않으니 0이다. 이점을 참고하여EdgeCount를 setting
- edgeCount가 0인값을 q에 넣고
- 큐에서 하나씩 빼서 인접노드들 검사한다. 그리고 그 인접노드의 edgecount를 제거하고 이때 edgecount가 0이됐으면 큐에 넣는다
int[] edgeCount =new int[n+1];
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for(int i=0;i<=n;i++){
graph.add(new ArrayList<>());
}
for(int i=0;i<m;i++){
String input2[] = br.readLine().split(" ");
int a1 = Integer.parseInt(input2[0]);
int a2 = Integer.parseInt(input2[1]);
graph.get(a1).add(a2);
edgeCount[a2]++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i=1;i<edgeCount.length;i++){
if(edgeCount[i]==0) queue.add(i);
}
while(!queue.isEmpty()){
int x = queue.poll();
bw.write(x + " ");
for(int s :graph.get(x)){
edgeCount[s]--;
if(edgeCount[s]<=0) queue.add(s);
}
}참고
https://sskl660.tistory.com/59 (자세한 다익스트라)
https://sorjfkrh5078.tistory.com/30 (자세한 벨만포드)
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BCKruskal-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 (자세한 크루스칼)
https://st-lab.tistory.com/250 (자세한 퀵정렬)
안녕하세요!
좋은 글 잘 읽었습니다, 감사합니다.