메이쁘

프림 알고리즘이란? -> n개의 정점을 가지는 그래프에서 MST(Minimun Spanning Tree = 최소 신장 트리) 를 구하기 위해 사용하는 알고리즘 -> 그래서 결과로 나온 트리는 N-1개의 간선을 가진다. = N-1번 반복 수행 -> 그래프의 간선을 넣을 때 간선이 방향이 없는 양방향이므로 양 쪽 다 넣어야 한다.(한 쪽만 넣어도 가능한 듯) -> 프림 : 원리 상 정점을 중심으로 간선을 탐색함. 크루스칼 : 간선을 중심으로 탐색함 -> 시간복잡도 : O(ElogV) -> 이진 힙(우선순위 큐)을 사용했을 때 매커니즘 1) 정점 중 아무 시작 정점을 고르고, 정점과 연결된 모든 Vertex를 큐에 넣는다. 2) 해당 정점에 연결된 모든 간선 중 가장 최소 비용을 가진 간선을 선택해서 연결. ..

다익스트라 알고리즘? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. -> 사이클 포함 X -> 음의 가중치가 존재하면 사용 불가능. 매커니즘 1) 체크되어있지 않은 정점 중에서 D(Distance)의 값이 가장 적은 정점(또는 시작점)을 선택(우선순위 큐에 삽입) 2) 우선순위 큐에서 해당 점을 꺼내고, 이 점을 인덱스로 하는 visited 배열의 값을 True로 변경(방문했다는 표시) -> 방문 따지면 안되는 경우도 있음..! 3) 해당 점과 연결된 모든 점을 검사(방문 여부에 관계 없이 진행. 그 이유는 최단 경로가 갱신될 수 있으므로) 4) 해당 점을 x, 연결된 다른 끝 점을 y, 이동하는 Weight를 w라고 했을 때, D[y] > D[x] + w를 만..

https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 문자열 처리 문제이다. 먼저, 길이 26의 int 배열을 만들어 사용한다. 알파벳 소문자는 아스키코드 97부터 시작하기 때문에 해당 알파벳 - 97 한 결과를 인덱스로 삼고, 결과로 나온 인덱스 원소의 count를 1 증가시킨다. 소스코드 package string; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; ..

버블 정렬 -> 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. = 인접한 두 원소를 비교하여 크기 순서를 맞춘다. -> 장점 : 구현이 매우 간단하다. -> 단점 : 일반적으로 SWAP(스왑)이 MOVE(이동)보다 복잡하기 때문에 거의 쓰이지 않는다. ** 시간복잡도 : Best : n^2, Avg : n^2, Worst : n^2 // i가 1 증가하면 처음부터 끝까지 정렬을 완료했단 뜻이므로 // 가장 맨 끝의 원소는 정렬이 완료되어있어 굳이 탐색을 하지 않는다. // i를 뺀다. for(int i = 0; i a[j + 1]) {// 여기서 스왑한다. int b =..