배경지식

Stack

• 선입후출의 자료구조

Stack<Integer> s = new Stack<>();

s.push(5);	//삽입
s.push(4);	//삽입
s.pop();	//제거

while(!s.empty()){
	System.out.print(s.peek() + "");	//최상단값 출력
    s.pop();
}

//실행결과
5

Queue

• 선입선출의 자료구조
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태

Queue<Integer> q = new LinkedList<>();

q.offer(5);	//삽입
q.offer(4);	//삽입
q.poll();	//제거

while(!q.isEmpty()){
	System.out.print(q.poll() + "");
}

//실행결과
4

재귀함수

• 자기 자신을 다시 호출하는 함수
• 재귀 함수의 종료 조건을 반드시 명시해야 함

활용 1) 최대공약수 계산 : 유클리드 호제법

유클리드 호제법이란?
두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다!

static int gcd(int a, int b) {
	if(a%b==0) {
    	return b;
	}
	return gcd(b,a%b);
}

활용 2) 최소공배수 계산

최소공배수 = 두수의 곱 / 두수의 최대공약수

static int lcm(int a,int b) {
    return a*b/gcd(a,b);
}

DFS & BFS

DFS

• 깊이 우선 탐색 / 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조 혹은 재귀함수를 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문처리.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄.
3. 더 이상 2번이 과정을 수행할 수 없을 때까지 반복.

BFS

• 너비 우선 탐색 / 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문처리.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.

---

참고

• 유튜브 (유코테2021 강의 몰아보기) 3. DFS&BFS