[이것이 코딩테스트다] 4. DFS/BFS - Stack, Queue, 재귀함수

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

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

• 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 
  • 대표적인 탐색 알고리즘 : DFS / BFS
• 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
  • 삽입(Push) : 데이터 삽입
  • 삭제(Pop) : 데이터 삭제
  • 오버플로(Overflow) : 공간이 꽉 찼는데 삽입 연산을 하면 발생
  • 언더플로(Underflow) : 공간에 데이터가 없는데 삭제 연산을 하면 발생

 

자료구조

• 스택(Stack) : FILO(First In Last Out)의 선입후출 구조. 즉, 데이터가 먼저 들어가면 가장 늦게 나오는 구조.

import java.util.Stack;

public class Main {

	public static void main(String[] args) {
        
		
		Stack<Integer> stack = new Stack<>();

		/**** Stack 사용법 ****/
		// Stack : FIFO. First In Last Out
		// push() : 삽입
		// pop() : 삭제
		// peek() : 데이터 조회
		// empty() : stack이 비어있는 지 확인. 비어있으면 true, 아니면 false 반환
		// search(Object o) : 인자값으로 받은 데이터의 위치 반환. 맨 위가 1로 시작하여 안으로 들어갈 때마다 증가
		// stack에 1,2,3,5 가 있을 때 stack.search(2)는 5~3~2 해서 3 반환
		/********************/
		
		// 삽입(1) - 삽입(2) - 삽입(3) - 삽입(4) - 삭제() - 삽입(5) - 삽입(6) - 삭제()
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.pop();
		stack.push(5);
		stack.push(6);
		stack.pop();
		
		System.out.println("2의 위치는 : " + stack.search(2));
        
        // 스택의 최상단 원소부터 출력
		// 스택이 빌 때까지 반복
        while (!stack.empty()) {
            System.out.println(stack.peek());
            stack.pop();
        }
    }

}

 

• 큐(Queue) : FIFO(First In First Out)의 선입선출 구조. 즉, 데이터가 먼저 들어가면 가장 먼저 나오는 구조.

import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Queue<Integer> queue = new LinkedList<>();

		/**** Queue 사용법 ****/
		// Queue : FIFO. First In First Out
		// JAVA에서 Queue 선언 시, LinkedList 필요
		// add(), offer() : 삽입. overflow 상황에서 add는 예외발생, offer는 false 반환
		// remove() : 첫번 째 데이터 삭제
		// poll() : 첫번 째 데이터 반환하고 삭제. 비어있으면 null 반환
		// peek() : 데이터 조회
		// isEmpty() : queue이 비어있는 지 확인. 비어있으면 true, 아니면 false 반환
		// clear() : 큐 비우기
		/********************/
		
        // 삽입(1) - 삽입(2) - 삽입(3) - 삽입(4) - 삭제() - 삽입(5) - 삽입(6) - 삭제()
		queue.offer(1);
		queue.offer(2);
		queue.offer(3);
		queue.offer(4);
		queue.poll();
		queue.offer(5);
		queue.offer(6);
        queue.poll();
        
        // 먼저 들어온 원소부터 추출
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
	}

}

 

• 재귀 함수(Recursive Function) : 자기 자신을 다시 호출하는 함수

public class recursive_Function_example {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// 아래에서 선언한 재귀함수에 인자를 1로 하여 호출
		recursiveFunction(1);
	}

	public static void recursiveFunction(int num) {
        
		// 100번째 호출을 했을 때 종료되도록 종료 조건 명시
        if (num == 100) 
        	return;
        
        System.out.println(num + "번 째 재귀 함수에서 " + (num + 1) + "번 째 재귀 함수를 호출");
        // 자기 자신을 num을 1 증가시켜서 호출
        recursiveFunction(num + 1);
        System.out.println(num + "번 째 재귀 함수를 종료");
    }
}