My Dev Blog

<최대 연속 부분 수열의 합>

public class Solution {
	
	// 최대 연속 부분 수열의 합
	// 현재 합, 합의 최대값 갱신
	// 1. 수의 합을 반복적으로 구한다.
	// 2. 이 때 합이 음수이면 그 다음 수부터 다시 시작
	// 3. 합의 최대값을 도출
	
	public static int getMaxSubsequence(int[] arr) {
		int temp = 0;
		int max = 0;
		
		for (int i = 0; i < arr.length; i++) {
			temp += arr[i];
			
			if (temp > max) {
				max = temp;
			} else if (temp < 0) {
				temp = 0;
			}
		}
		
		return max;
	}
	
	public static int getMaxElementForNegativeArr(int[] arr) { // 배열의 원소가 전부 음수일 경우
		int max = -10000;
		
		for (int i = 0; i < arr.length; i++) {
			
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		
		return max;
	}

	public static int solution(int[] arr) {
		
		int result = getMaxSubsequence(arr);
		
		if (result != 0) {
			return result;
		} else { // result 값이 0이라는 건 배열의 원소가 모두 음수라는 얘기
			return getMaxElementForNegativeArr(arr);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {-3, 3, 5, -3, -7, 9, -2, 10, -5, -2};
		// 0 번째 -3 : 현재 합 0, 합의 최대값 0
		// 1 번째 3 : 현재 합 3, 합의 최대값 3 (0보다 크므로 갱신)
		// 2 번째 5 : 현재 합 8, 합의 최대값 8 (3보다 크므로 갱신)
		// 3 번째 -3 : 현재 합 5, 합의 최대값 8 (갱신되지 않음)
		// 4 번째 -7 : 현재 합 0 (else if 조건문에 의해 -2 -> 0), 합의 최대값 8 (갱신되지 않음)
		// 5 번째 9 : 현재 합 9, 합의 최대값 9 (8보다 크므로 갱신)
		// 6 번째 -2 : 현재 합 7, 합의 최대값 9 (갱신되지 않음)
		// 7 번째 10 : 현재 합 17, 합의 최대값 17 (9보다 크므로 갱신)
		// 8 번째 -5 : 현재 합 12, 합의 최대값 17 (갱신되지 않음)
		// 9 번째 -2 : 현재 합 10, 합의 최대값 17 (갱신되지 않음)
		
		System.out.println(solution(arr)); // 합의 최대값 17
	}
}

최대 연속 부분 수열의 합 알고리즘 문제 풀이 Java

플로이드 워셜 알고리즘

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.

public class FloydWarshall {
	
	// 플로이드 워셜 알고리즘
	// 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
	// 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.
	
	static int number = 4;
	static int INF = 100000000;
	static int[][] originArr = {{0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0}}; // 자료 배열 초기화
	
	public static void floydWarshall() {
		int[][] renewArr = new int[number][number]; // 결과 배열 초기화
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				renewArr[i][j] = originArr[i][j]; // 결과 배열을 초기 자료 배열과 동일하게 만들어 준다.
			}
		}
		
		// k : 거쳐가는 노드
		for (int k = 0; k < number; k++) {
			
			// i : 출발 노드
			for (int i = 0; i < number; i++) {
				
				// j : 도착 노드
				for (int j = 0; j < number; j++) {
					
					if (renewArr[i][k] + renewArr[k][j] < renewArr[i][j]) { // k 노드를 거쳐갈 때 거리 값이 더 작다면
						renewArr[i][j] = renewArr[i][k] + renewArr[k][j]; // i 노드에서 j 노드로 가는 최단 거리 갱신
					}
				}
			}
		}
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				System.out.print(renewArr[i][j] + " "); // 결과 배열 출력
			}
			
			System.out.println();
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		floydWarshall();
	}
}

Floyd Warshall 알고리즘 문제 풀이 Java

<우선순위 큐를 활용한 풀이>

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class DijkstraByPriorityQueue {
	
	public static int n = 6; // 노드의 개수
	public static int INF = 1000000; // 무한대를 의미
	public static HashMap<Integer, ArrayList<Node>> nodeListMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드의 인덱스로부터 전체 노드까지의 인덱스와 거리를 담을 리스트
	public static HashMap<Integer, Integer> minDistanceMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드까지의 최단거리(출발 노드로부터)
	
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 생성 // 출발 노드로부터 현재 최단거리에 있는 노드부터 우선적으로 빼내어 체크하기 위함(출발 노드로부터 현재 최단거리에 있는 노드를 체크해야 다른 노드들까지의 최단거리 갱신의 가능성이 있기 때문)
		Node pqNode; // 우선순위 큐에서 빼낸 노드를 담을 변수(출발 노드로부터 현재 최단거리에 있는 노드)
		ArrayList<Node> nodeList; // 우선순위 큐에서 빼낸 (출발 노드로부터 현재 최단거리)노드를 거쳐서 체크할 타겟 노드 리스트

		// 각 노드까지의 최단거리 초기화
		for (int key : nodeListMap.keySet()){ // 0 ~ 5
			minDistanceMap.put(key, INF); // 모든 최단거리 무한대로 초기화
		}
        
		minDistanceMap.put(start, 0); //출발 노드까지의 최단거리는 0으로 SET
        
		pq.add(new Node(start, 0)); // 출발 노드를 우선순위 큐에 추가 // 최단거리가 갱신되었으므로 우선순위 큐에 추가 => 이 최단거리를 거쳐 다른 노드들까지의 최단거리도 갱신될 수 있기 때문

		while (!pq.isEmpty()) { // 더 이상 최단거리 갱신이 불가할 때까지 반복

			pqNode = pq.poll(); // 출발 노드로부터 현재 최단거리에 있는 노드

			if (pqNode.getDistance() > minDistanceMap.get(pqNode.getIndex())) { // 최단거리 갱신이 가능한지 체크
				continue;
			}
            
			nodeList = nodeListMap.get(pqNode.getIndex()); // 현재 최단거리에 있는 노드를 거쳐서 체크할 타겟 노드 리스트
            
			for (Node node : nodeList) { // 타겟 노드 0 ~ 5 모두 체크
                
				if (pqNode.getDistance() + node.getDistance() < minDistanceMap.get(node.getIndex())) { // 출발 노드로부터 현재 최단거리에 있는 노드를 거쳐서 타겟 노드로 가는 거리가 타겟 노드의 최단거리보다 작을 경우
					minDistanceMap.put(node.getIndex(), pqNode.getDistance() + node.getDistance()); // 타겟 노드의 최단거리 갱신
					pq.add(new Node(node.getIndex(), pqNode.getDistance() + node.getDistance())); // 타겟 노드 우선순위 큐에 추가
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < n; i++) { // 0 ~ 5
			nodeListMap.put(i, new ArrayList<Node>()); // key값 0 ~ 5(각 노드 인덱스)마다 Node 정보를 담을 리스트 생성
		}
		
		nodeListMap.get(0).add(new Node(0, 0)); // 0번 노드로부터 0번 노드까지의 거리 0
		nodeListMap.get(0).add(new Node(1, 2)); // 0번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(0).add(new Node(2, 5)); // 0번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(0).add(new Node(3, 1)); // 0번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(0).add(new Node(4, INF)); // 0번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(0).add(new Node(5, INF)); // 0번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(1).add(new Node(0, 2)); // 1번 노드로부터 0번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(1, 0)); // 1번 노드로부터 1번 노드까지의 거리 0
		nodeListMap.get(1).add(new Node(2, 3)); // 1번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(1).add(new Node(3, 2)); // 1번 노드로부터 3번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(4, INF)); // 1번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(1).add(new Node(5, INF)); // 1번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(2).add(new Node(0, 5)); // 2번 노드로부터 0번 노드까지의 거리 5
		nodeListMap.get(2).add(new Node(1, 3)); // 2번 노드로부터 1번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(2, 0)); // 2번 노드로부터 2번 노드까지의 거리 0
		nodeListMap.get(2).add(new Node(3, 3)); // 2번 노드로부터 3번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(4, 1)); // 2번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(2).add(new Node(5, 5)); // 2번 노드로부터 5번 노드까지의 거리 5
		
		nodeListMap.get(3).add(new Node(0, 1)); // 3번 노드로부터 0번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(1, 2)); // 3번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(3).add(new Node(2, 3)); // 3번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(3).add(new Node(3, 0)); // 3번 노드로부터 3번 노드까지의 거리 0
		nodeListMap.get(3).add(new Node(4, 1)); // 3번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(5, INF)); // 3번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(4).add(new Node(0, INF)); // 4번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(1, INF)); // 4번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(2, 1)); // 4번 노드로부터 2번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(3, 1)); // 4번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(4, 0)); // 4번 노드로부터 4번 노드까지의 거리 0
		nodeListMap.get(4).add(new Node(5, 2)); // 4번 노드로부터 5번 노드까지의 거리 2
		
		nodeListMap.get(5).add(new Node(0, INF)); // 5번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(1, INF)); // 5번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(2, 5)); // 5번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(5).add(new Node(3, INF)); // 5번 노드로부터 3번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(4, 2)); // 5번 노드로부터 4번 노드까지의 거리 2
		nodeListMap.get(5).add(new Node(5, 0)); // 5번 노드로부터 5번 노드까지의 거리 0
		
		dijkstra(0); // 출발 노드 0
		
		for (int i = 0; i < n; i++) { // 0 ~ 5
			System.out.print(minDistanceMap.get(i) + " "); // 각 노드까지의 최단거리 출력(출발 노드로부터)
		}
	}
}

public class Node implements Comparable<Node> {
	
	private int index = 0; // 노드의 번호
	private int distance = 0; // 노드의 거리
	
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
	
	public int getIndex() {
		return this.index;
	}
	
	public int getDistance() {
		return this.distance;
	}

	@Override
	public int compareTo(Node otherNode) {
		// TODO Auto-generated method stub
		return this.distance - otherNode.distance; // distance 기준 오름차순 정렬 // 1, 2, 3, ...
//		return otherNode.distance - this.distance; // distance 기준 내림차순 정렬 // ..., 3, 2, 1
	}
}

출력 결과 : 0 2 3 1 2 4

Dijkstra(다익스트라) 알고리즘 우선순위 큐 문제 풀이 Java

<선형 탐색 풀이>

public class Dijkstra {
	
	public static int n = 6;
	public static int INF = 1000000;
	public static int[][] arr = {{0, 2, 5, 1, INF, INF}, {2, 0, 3, 2, INF, INF}, {5, 3, 0, 3, 1, 5}, {1, 2, 3, 0, 1, INF}, {INF, INF, 1, 1, 0, 2}, {INF, INF, 5, INF, 2, 0}};
	public static boolean[] visited = new boolean[n];
	public static int[] minDistance = new int[n];
	
	
	// 선형 탐색 풀이
	public static int getSmallestValueIndex() { // 방문하지 않은 정점 중 최소 거리를 갖는 정점의 인덱스를 반환해주기 위한 함수
		int minValue = INF;
		int minValueIndex = 0;
		
		for (int i = 0; i < n; i++) {
			
			if (!visited[i] && minDistance[i] < minValue) { // 방문하지 않은 정점 중 최단 거리인 정점의 인덱스 찾기
				minValue = minDistance[i];
				minValueIndex = i;
			}
		}
		return minValueIndex;
	}
	
	public static void dijkstra(int startIndex) {
		
		// STEP 1. 입력받은 시작 인덱스토부터 각 정점까지의 거리를 최단 거리로 SET
		for (int i = 0; i < n; i++) {
			minDistance[i] = arr[startIndex][i]; // 시작 인덱스 0으로부터 각 정점까지의 거리를 최소값으로 세팅
		}
		// {0, 2, 5, 1, INF, INF}
		
		// STEP 2. 시작 인덱스 방문처리
		visited[startIndex] = true;
		// {true, false, false, false, false, false}
		
		// STEP 3 ~ STEP 6
		for (int i = 0; i < n - 2; i++) { // n - 2를 쓰는 것이 더 효율적인 이유 : 아래에 ★ 주석 부분 참고
			
			// STEP 3. 방문하지 않은 정점 중 최소 거리를 갖는 정점 인덱스 가져오기
			int minIndex = getSmallestValueIndex(); // 바로 위의 반복문은 getSmallestValueIndex(방문하지 않은 최소 거리를 갖는 정점의 인덱스를 가져오는 함수)를 호출해야 하는 횟수를 의미
			// minIndex : 3
			
			// STEP 4. 최소 거리를 갖는 정점 방문처리 => 현재 상테에서 최소 거리를 갖는다는 말은, 다른 정점(최소 거리보다 큰 값)을 거쳤을 경우 값이 절대 갱신될 수 없음을 의미
			visited[minIndex] = true;
			// {true, false, false, true, false, false}
			
			// STEP 5. 최소 거리를 갖는 정점으로부터 방문하지 않은 다른 정점까지의 거리 체크
			for (int j = 0; j < n; j++) {
				
				if (!visited[j]) { // 방문하지 않은 정점이라면
					
					// STEP 6. 최소 거리를 갖는 정점을 거쳐서 다른 정점을 가는 거리가 더 작을 경우 갱신
					if (minDistance[minIndex] + arr[minIndex][j] < minDistance[j]) { // 최소 거리를 갖는 정점까지의 거리 + 최소 거리 정점으로부터 방문하지 않은 다른 정점까지의 거리가 다른 정점까지의 최소 거리보다 작다면
						minDistance[j] = minDistance[minIndex] + arr[minIndex][j]; // 거쳐갔을 경우의 거리 값이 더 작으므로 최소 거리 갱신
					}
				}
			}
		} 
	}
	
	// ★ 방문하지 않은 최소 거리를 갖는 정점의 인덱스를 가져와야 하는 횟수를 의미 => 이미 방문한 startIndex가 있으므로 반복 횟수 -1,
	// ★ n - 1로 했을 경우 반복문의 흐름 상 getSmallestValueIndex에서 나오는 마지막 인덱스는 STEP 4에서 방문처리가 되고(모두 방문을 마친 상태), STEP 5 반복문이 아무 의미가 없는 상황이 된다.
	// ★ 이 문제는 minDistance를 갱신하기 위함이지, 방문에 목적이 있는 것이 아니므로 횟수를 한번 더 줄여 n - 2를 해도 같은 결과가 나온다.

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		dijkstra(0); // 시작 인덱스 0
		
		for (int i = 0; i < minDistance.length; i++) {
			System.out.print(minDistance[i] + " "); // 다익스트라 이후 갱신된 최단 거리 출력
		}
	}
}

STEP 3 ~ STEP 6 부분의 첫 번째 반복문의 횟수가 n도, n-1도 아닌 n-2인 이유는

방문하지 않은 노드 중 시작 노드로부터 최단 거리에 있는 노드의 인덱스를 가져와야 하는 횟수를 의미 =>

이미 방문한 startIndex가 있으므로 반복 횟수 -1,

n - 1로 했을 경우 반복문의 흐름 상 getSmallestValueIndex에서 나오는 마지막 인덱스는 STEP 4에서 방문처리가 되고

(모두 방문을 마친 상태), STEP 5 반복문이 아무 의미 없는 상황이 된다.

​

이 문제는 minDistance를 갱신하기 위함이지, 방문에 목적이 있는 것이 아니므로 횟수를 한번 더 줄여

n - 2를 해도 같은 결과가 나온다.

출력 결과 : 0 2 3 1 2 4

Dijkstra(다익스트라) 알고리즘 선형 탐색 문제 풀이 Java

public class DynamicProgramming {
	
	// DP
	// 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
	// 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산되지 않도록 한다.
	// 일반적으로 탑다운과 보텀업으로 구성된다. 1. 최적 부분 구조(작은 문제를 모아서 큰 문제 해결 가능), 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결해야 할 때)
	// 위에 1, 2 조건 모두 만족하면 DP로 풀 수 있다.
	// 탑다운(재귀 함수), 보텀업(반복문)
	// 피보나치 수열을 예로 들 수 있다.
	// 점화식을 만들 수 있는지 확인 필요
	// 피보나치 수열의 점화식 : an = an-1 + an-2, a1 = 1, a2 = 1
	// optimal solution : 최적의 해
	
	public static int[] dpArr1 = new int[100];
	public static int[] dpArr2 = new int[100];
	
	public static int fiboRecursiveFun(int n) { // 1, 1, 2, 3, 5, 8, 13, 21..
		
		if (n == 1 || n == 2) {
			return 1;
		} else {
			return fiboRecursiveFun(n-1) + fiboRecursiveFun(n-2);
				   // fiboRecursiveFun(4) 													+ fiboRecursiveFun(3)
				   // fiboRecursiveFun(3) 							+ fiboRecursiveFun(2) 	+ fiboRecursiveFun(3)
				   // fiboRecursiveFun(2) + fiboRecursiveFun(1) 	+ fiboRecursiveFun(2) 	+ fiboRecursiveFun(3)
				   //        1            +         1               +          1            + fiboRecursiveFun(3)
			 	   //        1            +         1               +          1            + fiboRecursiveFun(2) + fiboRecursiveFun(1)
				   //	     1            +         1               +          1            +          1          +           1
				   // 단순 재귀함수를 이용해 풀게 되면 계산한 것을 또 계산하기 때문에 지수 시간 복잡도를 가지게 된다.
				   // fiboRecursiveFun(5)를 구하기 위해 fiboRecursiveFun(2)가 3번 호출된다. 숫자가 커지면 더 많이 호출될 것이다.
				   // 이미 구한 값은 메모리에 저장해놓고 꺼내서 쓰기만 하면 더 효율적이다.
		}
	}
	
	// 탑다운 방식(하향식)에서 사용되는 메모이제이션(DP를 구현하는 방법 중 하나) 재귀함수를 이용할 거야
	// fiboRecursiveFun에서 구한 값을 저장해놓는 방식
	public static int fiboTopDown(int n) {
		
		if (n == 1 || n == 2) {
			return 1;
		}
		
		if (dpArr1[n] != 0) {
			return dpArr1[n];
		}
		
		dpArr1[n] = fiboTopDown(n - 1) + fiboTopDown(n - 2); // dpArr1[1], dpArr1[2]에는 1이 들어갈 것
		
		return dpArr1[n];
	}
	
	// 보텀업 방식(상향식)은 아래쪽에서부터 작은 문제를 하나씩 해결해 나가면서 다음 문제들을 해결해 나가는 방식으로 반복문을 이용한다.(전형적인 형태)
	// 결과 저장용 리스트는 DP테이블이라고 한다.
	public static int bottomUp(int n) {
		
		dpArr2[1] = 1;
		dpArr2[2] = 1;
		
		for (int i = 3; i <= n; i++) {
			dpArr2[i] = dpArr2[i - 1] + dpArr2[i - 2];
		}
		
		return dpArr2[n];
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(fiboRecursiveFun(5)); // 재귀함수를 이용한 피보나치 // 5
		System.out.println(fiboTopDown(5)); // 재귀함수를 이용한 탑다운 DP // 5
		System.out.println(bottomUp(5)); // 반복문을 이용한 보텀업 DP // 5
		
		// 분할 정복에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.(퀵 정렬이 대표적)
		// 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보자
		// 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 메모이제이션을 활용해 코드를 개선하도록 하자
		// 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.
	}
}

DP 알고리즘 문제 풀이 Java

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. 재귀함수 활용(복잡한 문제의 경우)