공부 기록

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

위 문제와 완전 동일한 방법으로 풀면 됨

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t=in.nextInt();
		int n=in.nextInt();
		int A[]=new int[n];
		for(int i=0;i<n;i++) {
			A[i]=in.nextInt();
		}
		int m=in.nextInt();
		int B[]=new int[m];
		for(int i=0;i<m;i++) {
			B[i]=in.nextInt();
		}
		
		
		ArrayList<Integer> left=new ArrayList<Integer>();
		for(int i=0;i<A.length;i++) {
			int sum=0;
			for(int j=i;j<A.length;j++) {
				sum+=A[j];
				left.add(sum);
			}
		}
		ArrayList<Integer> right=new ArrayList<Integer>();
		for(int i=0;i<B.length;i++) {
			int sum=0;
			for(int j=i;j<B.length;j++) {
				sum+=B[j];
				right.add(sum);
			}
		}
		
		long ans=0;
		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == t) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < t) {
				leftIndex++;
			} else {
				rightIndex--;
			}
		}
		System.out.println(ans);
	}
	
}

앞선 글들과 마찬가지 방법으로 풀었는데 12%에서 시간 초과가 나서

아래와 같이 바이너리 서치 방법으로 풀었는데 75% 대에서 다시 시간초과가 났다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		ArrayList<Integer> aPizza = new ArrayList<Integer>();
		ArrayList<Integer> bPizza = new ArrayList<Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);
		aPizza.add(aSum);
		bPizza.add(bSum);

		Collections.sort(aPizza);
		Collections.sort(bPizza);

		long ans = 0;
		for (int sum : aPizza) {
			int cnt = binarySearch(bPizza, size - sum);

			if (cnt != -1) {
				ans += cnt;
			}
		}

		System.out.println(ans);
	}

	public static int binarySearch(ArrayList<Integer> list, int target) {
		int left = 0;
		int right = list.size() - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			mid = (left + right) / 2;

			if (target == list.get(mid)) {
				break;
			} else if (target < list.get(mid)) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}

		if (target == list.get(mid)) {
			int ans = 1;
			int index = mid - 1;
			while (index >= 0) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index--;
			}
			index = mid + 1;
			while (index < list.size()) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index++;
			}
			return ans;
		}

		return -1;
	}

	public static void findAllSums(int arr[], ArrayList<Integer> list) {
		int length = arr.length;
		
		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.add(sum);
				index++;

				if (index - i + 1 == length) {
					break;
				}
			}
		}
		list.add(0);

		return;
	}
}

LinkedList에서의 데이터의 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠른데,

LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다.

삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다.

반면 ArrayList의 경우 삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N) 의 성능을 내게 된다.

그래서 LinkedList로 바꿨는데 그래도 시간초과는 똑같음

이진 탐색에서 시간이 걸리는 것 같아서 HashMap에 나올 수 있는 피자의 넓이를 넣어놓고 바로 가져올 수 있도록 바꿨다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		HashMap<Integer, Integer> aPizza = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> bPizza = new HashMap<Integer, Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);

		aPizza.put(aSum, 1);
		bPizza.put(bSum, 1);
		aPizza.put(0, 1);
		bPizza.put(0, 1);

		long ans = 0;

		for (int sum : aPizza.keySet()) {
			int cnt = bPizza.getOrDefault(size - sum, -1);
			if (cnt != -1) {
				ans += cnt * aPizza.get(sum);
			}
		}

		System.out.println(ans);
	}

	public static void findAllSums(int arr[], HashMap<Integer, Integer> list) {
		int length = arr.length;

		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.putIfAbsent(sum, 0);
				list.replace(sum, list.get(sum) + 1);
				index++;

				if (index - i + 1 >= length) {
					break;
				}
			}
		}
		return;
	}
}

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

위 글과 마찬가지 방법으로 풀면 된다.

크기 N이 주어졌을 때, 배열 A, B, C, D가 주어지면

A[a]+B[b]+C[c]+D[d]==0인 a, b, c, d의 쌍을 구하는 문제이다.

4중 for문을 돌리면 O(N^4)만에 풀 수 있지만,

A[a]+B[b]와 C[c]+D[d]를 순차적으로 구한 뒤 합이 0인지 찾는다면 O(N^2)만에 풀 수 있다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		long A[] = new long[n];
		long B[] = new long[n];
		long C[] = new long[n];
		long D[] = new long[n];
		for (int i = 0; i < n; i++) {
			A[i] = in.nextLong();
			B[i] = in.nextLong();
			C[i] = in.nextLong();
			D[i] = in.nextLong();
		}

		long left[] = new long[n * n];
		long right[] = new long[n * n];
		int index = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				left[index] = A[i] + B[j];
				right[index] = C[i] + D[j];
				index++;
			}
		}

		Arrays.sort(left);
		Arrays.sort(right);

		long ans = 0;
		int leftIndex = 0;
		int rightIndex = n * n - 1;
		while (leftIndex < n * n && rightIndex >= 0) {
			long leftSum = left[leftIndex];
			long rightSum = right[rightIndex];
			if (leftSum + rightSum == 0) {
				long leftSame = 0;
				long rightSame = 0;
				while (leftIndex < n * n && leftSum == left[leftIndex]) {
					leftIndex++;
					leftSame++;
				}
				while (rightIndex >= 0 && rightSum == right[rightIndex]) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum > 0) {
				rightIndex--;
			} else {
				leftIndex++;
			}
		}
		System.out.println(ans);
	}
}

문제의 크기가 클 경우에는 문제를 절반으로 나누어서 문제를 푼 후 두 개를 합치는 방식을 이용한다.

배열의 크기가 N인 집합이 있을 때 부분집합의 합이 M이 나오는 갯수를 찾는 문제이다.

이 문제의 경우는 N<=40이고 모든 부분 집합을 만들면 2^40가지가 나오므로 모든 경우의 수를 파악할 수 없다.

따라서 문제의 크기를 절반으로 나누어서 한쪽 절반과 다른쪽 절반에서 각각 푼 다음에 문제를 합쳐서 풀도록 한다.

먼저 절반에서 구한 모든 값들을 list에 넣고 left list의 값과 right list의 값의 합이 s인 가짓수를 찾는다.

부분집합의 크기는 양수이므로 둘 다 0인 경우는 마지막에 빼준다.

import java.util.*;
import java.io.*;

public class Main {
	public static long ans = 0;
	public static int arr[];
	public static int n, s;
	public static ArrayList<Integer> left, right;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		s = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		left = new ArrayList<Integer>();
		right = new ArrayList<Integer>();

		findAllSums(0, 0, n / 2, left);
		findAllSums(0, n / 2, n, right);

		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == s) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < s) {
				// 찾으려고 하는 수는 더 크기 때문에 left를 오른쪽으로 한 칸 움직여준다.
				leftIndex++;
			} else {
				// 마찬가지로 rightIndex 한칸 왼쪽으로 움직여준다.
				rightIndex--;
			}
		}

		if (s == 0) {
			ans -= 1;
		}

		System.out.println(ans);
	}

	public static void findAllSums(int sum, int index, int end, ArrayList<Integer> list) {
		if (index == end) {
			list.add(sum);
			return;
		}

		findAllSums(sum + arr[index], index + 1, end, list);
		findAllSums(sum, index + 1, end, list);
	}
}

• python3

항공 규정 등에 대한 내용은 특정한 단어들 때문에 기존의 번역기의 성능이 좋지 못한 경향이 있다.

항공 규정에 대한 올바른 번역 쌍을 데이터베이스에 저장하고, 가변 데이터나 오탈자가 들어가더라도 90%이상 데이터베이스에 유사한 cell이 있는 경우 이를 활용하도록 하고, 새로운 내용에 대한 input이 들어올 경우 머신 러닝을 활용하여 번역하도록 한다.

데이터베이스에는 또한 문장에서 추출한 키워드 10개가 (문장, 키워드들)의 쌍으로 저장되어 있다. 

유사도를 계산할 때에는 이 키워드를 가지고 계산한다. 

input data의 경우 구두점이 존재하지 않거나 줄 바꿈이 일어나지 않는 경우도 많아 머신 러닝 번역의 경우 정확도가 낮게 나오는 문제점이 있으므로, 기존 데이터베이스를 활용하여 특정한 단어가 문장의 처음에 나올 확률/문장의 마지막에 나올 확률 등을 계산하여 문장 segmentation을 진행한다.

문장 segmentation 이후 seq2seq를 적용한 모델을 활용하여 번역한다. (seq2seq with attention model)

성능을 높이기 위해 추가적으로 정규표현식 및 기존의 seq2seq with attention 모델에 domain adaption과 fine-tuning을 적용했다.

항공 corpus는 양이 매우 적기 때문에 overfitting이 발생했고, 주어진 corpus와 다른 형식의 문장은 전혀 번역하지 못하는 문제점이 있었다. 따라서 대량의 일반 corpus와 항공 corpus로 seq2seq 모델을 학습시켰다. 그리고 결과 모델을 항공 corpus 만으로 fine-tuning하여 번역 가능한 문장을 일반화 시켰다.

seq2seq는 시계열 데이터(sequence data)를 다른 종류의 시계열 데이터로 바꿔주는 모델로 기계 번역에 자주 사용된다.

• encoder: 입력 시계열 데이터를 LSTM에서 순차적으로 처리하여 하나의 벡터 형태로 정보를 압축한다. 마지막 단어를 입력받은 LSTM의 last hidden laer vector는 context vector로 decoder에 전달된다.
• decoder: 이전 단계의 LSTM hidden layer vector와 이전 단계의 예측 단어 vector를 입력으로 받는다. LSTM에서 반환된 전체 단어 수에 대응되는 shape으로 바뀐다. softmax를 통과하면 각 단어에 대한 확률값을 저장하는 vector로 바뀐다. 가장 높은 값을 갖는 인덱스에 대응되는 단어가 번역된 단어이다.

즉, 인코더는 번역할 문장의 정보를 압축하여 디코더로 보내고, 디코더는 인코더에서 받은 정보와 각 단계에서 예측한 단어들로 다음 단어를 예측한다고 할 수 있다.

attention seq2seq 모델은 seq2seq의 디코더에서 인코더의 hidden layer vector들을 참고하여 단어를 예측하는 모델이다.

• 디코더의 현재 단계의 LSTM이 반환한 vector가 query가 된다.
• 입력 데이터의 각 단어별로 LSTM 마지막 hidden layer vector들이 key 값이자 value 값이 된다.
• query를 각 key 값들을 dot product 하여 vector 쌍들의 유사도를 얻는다.
• 유사도 값들이 softmax를 거치면 어텐션 가중치(attention weight)가 된다. 이들은 각 입력 단어들과 디코더가 예측할 단어의 유사도를 의미한다.
• 어텐션 가중치를 value 값들에 곱하고 모두 더하면 예측할 단어와 유사도가 높을 수록 값이 더 많이 반영된 attention value가 된다.
• 디코더로 돌아와 attention value와 LSTM가 반환한 벡터를 concat한다.

즉, attention이란 인코더의 입력 데이터드로가 현재 예측해야 할 단어의 유사도를 구하여 유사도가 높은 입력 데이터들에 큰 비중을 두어 참고하는 방법이다.

이 프로젝트에서 어려웠던 점은 input이 문장단위로 들어오는 것이 아니라 1줄 당 64바이트로 이루어진 스트림으로 들어오기 때문에 문장의 단위를 나누고 이를 번역기에 넣는 것이 가장 어려웠다. 또한, 일반적인 문서에서 찾아볼 수 없는, 문장의 구두점이 없는데도 문장의 의미가 나누어져서 문장 segmentation을 어떻게 해야할 것인지 많은 고민을 해야 했다.

뿐만 아니라, regular expression을 이용한 가변 데이터를 처리할 때, 화폐, 퍼센트, 기간, 날짜, 서수 등에 대한 내용에 대해 가변 데이터 전처리를 하는데 그 모양이 너무 다양하여 예외 케이스가 많은 점이 어려웠다.

keyword matching을 알아보기 위해 데이터베이스에서 유사한 번역 쌍을 찾을 때에도 데이터베이스 전체 조회에 대한 시간이 오래 걸려서 문제가 됐다. 이는 처음에 데이터베이스 전체를 조회하여 캐싱해두고 input cell 이 들어올 때마다 캐싱 된 데이터베이스 테이블의 키워드와 인풋 cell의 키워드를 각각 full-scanning하며 비교하도록 함으로써 해결했다.

https://aiyprojects.withgoogle.com/voice/

• google AIY voice kit 를 사용해서 음성 인식 스피커를 만드는 프로젝트
• python3, raspberry pi Zero

스피커의 버튼을 눌러서 구글 어시스턴트로 시작하여 '내 얘기를 들어봐', '얘기 들어 줘' 등으로 듣기 모드 진입 후,

'들어줄게 얘기해 봐', '무슨일이야?' 등을 랜덤 재생한다.

사용자가 말하는 내용의 긍/부정/중립 또는 사용자의 목소리에서 긍/부정/중립을 판단하여

그에 맞는 반응 (7가지 중 하나)를 해 준다.

듣기 모드에서 '들어줘서 고마워', '내 얘기 들어줘서 고마워', '잘가', '어시스턴트' 등으로 어시스턴트 모드 복귀

이 프로젝트에서 어려웠던 점은 음성 자체의 긍/부정/중립 분석을 처음에는 google cloud speech API만 사용해서 했는데,

결과를 내는 데 시간이 오래 걸려서 사용자와 대화가 원활히 진행되지 못하고 지연 시간이 생기는 문제점이 있었다.

오픈 소스를 구글링 해 보니 텍스트의 감정 분석을 해 주는 것이 있었다.

그래서 상대적으로 지연 시간이 없는 google text to speech API를 사용하여 텍스트의 긍/부정/중립 분석을 하도록 했다.

이후 오픈소스를 사용하려고 했는데,

raspberry pi Zero 환경에 맞지 않아 Vokaturi drive를 활용하여 오픈 소스를 사용할 수 있도록 스피커에 코드를 이식 했다.

google text to speech API가 속도는 더 빨랐으나, 정확도는 google cloud speech API가 더 높았기 때문에

텍스트 감정 분석에 sentiment의 score와 magnitude 값을 보고,

즉 감정 분석 결과 충분히 긍/부정으로 치우쳐져 있으면 google text to speech API로 분석을 끝내고,

판단하기 어렵다면 google cloud speech API를 사용하여 조금 더 정확하게 감정 분석을 할 수 있도록 했다.

https://github.com/timedilation/ZASP/tree/master/emotion_analyze_aiy

그래프에서 사이클의 길이 중 최소 길이를 찾는 문제이다.

d[i][i]를 무한대로 초기화해 준 뒤 플로이드 알고리즘을 적용하면 i->i로 가는 어떠한 경로 중 최소 길이를 얻을 수 있다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][k] != Integer.MAX_VALUE && mat[k][j] != Integer.MAX_VALUE) {
						mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
					}
				}
			}
		}

		int min = mat[1][1];
		for (int i = 2; i <= n; i++) {
			min = Math.min(min, mat[i][i]);
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		System.out.println(min);
	}
}

플로이드 알고리즘의 결과가 주어졌을 때,

가능한 경우의 그래프의 최소 간선 수를 구하고, 모든 도로의 cost 합을 구하는 문제이다.

원래 플로이드 알고리즘은

• i->j로 가는 비용이 x보다 클 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로의 cost를 x로 바꿔준다

이 것을 반대로 적용해보면

• i->j로 가는 비용이 x일 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로는 필요없다.

입력이 이미 최단경로가 주어져있는데 다시 최단경로를 계산해보니 더 짧아진 경우는 입력이 모순이 되므로 -1을 출력하도록 했다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int ans = 0;
		boolean isEdge[][] = new boolean[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(isEdge[i], true);
		}

		Floyd: 
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				if (k == i) {
					continue;
				}
				for (int j = 1; j <= n; j++) {
					if (k == j || i == j) {
						continue;
					}

					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						ans = -1;
						break Floyd;
					}

					if (mat[i][j] == mat[i][k] + mat[k][j]) {
						isEdge[i][j] = false;
						isEdge[j][i] = false;
					}
				}
			}
		}

		if (ans != -1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (isEdge[i][j]) {
						ans += mat[i][j];
					}
				}
			}
			ans /= 2; // 양방향이므로 2로 나눠준다.
		}
		System.out.println(ans);
	}
}