I. 탐색
탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다.
탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다
탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프표현에 대해서 공부가 필요하다
II. 깊이 우선 탐색(DFS : depth-first serach) 이론
1. 들어가며
한쪽 분기를 지정해서 최대깊이까지 탐색하는것과 다른방식인 BFS과 비교가 된다.
(1) 정의
1)
DFS란 그래프 완전탐색기법 중 하나이다.
그래프의 시작노드에서 출발
-> 탐색할 한쪽 분기 지정 -> 해당 분기 최대 깊이까지 탐색,
-> 탐색할 다른쪽 분기 지정 -> 해당 분기 최대 깊이까지 탐색
2) 특징
두가지 방식으로 구현이 가능하다
재귀함수(이경우 스택 오버플로 유의) & 스택
3) 시간복잡도 (노드 수 : V (vertex), E (edge))
O(V + E) 의 시간복잡도를 가진다.
4) 응용문제
단절점 찾기 / 단절선 찾기 / 사이클 찾기 / 위상 정렬
(2) 핵심이론
1)
a. 노드 방문 여부 체크할 배열필요 (한번방문한 노드 다시 방문하면 안됨 : X 일시 무한 loop 빠짐)
b. 그래프는 인접리스트로 표현
c. DFS는 FILO 이므로 재귀함수나 스택을 이용한다
2)
정리하면
스택에 노드 삽입(push)시 방문 배열을 체크
스택에 노드 뺄(pop)때 탐색 순서에 기록한다
이 경우 인접 노드를 방문 배열과 대조하여 살펴본다.
3)
(3) Logic
1) DFS 시작할노드 지정 후 자료구조 초기화
a. 초기작업으로 인접리스트로 그래프 표현
b. 방문배열 초기화
c. 시작 노드 스택에 삽입
3가지 이다.
2) 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입
a.
시작점에 있던 노드를 pop 하여 노드를 꺼내고 탐색순서에 1을 기입한다.
b. 인접 리스트의 인접노드(1의 인접노드는 2,3)를 다시 스택에 삽입한다.
c. 스택에 삽입 하면서 방문배열에 체크한다
3) 스택 자료구조에 값이 없을 때 까지 반복하기
반복을 한다.
다만 중요한점은 방문한 노드는 방문배열을 확인하며 재삽입하지 않아야한다.
II. 깊이 우선 탐색(DFS : depth-first serach) - 문제 1
[ 백준 11724 ]
1. 문제설명
2. 문제풀이
(1) 문제분석
- 노드의 최대 개수 1000개 이다. 시간복잡도가 N^2 이하 알고리즘 모두 사용가능하다
- 문제에서 연결요소란 Edge로 연결된 Node의 집합을 의미한다. (미니 그래프로 생각함)
- 한번의 DFS가 끝날때 까지 탐색한 모든 노드의 집합을 의미한다.
- 연결요소의 개수는 DFS 로 탐색한 횟수로 판단할 수있다.
(2) 손으로 풀기
- 블로그에서 간략히 포현
- 한번의 탐색을 마치더라도 방문배열 초기화하면 안된다
- 아직 방문하지 않는 노드가 있으면 다시 시작점을 정해서 탐색을 진행한다
- 2번의 DFS진행은 곧 연결요소의 갯수가 2개라는 의미이다.
(3) 슈도코드 코드 작성
- 블로그에서 생략
(4) 코드 구현
1) 재귀함수로 구현
package datastructrue5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class P11724 {
//리스트를 전역으로 미리 선언해준다
//리스트를 정수형으로 타입을 정해준다.
static ArrayList<Integer>[] A;
//방문배열 참조명 선언
static Boolean [] visited;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
//입력이 10만개 이상이면 버퍼리더로 읽는것이 권장된다.
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); //
//버퍼로 입력을 받고, 문자열을 자르는 과정이다.
StringTokenizer st = new StringTokenizer(bf.readLine());
//문자열에 띄어쓰기 단위로 두개가 입력되기 때문에 잘린것은 두개로 나눠서 입력된다
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
//리스트로 입력을 받는다
// 이 경우 필요한 크기보다 1을 더해주어서 리스트 객체를 만들어준다
// 1을 더해준 이유는 데이터를 쉽게 넣고 빼기 위함이다.
A = new ArrayList[n + 1];
//방문배열도 마찬가지
visited = new Boolean[n + 1];
for(int i = 1 ; i < n + 1 ; i++) {
//리스트 안 리스트이기 때문에 각 배열인덱스 마다 리스트객체를 선언해서 넣어준다.
A[i] = new ArrayList<Integer>();
//flase로 초기화
visited[i] = false;
}
// 사고를 수월하게 하기위해 반복문 인덱스를 조정
for(int i = 1 ; i < m + 1 ; i++) {
//문자열 입력을 받는다
st = new StringTokenizer(bf.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
//양방향으로 추가(에지의 양끝점 u와 v가 주어지기 때문)
A[u].add(v);
A[v].add(u);
}
//연결요소 갯수 판단위해서
int count = 0 ;
//현재노드 순회
for(int i = 1 ; i < n + 1 ; i++) {
if(!visited [i] ) { //방문하지 않았으면
//첫번째 연결요소찾음
count++;
//노드에서 탐색 시작
DFS(i);
}
}
System.out.println(count);
}
//현재노드로 DFS탐색 시작
private static void DFS(int v) {
//깊이우선 탐색 특성상 다음 깊이에서 확인용이다
//해당 노드가 방문한적 있으면 DFS 메소드를 종료한다.
if(visited[v])
return;
// 방문배열에 특정 노드를 기록한다.
visited[v] = true;
//인접리스트의 각 노드와 연결된 노드들을
// 반복하면서 하나씩 i에 대입
for (int i : A[v]) {
if(visited[i] == false) { //방문한적 없으면
DFS(i); //대입
}
}
}
}
4. 보충 및 회고
(1) 보충
1) 인접리스트
각 노드들이 연결된 노드들의 정보를 기록하기 위한 방법이다.
2) 리스트의 종류
리스트는 배열과 비교되는 것으로서 '값과 포인터로 묶은 노드'를 포인터로 연결한 자료구조이다.
크게 2가지 종류로 순차리스트와 연결리스트로 나누어진다.
<순차리스트>
- 순차리스트는 순차적인 메모리 공간 안에 연속하여 저장되는 자료구조이다.
- 배열과 비슷하다 그래서 탐색에는 효율적이나 수정삭제에는 효율이 떨어짐
<연결리스트>
- 논리적인 순서로 메모리상에 저장할 뿐 메모리공간안에 연속하여 저장되지 않을수도 있음
- 추가 삭제에 효율적이나 탐색에 효율이 떨어짐
(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.
1) 이 문제를 풀 때 연결요소라고 해서 무엇인지 몰라서 당황을 했었다
DFS를 배우고 곧바로 연결요소라는게 나왔는데 이게 DFS와 무슨 연결점이 있는지 파악이 어려웠다
2) 이론과 달리 실제 문제에서는 방향성이 없는 경우도 같이 보여준다
III. 깊이 우선 탐색(DFS : depth-first serach) - 문제 2
[ 백준 2023 ]
1. 문제설명
2. 문제풀이
(1) 문제분석
- 재귀함수 원리를 이용해서 파고들어가는 방식을 택하자
- 이 문제는 재귀함수에 자릿수개 념을 붙여서 구현한다.
- 가지치기를 생각하자.
(2) 손으로 풀기
- 블로그에서 간략히 포현
- 첫 탐색 배열 가지치기 : 2,3,5,7
- 중간 탐색 배열 가지치키 : 뒷자리수가 짝수인 경우
- 중간 탐색 과정 가지치키 : 소수가 아닌 경우
(3) 슈도코드 코드 작성
- 블로그에서 생략
(4) 코드 구현
package datastructrue5;
import java.util.Scanner;
public class P2023 {
//
// public static void main(String[] args) {
//
//// 1
// //1번 N입력을 받는다
// Scanner sc = new Scanner(System.in);
// //자릿수 N을 입력받는다
// int N = sc.nextInt();
//
//// 2
// //2차원배열로 선언한다 (소수 4개 2,3,5,7) + ( 각각 인접리스트 표현 )
// int x [][] = new int[4][9];
// // 2차원배열로 선언 ( 동일 ) + 방문배열로 표현
// boolean y [] = new boolean[10];
// // 소수인경우 저장하는 배열 선언
// int prime[] = new int[36];
//
//
//// 3
// // 반복문으로 DFS 호출 (소수4개 반복문)
// for(int i = 1 ; i < -+ ; i ++){
// // 1자리 소수확인 -> 2차리 소수확인 한자리씩 하는 방식 재귀방식으로 호출
// y = new boolean[10];
//
// // 각 단계 마다 소수인지 반복문으로 확인하기
//
// }
//
//// 4
// // 마지막 까지 소수인지 확인되면 배열에 저장
// }
// //
// static boolean primeNumber(int num) {
// for (int i = 2 ; i < num + 1; i++) {
// //나누어 떨어질 때
// if (num % i == 0) {
// // i 와 num 이 다르면 (자기자신이 아니면)
// if (i != num) {
// //소수가 아니다)
// return false;
// }
// }
// }
// return true;
// }
//
// static void DFS(int V){
//
// }
//전역변수로 선언
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
//한정해서 넣어주기
DFS(2,1);
DFS(3,1);
DFS(5,1);
DFS(7,1);
}
static void DFS(int number, int order){
//마지막 출력용 부분
if(order == N){
if(isPrime(number)){
System.out.println(number);
}
return;
}
//1 부터 10까지 탐색위함
for(int i = 1 ; i < 10 ; i++){
//짝수는 소수가 아님 (뒤에 붙는수가)
if(i % 2 == 0)
continue;
//뒤에 붙는수가 소수이면
//한자릿수 올려서 i를 추가했는데 소수이면
//출력을 위해서 그리고 자릿수를 올려주어서 DFS를 또 호출한다.
if(isPrime(number * 10 + i))
DFS(number * 10 + i, order + 1);
}
}
private static boolean isPrime(int number) {
//왜 num/2??????
for(int i = 2 ; i <= number / 2 ; i ++)
if(number % i == 0)
return false;
return true;
}
}4. 보충 및 회고
(1) 보충
(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.
1)
이 문제에서 시작할때 2,3,5,7 이 소수라는것을 상정하고 해야할까 고민을했었다.
기본적으로 알고있다면 굳이 할필요없이 미리 설정하고, 바로 그에따라서 호출을 하면 시간복잡도를 줄일 수 있다는 것을 알게되었다
2)
궁금한점은 소수 구하는 함수에서 왜 num/2 를 했을까?
3)
가지치기를 크게보면 두번 세세하게 보면 3번한것이 흥미로웠다.
4)
가급적 문제를 풀 때 나누어서 풀고싶은데, 난이도 때문에 쉽게 이런것을 해야하는것에 대해서 생각할 여유가 부족한것같다.
1. 보충
2. 회고
1) DFS 의 실 용도가 궁금하다가 찾아보아도, 완전탐색을 한다는것이 주안점을 두면 수월할것 같다.
즉 상호연결된 그래프가 몇개인지 등이다.
찾아보려다가 괴니히스베르크 다리가까지 나왔던게 생각난다
'배움 __IL > 자료구조&알고리즘' 카테고리의 다른 글
| 알고리즘 3줄 정리 [합병정렬, 퀵정렬] (0) | 2023.12.26 |
|---|---|
| 동적계획법 : 동적계획법 이론과 문제 (0) | 2023.04.02 |
| 그리디 : 그리디 알고리즘 이론과 문제 (0) | 2023.04.02 |
| 탐색 : 이진탐색 이론과 문제 (0) | 2023.03.26 |
| 탐색 : BFS 이론과 문제 (0) | 2023.03.25 |