공부리뷰_10주차

전재우·2021년 3월 28일
0

알고리즘

2021-03-22

최단 경로

최단 경로 정의

  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소 인 경로

하나의 시작 정점에서 끝 정점가지의 최단 경로

  • 다익스트라 알고리즘

    음의 가중치를 허용하지 않음

  • 벨만-포드 알고리즘

    음의 가중치 허용

모든 정점들에 대한 최단 경로

  • 플로이드-워샬(floyd-warshall) 알고리즘

다익스트라 알고리즘

→ 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.

시작 정점에서의 거리 D 배열이 중요하다.

  • 인접 행렬을 이용한 다익스트라 알고리즘
package com.study36;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTest {
	public static void main() throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());
		int start = 0;
		int end = V-1;
		
		int[][] adjMatrix = new int[V][V]; //인접 행렬
		
		StringTokenizer st = null;
		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < V; j++) {
				adjMatrix[i][j]=Integer.parseInt(st.nextToken());			}
		}
		
		
		int[] distanece = new int[V];
		boolean[] isSelected = new boolean[V];
		Arrays.fill(distanece, Integer.MAX_VALUE);
		distanece[start] = 0;
		for (int i = 0; i < V; i++) {
			int min = Integer.MAX_VALUE;
			int current=0; //min 최소비용에 해당하는 정점 번호
			
			//step 1 : 처리하지 않은 정점중에 출발지에서 가장 가까운 (최소비용) 정점 선택
			//최적화를 위해서 최소 힙을 사용 하는 방법!도 있음
			for (int j = 0; j < V; j++) {
				if(!isSelected[j]&& min>distanece[j]) {
					min = distanece[j];
					current = j;
					
				}
			}
			isSelected[current] = true;
			if(current == end) break; //
			
			
			//step 2 : 선택된 current를 경유지로 하여 아직 처리하지 않은 다른 정점으로의 최소 비용을 따져본다
			for (int j = 0; j < V; j++) {
				if(!isSelected[j]&&adjMatrix[current][j] !=0&&distanece[j] > min + adjMatrix[current][j] ) {
					distanece[j]= min + adjMatrix[current][j];
				}
			}
			
		}
		System.out.println(distanece[end]);
	}
	
}

최적화를 위한 PQ를 이용해서 최소 힙을 사용해서 맨 위에 값을 꺼내기만 하면된다.

→ step2 에서 계속 삽입이 되어야한다 .

문자열 알고리즘

패턴 매칭에 사용 되는 알고리즘

  • 고지식한 패턴 검색 알고리즘(완탐,브루트포스)

    본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식

  • KMP알고리즘

라빈 - 카프 알고리즘

문자열 검색을 위해 해시 값 함수를 이용

패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값만을 비교

최악의 시간 복잡도는 O(MN) 이지만 평균적으로는 선형에 가까운 빠른속도를 가지는 알고리즘

KMP 알고리즘

  • 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교 하지 않고 매칭을 수행

  • 패턴을 전처리하여 배열 fail[k]을 구해서 잘못된 시작을 최소화함

    fail[k] : k인덱스에서 일치하는 접두사와 접미사가 일치하는 최대 길이

  • 시간 복잡도 : O(M+N)

보이어 무어 알고리즘

오른쪽에서 왼쪽으로 비교

보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치 하고

이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이 만큼이 된다.

최악의 시간 복잡도는 O(MN)이지만 최선의 시간 복잡도는 O(N/M) 이며 평균적으로는 가장 빠른 속도를 가지는 알고리즘

DP (다이나믹 프로그래밍)

피보나치 수열

  • 피보나치 수를 구하는 재귀함수

메모이제이션

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산 하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술

→ 메모리에 넣기 라는 의미이며, 기억되어야할 것 이라는 뜻에서 나왓다.

메모가 구분 가능한 초기 값을 memo[0] 저장한다.

동적 계획법은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.

⇒ "똑똑한 완탐"

최적화 문제 : 최적(최대값이나 최소값 같은) 값을 구한느 문제

  • 해당 문제에 여러 해가 있을 수 있다.

동적 계획법 적용 요건

  • 중복 부분 문제 구조

    DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제를 해결한다

    ⇒ 순환적 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적인 도구인 점화식을 이용

    DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에 필요하게 되는데 이를 위해서 DP는 이미 해결된 작은 문제들의 해들을 어떤 공간에 저장 하게 된다.

    그리고 이렇게 저장된 해들이 다시 필요할 떄마다 해를 얻기 위해 다시 문제를 재계산하지 않고 Table의 참조를 통해서 중복된 계산을 피하게 된다

  • 최적 부분문제 구조

    동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는것은 아니다. 주어진 문제가 최적화의 원칙을 만족해야만 동적 계획법을 효율적으로 적욜할 수 있다.

    최적화의 원칙이란 어떤 문제에 대한 해가 최적일 떄 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법의 방법 자체가 큰 문젤의 최적해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이문제는 동적 계획법을 정용 X

  • 최적의 원칙이 적용되지 않는 예 : 최장경로 문제

    A에서 D로의 최장 경로는 A,B,C,D

    그러나 , 이 경로의 부분 경로인 A에서 C로의 최장 경로는 A,C가 아니라 A,B,C이다.

    → 최적의 원칙이 적용 X

    따라서 최장 경로 문제는 DP로 해결 불가능

분할 정복과 동적계획법의 비교

  • 분할 정복

    연관 없는 부분 문제로 분할한다.

    부분문제를 재귀적으로 해결한다.

    부분문제의 해를 결합한다.

    병합 정렬, 퀵정렬

  • DP

    부분 문제들이 연관이 없으면 적용할 수 없다. 즉 부분 문제들은 더 작은 부분 문제들을 공유한다.

    모든 부분 문제를 한번만 계산하고 결과를 저장하고 재사용한다.

    DP에는 부분 문제들 사이에 의존적 관계가 존재한다 (순환적인 관계)

    이런한 관계는 문제에 따라 다르고 대부분의 경우 뚜렷이 보이지 않아서 함축적인 순서라고 한다.

    분할 정복은 하향식 방법으로 DP는 상향식 방법으로 접근한다.

3단계 DP 적용 접근 방법

최적해 구조의 특성을 파악하라

  • 문제를 부분 문제로 나눈다

    최적해의 값을 재귀적으로 정의하라 → 연관선 순환관계- >점화식

  • 부분문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다.

    상향식 방법으로 최적해의 값을 계산하라

  • 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장

    • 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다(상향식 방법)

    피보나치 수 DP 적용
    피보나치 수는 부분 문제의 답부으로 부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.

  1. 문제를 부분 문제로 분할한다.
  2. 점화식으로 정의한다.
  3. 가장 작은 부분문제부터 해를 구한다 . 그 결과는 테이블에 저장하고 , 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

문제 제시 : 동전 거스름 돈 구하기
모든 동전의 단위가 배수의 성질인 경우 →,100,200,300 그리디의 성질을 이용가능
동전의 단위가 배수가 아닌경우 → 1,4 ,6 → 완전 탐색 필요하다.

재귀 : 함수에 대한 정의를 명확하게 !!

DP 접근 : 상향식
1원에 대한 최적해 → (선택) 2원에 대한 최적해 → (선택) 3원에 대한 최적해 → (선택)4원에 대한 최적해 .........
C[n] = n원을 거슬러 줄 때의 최적 ⇒ 동전 개수 ⇒ 동적 테이블 역활 (동적 테이블에 저장되는 값 의미!)

    package com.study37;

    import java.util.Arrays;
    import java.util.Scanner;

    public class DP1_MinCoinTest {

    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int money = sc.nextInt();
    		int[] D = new int[money+1];
    		
    		//D[i-1],D[i-4],D[i-6]
    		
    		D[0]=0;
    		for (int i = 1; i <= money; i++) {
    			int min = Integer.MAX_VALUE;
    			if(D[i-1]+1<min)//1원하나 쓰는 시도
    				min=D[i-1]+1;
    			
    			if(i>=4 && D[i-4]+1<min)//4원을 하나 쓰는 시도
    				min = D[i-4]+1;
    			
    			if(i>=6 && D[i-6]+1<min)//6원을 하나 쓰는 시도
    				min = D[i-6]+1;
    			
    			D[i] = min;
    		}
    		System.out.println(D[money]);
    		System.out.println(Arrays.toString(D));
    	}
    }

이항계수 구하기

0/1 KNapsac

배낭 문제를 DP로 접근해 보자

먼저 배낭 문제의 부분 문제를 찾아내기 위해 문제의 주어진 조건을 살펴보면

  • 물건, 물건의 무게, 물건의 가치, 배낭의 용량 모두 4가지의 요소가 있다.

⇒ 따라서 배낭 문제의 부분문제를 아래와 같이 정의 !

W = 배낭의 용량 (kg)

(v,W) = 가치(만원), 무게(kg) 물건

K[i,w] = 물건 1~ i까지만 고려하고, 배낭의 용량이 W일때의 최대 가치

K[i,w]를 재귀적으로 정리하면

배낭 문제의 부분 문제간의 함축적 순서는 2개의 부분문제가 미리 계산 되어 있어야지만 k[i,w]를 계산 가능하다.

배열을 하나를 이용하게 된다면 → 나의 최적해가 내 다음에 나오는 최적해가 나올 수 있다. → 따라서 바텀 업 방식을 사용하기 보다 탑다운 방식을 사용하면 해결 가능하다. (배열을 뒤쪽에서부터 채우면 해결 가능하다.)

최장 증가 수열

  • brute-force 접근 방법

    수열의 모든 부분집합을 구하여 그 부분집합이 증가 수열인지 판단 →

    길이가 긴것부터 확인 하는것이 효과적 →

    O(2^n) 시간 → N이 커지면 불가능

  • DP 접근 방법

    입력 : 숫자열 a....

    LIS(i):

  • DP접근 방법 2

lis [] 배열에 각위치를 LIS 길이로 할 떄 그자리에 올 수 있는 최솟값을 넣는다.→ 단 맨마지막값은 lis의 값과 일치한다.

이때 배열의 사이즈 값은 LIS의 값이고 해당 인덱스는 LIS를 길이로 할떄 그자리에 올 수 있는 최솟값을 가지고 있다.

- LIS[] 안에는 각 각 수를 끝에 세울 수 있는 최장길이 code

package com.study38;

import java.util.Scanner;

public class DP2_LISTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();//수열의 길이
		int[] arr = new int[N]; //수열의 값
		int[] LIS = new int[N]; //각 수를 끝에 세울 수 있는 최장길이/
		
		
		for (int i = 0; i < N; i++) {
			arr[i]= sc.nextInt();
		}
		int max = 0;
		for (int i = 0; i <N; i++) {
			LIS[i] = 1 ; //자기 혼자 세웠을때의 길이로 초기화 자신만으로 구성되는 lis
			for (int j = 0; j < i; j++) { //맨앞부터 자신의 직전 원소들과 비교
				if(arr[j]<arr[i] && LIS[i]<LIS[j]+1) {
					LIS[i]=LIS[j]+1;
				}
				
			}
			if(max < LIS[i]) max = LIS[i];
		}
		System.out.println(max);
	}

}

- LIS[] 안에는 각 수를 끝에 세울 수 있는 수의 값 ->배열의 사이즈가 최장길이

    package com.study39;

    import java.util.Arrays;
    import java.util.Scanner;

    public class DP3_LISTest2 {

    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		
    		int N = sc.nextInt();//수열의 길이
    		int[] arr = new int[N]; //수열의 값
    		int[] LIS = new int[N]; //각 위치 ==> LIS 길이를 만족하는 원소의 최소값
    		
    		
    		for (int i = 0; i < N; i++) {
    			arr[i]= sc.nextInt();
    		}
    		int size = 0;
    		for (int i = 0; i < LIS.length; i++) {
    			int temp = Arrays.binarySearch(LIS, 0, size, arr[i]);
    			temp = Math.abs(temp)-1; //중복값이 없으므로 탐색에 실패하고 음수값이 리턴
    			LIS[temp] = arr[i]; //맨뒤에 추가되거나 기존 위치에 덮어쓰거나
    			
    			if(temp == size) ++size;
    			
    		}
    		System.out.println(size);
    	}

    }

모든 쌍 최단 경로 (floyed warshall)

3중 포문 경유지 → 출발지 → 도착지 (경출도)

가중치 포함, 방향성 그래프에서 최단 경로 찾기

최적화 문제 → 주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때 이 가운데 가장 최적인 해답을 찾아야하는 문제

floyed warshall

동적 계획 알고리즘으로 모든 쌍 최단 경로 문제를 해결하려면 먼저 부분 문제들을 찾아야한다.

⇒ 일단 그래프의 정점의 수가 적을 때를 생각해보자

그래프에 3개의 정점이 있는 경우, 정점 i에서 정점 j 까지의 최단 경로를 찾으려면 2가지 경로 , 즉 정점 i에서 정점 j로 직접 가는 경로와 정점 1을 경유하는 경로 중에 짧은것을 선택

또하나의 중요한 아이디어는 경유 가능한 정점들을

정점1 로부터 시작하여 , 정점 1과 2 그다음엔 정점1,2,3,으로 하나씩 추가하여, 마지막에는 정점 1~n까지의 모든 정점을 경유 가능한 정점들로 고려하면서, 모든 상의 최단 경로의 거리를 계산한다.

  • 부분문제 정의 : 단 입력 그래프의 정점을 각각 1,2,3,````ㅜnd리하자
  • D = 정점 1,2,3~k만을 경유 가능한 정점들로 고려하여 , 정점 i로 부터 정점 j 까지의 모든 경로 중에서 가장 짧은 경로의 거리

⇒ 여기서 주의할 것은 정점 1에서 정점 K까지의 모든 정점들을 반드시 경류하는 경로를 의미하는것이 아니다 .

package com.study39;

import java.util.Scanner;

/*플로이드 : 모든 정점 간의 최소 비용
음수도 허용, 사이클 x
for 3개 사용
for 경유지 
	for 출발지
		for 도착지
*/
public class floydTest {
	static final int INF = 999;
	static int N, AdjMatrix[][];
	static String src = "5\r\n" + 
			"0 4 2 5 0\r\n" + 
			"0 0 1 0 4\r\n" + 
			"1 3 0 1 2\r\n" + 
			"-2 0 0 0 2\r\n" + 
			"0 -3 3 1 0";
	public static void main(String[] args) {
		Scanner sc = new Scanner(src);
		N = sc.nextInt();
		AdjMatrix = new int [N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				AdjMatrix[i][j] =sc.nextInt();
				
				if(i!= j && AdjMatrix[i][j]==0) {
					AdjMatrix[i][j]=INF;
				}
			}
		}
		System.out.println("입력값");
		print();
		
		//최소 비용 계산 하러 감 
		//경유지 -> 출발지 -> 도착지 
		for (int via = 0; via < N; via++) { // 경유지
			for (int from = 0; from < N; from++) {//출발지
				if(via==from) continue;
				
				for (int to = 0; to < N; to++) {//도착지
					if(via==from||via==to) continue;
					
					if(AdjMatrix[from][to] > AdjMatrix[from][via] +AdjMatrix[via][to]) {
						AdjMatrix[from][to] = AdjMatrix[from][via] +AdjMatrix[via][to];
					}
				}
			}
			print();
		}
		
	}
	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(AdjMatrix[i][j]+"\t");
				
			}
			System.out.println();
		}
		System.out.println("======================================");
	}
}
profile
코린이

0개의 댓글