알고리즘30 [JAVA] 너비 우선 탐색 (BFS) 너비 우선 탐색은 시작 정점에 인접한 정점들을 모두 방문한 뒤에 이 정점들에 인접한 방문하지 않은 정점들을 모두 방문한다. 이 과정을 반복해 정점들을 시작 정점까지의 최단 경로의 길이 순서대로 방문한다. 만약 탐색이 종료된 후에 아직 방문하지 않은 정점들이 남아 있다면 그 정점들 중 한 정점에서 너비 우선 탐색을 시작한다. 너비 우선 탐색 알고리즘은 깊이 우선 탐색과 달리 재귀를 사용하여 작성할 수 없는 유형이다. 대신 너비 우선 탐색은 큐를 사용하여 쉽게 작성할 수 있다. 시간복잡도 - 인접 리스트: O(V+E) - 인접 행렬: O(V^2) 알고리즘 알고리즘 BFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 BFS(v.. 2021. 12. 14. [JAVA] 깊이 우선 탐색 (DFS) 깊이 우선 탐색은 한 그래프의 정점들을 유용한 순서로 방문하는 한 방법이다 주어진 그래프의 한 정점에서 탐색을 시작하여 그 정점을 방문했다고 표시하고, 그 정점에 인접한 정점들 중 방문 안한 정점을 임의로 선택하여 방문한다 선택된 정점에 대해 같은 탐색과정을 반복한다. 더 이상 방문하지않은 인접한 정점이 없으면 바로 전에 방문했던 정점으로 돌아간다. 탐색을 반복하다가 시작 정점으로 돌아간 후 그 시작 정점에 인접한 정점들 중 방문하지 않은 정점이 없으면 종료한다. 시간복잡도 - 인접 행렬: O(V^2) - 인접 리스트: O(V+E) 알고리즘 알고리즘 DFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다. 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 DFS(v)를 호출.. 2021. 12. 12. [JAVA] 힙 정렬 (Heap Sort) 힙 정렬은 주어진 배열에 대해 힙을 구성한 후 남은 힙에서 최댓값을 순차적으로 제거하면서 정렬한다. 1. 주어진 배열을 힙(힙 조건을 만족시키는 완전 이진 트리)으로 만든다. 2. 다음을 (n-1)번 반복한다. 2.1 힙에서 최댓값을 제거한다(힙의 루트 노드의 값을 마지막 노드의 값과 교환한다) 2.2 트리에서 마지막 노드를 제거한다. 2.3 남은 트리를 힙으로 만든다. 시간복잡도 O(N logN) 알고리즘 알고리즘 HeapSort(A[1 .. n]) eh = n buildHeap(A, eh) while (eh > 1) { A[1] A[eh] eh = eh - 1 pushDown(A, 1, eh/2, eh) } 알고리즘 buildHeap(A[1 .. n], eh) bh = (n/2) + 1 while (.. 2021. 12. 7. [JAVA] 2805번 농작물 수확하기 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 마름모로 별 찍기를 할 수 있다면 쉽게 풀 수 있는 문제이다. 첫 줄의 중앙으로부터 퍼져가며 값을 더하면 정답을 구할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; public class 농작물수확하기 { public static void main(String[] args) throws Exception { .. 2021. 9. 23. [JAVA] 1251번 하나로 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 보급로 문제와 비슷하게 우선순위 큐를 사용해 문제를 풀이하였다. 좌표 형태로 값이 주어지기 때문에, 각 섬 간의 거리를 저장하고 그 값으로 비교를 하여 우선순위를 정하도록 하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; i.. 2021. 9. 22. [JAVA] 1037번 오류교정 문제 http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=316&sca=99 JUNGOL www.jungol.co.kr 풀이 단순 구현문제로, 행과 열을 따로 검사하여 1의 개수가 짝수인지 홀수인지를 판별하는 과정을 거친다. 검사하는 과정에서 홀수번째의 1이 나오면 해당 좌표를 저장한다. 그 후, 홀짝의 개수에 따라 분기를 나눠 값을 출력한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 오류교정 { public static void main(String[] args) throws Exception { B.. 2021. 9. 22. 이전 1 2 3 4 5 다음