코딩 테스트를 준비하게 되면서 먼저 알고리즘에 대해서 정리 해볼 필요가 생겼다
하루에 한 개에서 두 개씩 준비해보도록 하자
모든 자료는 해당 블로그를 참조해서 공부하였다
👨🏻💻 Tech Interview (gyoogle.dev)
👨🏻💻 Tech Interview
gyoogle.dev
1. 버블 정렬(Bubble Sort) - 8 / 2
2. 선택 정렬(Selection Sort)
3. 삽입 정렬(Insertion Sort)
4. 퀵 정렬(Quick Sort)
5. 병합 정렬(Merge Sort)
6. 힙 정렬(Heap Sort)
7. 기수 정렬(Radix Sort)
8. 계수 정렬(Counting Sort)
9. 이분 탐색(Binary Search)
10. 해시 테이블(Hash Table)
11. DFS & BFS
12. 최장 증가 수열(LIS)
13. 최소 공통 조상(LCA)
14. 동적 계획법(DP)
15. 다 익스트라(Dijkstra) 알고리즘
16. 비트마스크(BitMask)
1. 버블 정렬(Bubble Sort)
[ 버블 정렬이란? ]
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
- 요 약 -
int arr[ ] = new arr[5]
라는 배열이 있고 해당 배열에
1, 5, 3, 2, 4
라는 데이터가 있다고 치자
그럴 때 버블 정렬을 사용하게 되면
arr[0] 번째 숫자 부터 비교를 해서 큰 숫자를 뒤로 미루게 된다
[0,1] - [1,2] - [2,3] - [3,4]
의 형식으로 데이터를 비교하게 된다
[ 코드 ]
int temp = 0;
for(int i = 0; i < arr.length; i++) { // 1.
for(int j= 1 ; j < arr.length-i; j++) { // 2.
if(arr[j-1] > arr[j]) { // 3.
// swap(arr[j-1], arr[j])
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
↑ 위 코드에서 알 수 있듯이
기존 배열 : 1 5 3 2 4
1번 루프 : 1 3 2 4 5
2번 루프 : 1 2 3 4 5
3번 루프 : 1 2 3 4 5
4번 루프 : 1 2 3 4 5
5번 루프 : 1 2 3 4 5
6번 루프 : 해당 배열의 길이가 5이기에 5번만 반복문을 진행함
위와 같은 형식으로 정렬하게 된다
[ 시간 복잡도 ]
O(n^2)
시간 복잡도를 계산하면
(n-1) + (n-2) + (n-3) ... + 2 + 1 => n (n-1) / 2
[ 공간 복잡도 ]
O(n)
주어진 배열 안에서 교환을 통해 정렬이 수행 된다
[ 장 점 ]
● 구현이 매우 간단하고, 소스 코드가 직관적임
● 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간을 필요로 하지 않음
● 안정 정렬
[ 단 점 ]
● 시간 복잡도가 최악, 최선, 평균 모두 O(n^2) 으로 굉장히 비효율적이다
● 정렬 되어 있지 않은 원소가 정렬 되었을 때의 자리로 가기 위해서 교환연산(swap)가 많이 일어나게 된다
2. 선택 정렬(Selection Sort)
[ 선택 정렬 이란? ]
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 요 약 -
배열을 0번째 부터 시작해서 뒤에 있는 배열들과 비교한다
그렇게 해서 해당 자리에 가장 작은 데이터를 교환하여
가장 작은 데이터를 앞쪽으로 배치시키는 정렬 방법이다
[ 코 드 ]
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
indexMin 에 0 ~ 길이 - 1 을 하여서 비교한다
-1을 하는 이유는 결국 마지막에 남은 데이터는 가장 큰 데이터일 것이 기 때문에 비교할 필요가 없기 때문이다
그렇게 해서 i + 1 (선택 배열 보다 1자리 뒤의 배열) 부터 비교해서 더 작은 것을 indexMin에 넣어주고
해당 데이터를 교환해서 데이터를 저장한다
[ 장 점 ]
● 알고리즘 단순함
● 정렬을 위한 비교 횟수는 많지만 실제 교환횟수는 버블 정렬에 비해 적기에 많은 교환이 일어나는 자료에서는 효율적
● 배열 안에서 일어나는 교환 방식으로 다른 메모리가 필요하지 않음
[ 단 점 ]
● 시간복잡도가 O(n^2) 로 비효율적이다
● 불안정 정렬
[ 시간 복잡도 ]
O(n^2)
[ 공간 복잡도 ]
O(n)
3. 삽입 정렬(Insertion Sort)
[ 삽입 정렬 이란? ]
2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정 된 자리에 자료를 삽입하는 정렬
- 요 약 -
2번 째 원소부터 앞의 값들과 값을 비교하여 한칸 씩 작은 데이터를 앞으로 당겨주는 방식이다
예를 들어
배열의 1번 값이 0보다 작으면 1과 0을 교환
배열의 2번 값이 0 , 1 보다 작으면 교환 등
앞 쪽의 데이터와 비교해서 데이터를 바꿔주는 방식
[ 코 드 ]
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
[ 장 점 ]
● 알고리즘 단순
● 대부분의 원소가 이미 정렬되어 있을 경우 굉장히 효율적
● 배열 안에서 일어나는 교환방식이므로, 다른 메모리 필요없음
● 안정 정렬
● 버블, 선택에 비해서 빠르다
[ 단 점 ]
● 평균, 최악 시간복잡도는 O(n^2)
● 버블, 선택과 마찬가지로 배열이 길어지면 길어질수록 비효율 적이다
[ 시간 복잡도 ]
최악 : O(n^2)
최선 : O(n)
[ 공간 복잡도 ]
O(n)
4. 퀵 정렬(Quick Sort)
[ 퀵 정렬 이란? ]
퀵 정렬이란 피벗이라는 기준 데이터를 정한 뒤
해당 데이터 보다 작은 값은 왼쪽으로 해당데이터 보다 큰 값은 오른쪽으로 정렬시켜
재귀함수를 사용해 무한히 반복적으로 반복하여 정렬시키는 방법
반드시 재귀가 멈출 수 있는 방법을 만들어 줘야한다
- 요 약 -
만약 배열 a가 있고 a의 데이터가 이렇다고 가정해보자
[a]
1 3 7 9 5 6 4
해당 배열이 있을 때 보통은 피벗(기준) 데이터를
배열 길이 / 2 = 데이터 중앙 값
으로 설정하는데 해당 a 배열에서는 9가 피벗으로 설정 된다
그러고 난뒤 데이터를 비교 9보다 큰 값은 뒤로 9보다 작은 값은 앞으로 이동시킨다
이러한 방법을 계속해서 반복하게 되고
다음 루틴에서도 피벗을 정하고 순서를 바꾸고
진행하게 되고 모든 배열이 크기에 맞게 정렬되었을 때 재귀함수가 멈추고
정렬된 데이터를 볼 수 있게 된다
[ 코 드 ]
package Algorithm.One;
import java.util.Scanner;
public class QuickSort {
static void swap(int a[], int idx1, int idx2){
int temp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = temp;
}
// 배열을 나눈다
static void quickSort(int a[], int left, int right){
int pl = left;
int pr = right;
int x = a[(pl+pr)/2];
System.out.printf("a[%d]~a[%d] : {", left, right);
for(int i = left; i < right; i++){
System.out.printf("%d, ", a[i] );
}
System.out.printf("%d}\n", a[right]);
System.out.println("pl : " + pl + " / pr : " + pr);
do{
while(a[pl] < x) {// pl : 피벗 좌측에 데이터가 몇개 있는지를 계산
pl++;
}
System.out.println("pl : " + pl);
while(a[pr] > x){ // pr : 피벗 우측에 데이터가 몇개 있는지를 계산
pr--;
}
System.out.println("pr : " + pr);
if(pl <= pr){
swap(a, pl++, pr--);
}
}while(pl <= pr);
if(left < pr) {
quickSort(a, left, pr);
}
if(pl < right){
quickSort(a, pl, right);
}
}
public static void main(String[] args){
// 퀵배열을 만들어보자
// 배열을 만들고 데이터를 입력 받는다
// 해당 데이터를 중앙의 퍼빗을 만들어서 작은값은 좌측으로 큰값은 우측으로 이동
// 재귀적으로 반복할 수 있게 설정한다
Scanner sc = new Scanner(System.in);
System.out.print("배열 크기를 입력하세요 : ");
int n = sc.nextInt();
int arr[] = new int[n];
System.out.println("배열 크기 : " + arr.length);
for(int i = 0; i < arr.length; i++){
System.out.print( i+1 +"번째 데이터 : ");
arr[i] = sc.nextInt();
}
System.out.println("입력된 데이터");
for(int i = 0; i < arr.length; i++){
System.out.print("[" + arr[i] + "] ");
}
System.out.println();
quickSort(arr, 0, n-1);
for(int i = 0; i < arr.length; i++){
System.out.print("[" + arr[i] + "] ");
}
}
}
데이터의 피벗을 전체 데이터 / 2로 정하고
처음에 설정했던 가장 좌측값 left와, 정렬 된 데이터가 아닐 때 pl과 pr의 값이 바뀌어서
다시금 피벗을 기준으로 좌측 우측이 나뉘어져서 퀵 정렬을 할 수 있도록 재귀처리되어있다
[ 장 점 ]
● 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog2n)를 가지는 다른 알고리즘과 비교했을 때 가장 빠르다
● 정렬하고자하는 배열 안에서 교환이 이뤄지는 방식으로, 다른 메모리 공간 필요로 하지 않는다
[ 단 점 ]
● 불안정 정렬
● 정렬된 배열에서는 수행시간이 더 많이 걸린다
[ 시간 복잡도 ]
최선 :O(nlog₂n)
평균 : O(nlog₂n)
최악 : O(n^2)
[ 공간 복잡도 ]
O(n)
5. 병합 정렬(Merge Sort)
[ 병합 정렬 이란 ? ]
합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현하는 정렬법으로
큰 문제를 작은 문제 반위로 쪼개가면서 해결해나가는 방식
예를 들어, 8개의 데이터가 들어있는 배열이 있다면 해당 데이터를 1개씩 쪼개서
2개, 4개 씩 정렬하면서 합치는 병합하는 정렬 방식을 의미한다
시간 복잡도 부분에서 굉장히 빠른 정렬 방법으로, 퀵소트와 많이 언급되는 정렬 방식이다
[ 코 드 ]
private void solve() {
int[] array = { 230, 10, 60, 550, 40, 220, 20 };
mergeSort(array, 0, array.length - 1);
for (int v : array) {
System.out.println(v);
}
}
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
public static void merge(int[] array, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(array, left, mid + 1);
int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while (i < ll && j < rl) {
if (L[i] <= R[j]) {
array[k] = L[i++];
} else {
array[k] = R[j++];
}
k++;
}
while (i < ll) {
array[k++] = L[i++];
}
while (j < rl) {
array[k++] = R[j++];
}
}
mergeSort 라는 범위를 나누는 메소드를 실행해서 배열을 쪼갠다
그리고 난 뒤 merge라는 정렬 메소드를 통해서 배열을 정렬하면서 합친다
합병 정렬은 이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있는 상태이기에
두 배열을 순차적으로 비교하면서 정렬할 수가 있다
합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적 이다
하지만 LinkedList에 퀵 정렬을 사용하면 오버플로우가 발생해서 비효율적이다
6. 힙 정렬(Heap Sort)
7. 기수 정렬(Radix Sort)
[ 기수 정렬 이란 ? ]
데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식
[ 코 드 ]
void countSort(int arr[], int n, int exp) {
int buffer[n];
int i, count[10] = {0};
// exp의 자릿수에 해당하는 count 증가
for (i = 0; i < n; i++){
count[(arr[i] / exp) % 10]++;
}
// 누적합 구하기
for (i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 일반적인 Counting sort 과정
for (i = n - 1; i >= 0; i--) {
buffer[count[(arr[i]/exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++){
arr[i] = buffer[i];
}
}
void radixsort(int arr[], int n) {
// 최댓값 자리만큼 돌기
int m = getMax(arr, n);
// 최댓값을 나눴을 때, 0이 나오면 모든 숫자가 exp의 아래
for (int exp = 1; m / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]); // 좋은 습관
radixsort(arr, n);
for (int i = 0; i < n; i++){
cout << arr[i] << " ";
}
return 0;
}
[ 시간 복잡도 ]
O ( d * n + b ) )
[ 장점 ]
문자열, 정수 정렬 가능
[ 단 점 ]
자릿수가 없는 것은 정렬이 불가능하다
중간 결과를 저장할 bucket 공간이 필요하다
9. 이분탐색(Binary Search)
[ 참고 블로그 ]
https://bbangson.tistory.com/73
[Java] 이분 탐색(Binary Search)
공부를 목적으로 진행하는 포스팅으로 만약 틀린 부분이 있거나 미흡한 점이 있으면 피드백 부탁드리겠습니다. 이분 탐색 혹은 이진 탐색이라 불리는 이 알고리즘은 간단하면서 굉장히 효율
bbangson.tistory.com
[ 이진 탐색 이란 ? ]
간단하게 이야기하자면
배열 안에서 어떠한 숫자를
탐색할 때 사용하는 알고리즘으로
배열의 중앙이 탐색하는 숫자와 같은지 비교,
해당 비교할 숫자보다 중앙 값이 작으면 시작지점을 늘리고
중앙 값이 크며 끝지점을 줄이는 방식으로
점점 범위를 좁혀가며 탐색하는 방식을 말한다
아래의 코드를 보자
- 배열 -
1 2 3 4 5
- 탐색할 숫자 -
4
먼저 중앙값을 설정한다
보통 중앙값은 시작점과 끝점을 더해서 % 2를 한값을 설정한다
int mid = 0 + 4 / 2 = 2
배열[ 2 ] == 3
즉 중앙 값에는 3이 들어가게 된다
하지만 중앙 값이 탐색하는 숫자와 같지 않고 중앙 값이 기준값보다 작다
그렇기에 시작지점을 늘려준다
현재 중앙 값보다 컸기에 중앙 값인 3보다 큰 숫자 4를 시작지점으로 지정
확인 한 뒤 반복한다
위의 방식으로 탐색할 숫자를 찾아서 있으면 true
탐색할 숫자가 없으면 false를 반환한다
코드를 보자
해당 문제
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
[ 코드 ]
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
// 배열 입력
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
// 배열 정렬
Arrays.sort(arr);
// 검색할 숫자 갯수 입력
int t = sc.nextInt();
while(t -->0){
// 검색할 숫자자
int target = sc.nextInt();
boolean check = binarySearch(arr, target);
if(check){
System.out.println(1);
}else{
System.out.println(0);
}
}
}
해당 코드에서 주목할 점은
while문 부분이다
binarySearch를 메소드를 구현해서 배열과 target(탐색할 숫자) 를 넣어서
숫자가 해당 배열(arr)에 있으면 true, 없을 때는 false를 반환하고
있을때는 1을 출력, 없을 때는 0을 출력한다
그러면 binarySearch를 보도록하자
매개변수에는 arr[] 탐색할 배열, target 탐색 목표 숫자 를 변수로 받는다
public static boolean binarySearch(int arr[], int target){
int start = 0;
int end = arr.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(arr[mid] == target){
return true;
}else if(arr[mid] < target){
start = mid + 1;
}else if(arr[mid] > target){
end = mid - 1;
}
}
return false;
}
while 문을 통해서 target이 해당 배열에 없는 숫자일 경우 반복을 종료하게 조건을 설정 후
중간 값 mid를 정한다
그리고 난 뒤 target을 탐색해나가고 탐색 성공시 true를 반환
없을 시 fasle를 반환하는 형식이다
11. BFS & DFS
[ 가장 좋은 정리 유튜브 ]
https://www.youtube.com/watch?v=_hxFgg7TLZQ
(1) 깊이 우선 탐색 (DFS)
Depth First Search
https://codingnojam.tistory.com/44
[Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!
안녕하세요 코딩노잼입니다. 오늘은 그래프와 트리를 탐색할 때 사용되는 DFS알고리즘에 대해서 알아보겠습니다. 1. DFS(Depth-first Search)란? DFS는 번역하면 깊이 우선 탐색이라고 합니다. 이름에서
codingnojam.tistory.com
깊이 우선 탐색이라는 것은
연결 된 노드를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들이 없을 때 그 전 노드로 되돌아 가고 다시 연결된 노드를 따라서 탐색을 진행하는 것을 말합니다
DFS 는 스택 방식을 활용해서 진행하는데
Stack의 구조는
위의 사진으로 간단하게 이해할 수 있다, LIFO 형식으로 마지막에 들어간 것 부터 출력되는 방식이다
스택을 사용해서 DFS를 사용하는 방법도 있지만
기본적으로 프로그램은 스택방식을 사용하기에 재귀 적인 코드를 활용하면 코드를 더 깔끔하게 구현할 수 있다
위 와 같은 그래프가 있을 때
1부터 시작해서 DFS를 실행한다(오름차순)
그러면
1 - 2 - 6 - 8 - 3 - 5 - 4 - 7
순으로 출력되게 된다
[ 코 드 ]
코드를 보기전 그래프는 위의 사진과 동일한 그래프를 미리 셋팅한 체로 코드를 진행한다
// 그림예시 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};0번은 비워 둔 체로 2차원 배열에
앞을 i, 뒤를 j라고 했을 때
0 ~ 8 까지 배열이 존재하고
0 번은 비워둔 체로
1번 노드는 2,3,8과 연결
2번 노드는 1,6,8과 연결
되어있는 형식이다
위의 형식을 잘 보고 코드를 보도록 하자
(1) 재귀 방식
public class Main {
// 방문처리에 사용 할 배열선언
static boolean[] vistied = new boolean[9];
// 그림예시 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
public static void main(String[] args) {
dfs(1);
}
static void dfs(int nodeIndex) {
// 방문 처리
vistied[nodeIndex] = true;
// 방문 노드 출력
System.out.println("출력 : " + nodeIndex);
// 방문한 노드에 인접한 노드 찾기
for (int node : graph[nodeIndex]) {
// 인접한 노드가 방문한 적이 없다면 DFS 수행
if(!vistied[node]) {
dfs(node);
}
}
}
}
재귀 방식은
1. dfs에 1을 넣어 준다
2. 아래의 dfs(int nodeIndex) 메소드가 실행된다
3. visitied[1]번이 true로 바뀐다(이건 1번이 출력되었다는 의미이다)
4. int node : graph[nodeIndex]에 있는 값을 첫번째 숫자부터 node에 넣어서 for문을 실행한다
5. if 문을 통해서 visitied 즉 출력했는지 안했는지 체크를해서 출력하지 않았을 때 다시 재귀 함수를 통해서 dfs에 출력하지 않은 노드 값을 넣어서 실행한다
6. 중요한 것은 출력이 다되면 그 다음 숫자를 자동으로 출력하게 된다
7. 모든 visitied가 true (즉, 모든 값을 출력) 이 되면 재귀는 종료되게 된다
(2) 스택 방식
public class Main {
// 방문처리에 사용 할 배열선언
static boolean[] vistied = new boolean[9];
// 그림예시 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
// DFS 사용 할 스택
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) {
// 시작 노드를 스택에 넣어줍니다.
stack.push(1);
// 시작 노드 방문처리
vistied[1] = true;
// 스택이 비어있지 않으면 계속 반복
while(!stack.isEmpty()) {
// 스택에서 하나를 꺼냅니다.
int nodeIndex = stack.pop();
// 방문 노드 출력
System.out.print(nodeIndex + " -> ");
// 꺼낸 노드와 인접한 노드 찾기
for (int LinkedNode : graph[nodeIndex]) {
// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리
if(!vistied[LinkedNode]) {
stack.push(LinkedNode);
vistied[LinkedNode] = true;
}
}
}
}
}
스택 방식은 길어지니 유튜브 영상을 참조하자
(2) 넓이 우선 탐색(BFS)
https://minhamina.tistory.com/36
[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현
BFS 너비 우선 탐색(Breadth First Search) "꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다. 시작 정
minhamina.tistory.com
Breadth First Search
가까운 거리에 있는 노드를 먼저 탐색하는 방식이다
BFS는 DFS 와는 다르게 재귀 방식으로는 사용이 불가능하고 큐(Queue)방식으로 탐색을 진행한다
[ 구현 방법 ]
참조 블로그에 굉장히 이해하기 쉬운 자료가 있어서 가져왔다
간단하게 정리하자면 시작 지점을 기점으로 오름차순이라는 가정하에 먼저 낮은 숫자부터 큐에 입력한다
인접한 모든 노드의 숫자를 큐에 삽입 시킨 뒤 가장 앞에 있는 노드를 출력하고 난 뒤 해당 노드로 이동 해당 노드의 모든 데이터를 큐에 삽입
그리고 출력 삽입 작업을 반복하고 난 뒤 모든 데이터를 삽입 완료하면 큐에있는 데이터를 전부 출력한다
[ 코 드 ]
package Algorithm.One;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
// 하나를 더 만드는 이유는 ?? 0번째에는 노드의 데이터를 넣지 않기위해서 1번 부터 넣을꺼기 때문에
LinkedList<Integer>[] adjList = new LinkedList[n + 1];
// 모든 링크드리스트의 배열 생성
for (int i = 0; i <= n; i++) {
adjList[i] = new LinkedList<Integer>();
}
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjList[v1].add(v2);
adjList[v2].add(v1);
}
for (int i = 1; i <= n; i++) {
Collections.sort(adjList[i]); // 방문 순서를 위해 오름차순 정렬
}
for(int i = 0; i < adjList.length; i++){
System.out.println((i) + "번째 : " + adjList[i]);
}
System.out.println("BFS - 인접리스트");
bfs_list(v, adjList, visited);
}
// BFS - 인접리스트
public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
// 큐 생성
Queue<Integer> queue = new LinkedList<Integer>();
// 첫번째 방문할 노드 방문해서 큐에 add 했기에 true 방문 표시
visited[v] = true;
queue.add(v);
// 큐에서 데이터를 전부 꺼내면 종료하는 반복문
while(queue.size() != 0) {
// v 에다가 가장 앞에 있는 데이터를 출력
v = queue.poll();
System.out.print(v + " ");
// LinkedList(Graph) 에서 해당 노드와 연결 되어 있는 노드를 전부 iter에 저장
Iterator<Integer> iter = adjList[v].listIterator();
// iter에 저장한 데이터가 없을 떄 까지 실행
while(iter.hasNext()) {
// w에 iter에 있는 데이터를 오름차순으로 꺼낸다(오름 차순인 이유는 위에서 sort 정렬을 사용했기 때문이다)
int w = iter.next();
// 해당 데이터에 방문한 적이 없어서 false라면 해당 데이터를 큐에 삽입하고 방문 표시를 남긴다
if(!visited[w]) {
visited[w] = true;
queue.add(w);
}
}
}
}
}'알고리즘' 카테고리의 다른 글
| 18. [JAVA] 투 포인터, 슬라이딩 윈도우 (0) | 2022.08.24 |
|---|---|
| 17. [JAVA] 스택 과 큐(Stack / Queue) (0) | 2022.08.24 |
| 16. [JAVA] Comparable (0) | 2022.08.17 |
| 15.[JAVA] Arrays.sort / Collecions.sort (0) | 2022.08.16 |
| 14. [JAVA] ValueOf, contains (0) | 2022.08.15 |
