[DFS/BFS] 개념정리1 - 탐색, 스택, 큐, 재귀함수

1. 탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸

대표적 탐색 알고리즘 : BFS, DFS

→ 2가지 알고리즘의 원리를 제대로 이해해야 탐색 문제 유형을 풀 수 있음

→ 2가지 알고리즘을 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 필요함

 

2. 자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

스택과 큐는 자료구조의 기초 개념으로 2가지 핵심적인 함수로 구성됨 + 언더플로우&오버플로우

1. 삽입(push) : 데이터 삽입함
2. 삭제(pop) : 데이터 삭제

 

2-1. 스택 in java

Stack<E> 클래스

• List 컬랙션 클래스의 Vector 클래스를 상속받아, 스택 메모리 구조의 클래스를 제공함 
• 스택 메모리 구조를 표현하기 위해 Vector 클래스의 메소드를 상속받아 사용함  

  

  Stack클래스의  메소드 : 각 메소드 내에서 Vector클래스의 메소드를 호출함

• 후입선출 구조 

높은 메모리 주소부터 삽입됨

[예제]

import java.util.Stack;

public class StackEx {

	public static void main(String[] args) {
		Stack<Integer> st = new Stack<Integer>(); //스택 생성 
		
		//push()를 이용한 요소 삽입 
		st.push(3);
		st.push(2);
		st.push(1);
		
		//peek()을 이용한 요소의 반환 
		System.out.println(st.peek());
		System.out.println(st); 
		
		//pop()을 이용한 요소의 반환 및 제거 
		System.out.println(st.pop());
		System.out.println(st);
		
		//search()를 이용한 요소의 위치 검색 
		System.out.println(st.search(2));
		System.out.println(st.search(3)); 
	}

}

 

2-2. 큐 in java

자바에서 큐 메모리 구조는 인터페이스 형태로 제공됨

Queue 인터페이스를 상속받는 하위 인터페이스들:

            BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는데 가장 많이 사용됨. 

• 선입선출 구조

낮은 메모리 주소부터 요소 삽입됨

[예제]

import java.util.LinkedList;

public class QueueEx {

	public static void main(String[] args) {
		LinkedList<String> qu = new LinkedList<String>(); //큐 생성 
		
		//add()를 이용한 요소의 저장 
		qu.add("h");
		qu.add("e");
		qu.add("l");
		qu.add("l");
		qu.add("o");
		
		//peek()을 이용한 요소의 반환 
		System.out.println(qu.peek());
		System.out.println(qu);
		
		//pop()을 이용한 요소의 반환 및 제거
		System.out.println(qu.pop());
		System.out.println(qu);
		
		//remove() 메소드를 이용한 특정한 요소의 제거 
		qu.remove("l");
		System.out.println(qu);		
	}
}

 

-> 더욱 복잡하고 빠른 스택과 큐 구현 시에는 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 됨 

Deque<Integer> st = new ArrayDeque<Integer>();

 

3. 재귀함수 

자기 자신을 다시 호출하는 함수

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 함

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용함

• 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문임
• 컴퓨터의 구조 측면에서 보면, 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재됨
• 즉, 재귀 함수는 내부적으로 스택 자료구조와 동일함

 

*재귀 함수 사용 시 장점?!

재귀 함수 코드가 더 간결함

• 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문임
• 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 → 다이나믹 프로그래밍과 연관되므로 중요함! ! !

[예제]

#2가지 방식으로 구현한 팩토리얼 예제
#1. 반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
	#1~n까지의 수를 차례대로 곱하기 
	for i in range(1,n+1);
		result *= i
	return result 
#2. 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <= 1: #재귀 함수의 종료 조건 
		return 1
	#n! = n * (n-1)! 
	return n * factorial_recursive(n-1)

#팩토리얼을 수학적 점화식으로 표현하기
1) n = 0 or n = 1 : factorial(n) = 1
2) n > 1 : factorial(n) = n * factorial(n-1) 

 

참고)

"이것이 취업을 위한 코딩 테스트다" 책

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html http://tcpschool.com/java/java_collectionFramework_stackQueue

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Stack.html