My Dev Blog

DP(Dynamic Programming)는 완전 탐색, DFS, BFS와 같이 수많은 경우를 따져봐야 할 때

속도가 느려지는 문제를 개선하고자 수행 시간 단축을 목적으로 만들어진 알고리즘이다.

프로그래머스의 정수 삼각형 문제를 예로 들어보자

DP 삼각형의 11이 16으로 갱신되었으므로 이제 11을 만들었던 7-3-1 조합은 고려하지 않아도 된다.

여기서 DP의 장점을 확인할 수 있다.

DP 삼각형을 활용하면 세 번째 줄의 값을 구할 때

두 번째 줄의 값만 확인하고, 첫 번째 줄의 값은 확인하지 않아도 된다.

왜냐하면 두 번째 줄에는 두 번째 줄까지의 모든 조합들 중 최고의 값만 남겨놨기 때문이다.

(이전의 정보를 확인할 필요가 없게 됨)

다섯 번째 줄까지의 최댓값은 30이며 이 값은 7-3-8-7-5 조합의 결과이다.

DP의 목적 : 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도를 개선한다.

메모리를 사용한다 : 배열 혹은 자료구조를 만든다.

중복 연산을 줄인다 : 연산한 결과를 배열에 담는다.

사실 'Dynamic Programming'보다 '기억하며 풀기 알고리즘'이 더 적합한 명칭인 거 같다.

DP 문제인지 확인하는 방법

1. DFS / BFS로 풀 수 있지만 경우의 수가 너무 많은 문제

(최대 경우의 수가 500만 개가 넘어간다면 DP로 풀이하는 게 효율적)

2. 경우의 수들에 중복적인 연산이 많은 경우

DP 유형의 경우 오래 붙잡고 있기 보다 30분 정도 고민(어떻게 하면 뒤로 돌아가지 않을 수 있을까) 후

답이 안 나오면 풀이를 참고해서 구현만 해보는 방식이 좋다.

현재 단계까지 연산을 잘 했다면 이 연산을 또 하지 않기 위해 어떤 정보를 어떻게 남겨야 할지 생각해 보자

<재귀함수를 활용한 소수 만들기 완전 탐색>

import java.util.HashSet;
import java.util.Iterator;

public class CreatePrimeNumber {
	
	// 소수 만들기
	
	static HashSet<Integer> hs = new HashSet<>();
	
	public static boolean isPrimeNumber(int num) {
		
		int limit = 0;
		
		if (num == 0 || num == 1) { // 0과 1은 소수가 아니다.
			return false;
		}
		
		limit = (int) Math.sqrt(num);
		
		for (int i = 2; i <= limit; i++) { // num이 80이라면 루트 80의 정수 값인 8까지만 체크하여 나누어떨어지는지 확인하면 된다.
			
			if (num % i == 0) { // 나누어떨어진다면 num은 1과 자기 자신을 제외한 약수를 가지는 것이므로 소수가 아니다.
				return false;
			}
		}
		
		return true;
	}
	
	public static void recursive(String comb, String rest) {
		
		if (!"".equals(comb)) {
			hs.add(Integer.parseInt(comb)); // HashSet은 중복을 허용하지 않는다.
		}
		
		for (int i = 0; i < rest.length(); i++) { // rest 문자열 중 한 문자를 comb에 붙이고, 그 문자를 제외한 나머지 문자열을 rest 값으로 다시 재귀함수를 호출한다.
			recursive(comb + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1));
		}
	}
	
	public static int solution(String numbers) {
		int answer = 0;
		int tempNum = 0;
		
		// STEP 1. 모든 조합의 숫자를 만든다.
		recursive("", numbers); // 재귀함수 호출("", "011")
		
		// STEP 2. 소수의 개수를 센다.
		Iterator<Integer> it = hs.iterator();
		
		while (it.hasNext()) {
			tempNum = it.next();
			
			if (isPrimeNumber(tempNum)) { // 소수이면
				answer++; // 개수 1 증가
			}
		}
		
		// STEP 3. 소수의 개수를 리턴한다.
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String numbers = "011"; // 11, 101
		
		System.out.println(solution(numbers)); // 2
	}
}

<반복문을 활용한 소수 찾기 완전 탐색>

import java.util.Arrays;

public class Solution {
	
	// 소수 찾기
	
	public static int solution(int n) {
        int answer = 0;
        
        boolean[] boolArr = new boolean[n + 1]; // 0 ~ n까지 체크를 위함
        
        Arrays.fill(boolArr, true);
        
        boolArr[0] = false;
        boolArr[1] = false;
        
        for (int i = 2; i <= Math.sqrt(n); i++) { // n이 10이라면 루트 10의 정수 값인 3까지 체크
        	
        	if (boolArr[i] == true) { // false 처리가 되지 않은 값이라면
        		int j = 2;
        		
        		while (i * j <= n) {
        			boolArr[i * j] = false;
            		j++;
            	}
        	}
        }
        
        for (int i = 0; i < boolArr.length; i++) {
        	
        	if (boolArr[i] == true) {
        		answer++;
        	}
        }
        
        return answer;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		
		System.out.println(solution(n)); // 4개 // 2, 3, 5, 7
	}
}

Brute Force 알고리즘 문제 풀이 Java

Brute Force(완전 탐색)

단순히 힘만으로 풀겠다는 알고리즘을 의미한다.

즉, 모든 것을 다 해보겠다는 의미이며,

숫자 4자리 비밀번호를 풀어야 하는 경우 0000부터 9999까지 모두 대입하는 것을 예로 들 수 있다.

Brute Force 풀이 방법

1. for / while loop 활용(간단한 문제의 경우)

2. 재귀함수 활용(복잡한 문제의 경우)

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	public static int[] moveRow = {-1, 1, 0, 0};
	public static int[] moveCol = {0, 0, -1, 1};
	
	public static boolean bfs(int a, int b) {
		
		Queue<Point> q = new LinkedList<>();
		
		if (arr[a][b] == 0) { // 아이스크림 재료를 부을 수 있는 칸이라면
			
			q.offer(new Point(a,b));
			
			arr[a][b] = 1; // 아이스크림 재료 붓기
			
			while (!q.isEmpty()) {
				
				Point p = q.poll();
				
				int row = p.x;
				int col = p.y;
				
				for (int z = 0; z < 4; z++) { // 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 확인하며 재료를 부을 수 있다면 같이 얼려서 아이스크림 덩어리 키우기
					int nextRow = row + moveRow[z];
					int nextCol = col + moveCol[z];
					
					// 4회 반복으로 인해 nextRow, nextCol은 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 좌표가 될 것
					
					if (nextRow < 0 || nextRow > n - 1 || nextCol < 0 || nextCol > m - 1) { // 범위를 벗어난다면 continue
						continue;
					}
					
					if (arr[nextRow][nextCol] == 0) { // nextRow, nextCol이 재료를 부을 수 있는 칸이라면
						q.offer(new Point(nextRow,nextCol)); // nextRow, nextCol 기준 상, 하, 좌, 우 좌표 또한 같이 얼릴 수 있는 칸인지 확인을 위해 큐에 담기
						
						arr[nextRow][nextCol] = 1; // 재료 붓기
					}
				}
			}
			
			return true; // 아이스크림 재료를 부을 수 있는 칸이었으므로 true 리턴하여 result 값 1 증가되도록 하기
		}
		
		return false; // 아이스크림 재료를 부을 수 없는 칸이므로 false 리턴
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (bfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

BFS 알고리즘 문제 풀이 Java

import java.util.Scanner;

public class DfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	
	public static boolean dfs(int a, int b) {
		
		if (a < 0 || a > n - 1 || b < 0 || b > m - 1) { // 범위 벗어나는지 확인
			return false;
		}
		
		if (arr[a][b] == 0) { // 아이스크림을 만들 수 있는 공간이라면
			arr[a][b] = 1; // 아이스크림을 붓기
			dfs(a, b + 1); // 상 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행 // 여기서 또 0이 나오면 아이스크림 붓고 상,하,좌,우 체크하여 dfs함수 실행 반복 또 반복
			dfs(a, b - 1); // 하 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a - 1, b); // 좌 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a + 1, b); // 우 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			return true; // 아이스크림을 만들었다면 카운트 증가를 위해 true 반환
		}
		
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (dfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

DFS 알고리즘 문제 풀이 Java

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

public class BreadthFirstSearch {
	
	// BFS
	// [BFS 알고리즘] 큐 사용 // peek() : Queue에 맨 앞에 있는 데이터를 가져온다 (Queue에서 꺼내진 않음) // poll() : Queue에 맨 앞에 있는 데이터 꺼낸다 // offer() : Stack에 데이터를 삽입
	// (6)--(2)--(1)--(3)--(5)
	//       |  /           |  \
	//      (8)            (4)--(7)
	
	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 2차원 배열 또는 리스트 활용하자
//	public static int[][] arr = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void bfs(int n) {
		Queue<Integer> q = new LinkedList<>();
		
		q.offer(n); // 넣
		
		visited[n] = true; // 방
		
		while (!q.isEmpty()) { // 반
			int x = q.poll(); // 빼
			
			System.out.println(x + " "); // 출
			
			for (int i = 0; i < graph.get(x).size(); i++) { // 반
				int y = graph.get(x).get(i);
				
				if (!visited[y]) {
					q.offer(y); // 넣
					visited[y] = true; // 방
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < 9; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 0번째는 생략
		
		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		
		graph.get(2).add(1);
		graph.get(2).add(6);
		graph.get(2).add(8);
		
		graph.get(3).add(1);
		graph.get(3).add(5);
		
		graph.get(4).add(5);
		graph.get(4).add(7);
		
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(5).add(7);
		
		graph.get(6).add(2);
		
		graph.get(7).add(4);
		graph.get(7).add(5);
		
		graph.get(8).add(1);
		graph.get(8).add(2);
		
		bfs(1); // 1부터
	}
}

BFS 알고리즘 문제 풀이 Java

import java.util.ArrayList;

public class DepthFirstSearch {
	
	// DFS
	// [DFS 알고리즘] 스택 사용 // peek() : Stack 최상단에 있는 top data 반환한다(Stack에서 꺼내진 않음) // pop() : Stack에 있는 데이터 꺼낸다 // push() : Stack에 데이터를 삽입한다 // isEmpty() : Stack 비어있는지 확인한다 // empty() : Stack을 초기화한다 // size() : Stack Size를 반환한다
	// (6)--(2)--(1)--(3)--(5)
	//       |  /           |  \
	//      (8)            (4)--(7)
	
	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 2차원 배열 또는 리스트 활용하자
//	public static int[][] arr = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void dfs(int n) {
		
		visited[n] = true; // 방
		
		System.out.println(n + " "); // 출
		
		for (int i = 0; i < graph.get(n).size(); i++) {
			
			int x = graph.get(n).get(i);
			
			if (!visited[x]) {
				dfs(x);
			}
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		for (int i = 0; i < 9; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 0번째는 생략
		
		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		
		graph.get(2).add(1);
		graph.get(2).add(6);
		graph.get(2).add(8);
		
		graph.get(3).add(1);
		graph.get(3).add(5);
		
		graph.get(4).add(5);
		graph.get(4).add(7);
		
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(5).add(7);
		
		graph.get(6).add(2);
		
		graph.get(7).add(4);
		graph.get(7).add(5);
		
		graph.get(8).add(1);
		graph.get(8).add(2);
		
		dfs(1); // 1부터
	}
}

DFS 알고리즘 문제 풀이 Java 

DFS : 한 드라마를 몰아서 본다(Stack이나 재귀함수를 사용)

BFS : 여러 드라마를 한 편씩 본다.(Queue나 LinkedList를 사용)

DFS  또는 BFS로 풀어야 하는 대표적인 유형

1. 경로 탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

DFS가 동작 검증이 쉽다.

하나씩 조합을 만들어서 정답과 비교하기 때문에 조합이 잘 나왔는지 확인이 쉽다.

하지만 수행 시간 관점에서는 복불복

운이 좋으면 첫 번째 조합이 최적의 답, 최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비하게 된다.

BFS는 한 번에 여러 조합들을 한 칸 한 칸씩 만들다 보니 조합이 완성되어 정답과 비교하는 시점에
언제 이렇게 만들어졌는지 또는 어디서부터 틀린 건지 분석하기가 까다롭다.

초반에는 느려 보일 수 있지만 하나의 정답만 찾고 나면 나머지 경우의 수는 정답에서 제외된다.

가장 먼저 넣었던 것을 꺼내기 => 연결된 점을 Queue에 넣기 => Queue가 비워질 때까지 반복

코딩 테스트에서 앞에 출제된 문제는 DFS로, 뒤에 출제된 문제는 탐색 시간이 오래 걸릴 거 같다면 BFS로 푸는 것을 추천한다.