내일은 알고리즘

https://www.acmicpc.net/problem/18248

상당히 재밌는 문제였습니다. 

얼핏보면 이게 뭔소리지 싶은 문제일 수도 있습니다.

하지만 소리가 발생한 지점으로부터 원형으로 퍼져나간다는 사실을 생각해보면 쉽게 풀이방법을 알아 낼 수 있습니다.

주어진 예제가 너무 단편적이니 제가 직접 예제를 만들어 보겠습니다.

10 5
1 0 1 0 1
0 0 0 0 0
0 0 1 0 0
1 0 1 0 1
1 0 1 0 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 0 0

조건에 성립하는 예제라고 가정하고, 이 예제를 시각적으로 나타내 볼까요?

네, 그림을 보고 슬슬 느끼셨을것 같은데요.

이 문제는 정렬 문제입니다.

소리가 원형으로 퍼지기 때문에 바깥 사람이 들은 종소리를 더 가까운 사람은 무조건 들을 수 밖에 없죠.

따라서 종소리를 들은 숫자대로 사람들을 내림차순으로 정렬한다면,

안의 사람이 듣지 못한 종소리를 더 바깥에 있는 사람이 듣는 일은 없습니다.

(안의 사람이 들은 종소리를 바깥사람이 못듣는 경우는 당연히 존재합니다.)

예시를 살짝 바꿔 볼까요??

10 5
1 0 1 0 1
0 0 0 0 0
0 0 1 0 0
1 0 1 0 1
1 0 1 0 0
0 0 1 0 0
1 0 1 0 0
0 1 0 0 0
1 0 1 1 1
0 0 1 0 0

만약 바꾼 예시처럼 8번 사람이 아무도 듣지 못한 2번 종소리를 들었다고 가정해 봅시다.

그럼 8번은 다른 모두보다 종에 가까이 있어야 하는데, 그렇다면 다른 종소리도 자연스럽게 듣게 됩니다.

옳바른 예시와 잘못된 예시를 정렬 해보면 이렇게 되겠네요.

옳은 예

10 5

1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0
0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

틀린 예

10 5

1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0
0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 1 0 0 0

0 0 0 0 0

모순관계가 생기면 문제에서 주어진 예시 2번 처럼 어떻게든 0->1로 바뀌는 모습이 나타날 수 밖에 없습니다.

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] people = new int[N][M + 1];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			int sum = 0;
			for (int m = 0; m < M; m++) {
				people[n][m] = Integer.parseInt(st.nextToken());
				sum += people[n][m];

			}
			people[n][M] = sum;
		}

		Arrays.sort(people, (e1, e2) -> {
			return e2[M] - e1[M];
		});

		boolean answer = true;

		loop: for (int m = 0; m < M; m++) {
			int check = people[0][m];
			for (int n = 0; n < N; n++) {
				if(check < people[n][m]) {
					answer = false;
					break loop;
				}
				check = people[n][m];
			}
		}

		if (answer) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

https://www.acmicpc.net/problem/4600

(문제가 무척 길어서 스크린샷은 생략..)

대학교 후배가 실버도장깨기를 하다가 막혔다며 SOS를 친 문제다.

자신만만하게 OK사인을 보내고 문제를 풀러갔다가, 100명도 되지 않는 적은 정답자 수에 놀라고 어마어마하게 긴 문제의 길이에 놀라고 불친절한 Input에 놀라고... 아무튼 생각보다 난이도 있는 문제였다.

처음에는 각 나무를 일종의 PriorityQueue처럼 보고 가능한 경우의 수를 모두 계산해서 최적해를 구하는 식으로 짜려고 했는데, 예외와 조건이 너무 많아서 불가능했다.

다른 후배도 같이 도전하던 와중에 그 친구가 먼저 정답을 통과했고, 전체적인 시간을 가지고 관리한다는 tip과 놓치고 있던 조건(최적해를 위해 기다리는것이 금지된다. 건널 수 있으면 바로 건넌다.)을 듣고 바로 구현을 마칠 수 있었다.

나무에 대기하고 있는 사람과

다리를 건너고 있는 사람

두개의 데이터를 가지고 가장 시간이 적게 걸리는 그룹이 다리를 건너는 시점마다를 트리거로 동작시켜서

빈 다리에 건널 사람이 있다면 채워 넣고, 다리를 건너는 그룹들은 남은 시간을 줄이는 식으로 구현했다.

코드는 이렇다.

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

public class Main {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			st = new StringTokenizer(br.readLine());
			int B = Integer.parseInt(st.nextToken())*-1;
			int P = Integer.parseInt(st.nextToken());

			if (B == 0 && P == 0) {
				break;
			}
			int[] trees = new int[B + 1];
			trees[0] = P;
			trees[B] = -P;
			int[][] bridges = new int[B][2];
			int[][] groups = new int[B][2];
			int totalTime = 0;

			for (int b = 0; b < B; b++) {
				st = new StringTokenizer(br.readLine());
				bridges[b][0] = Integer.parseInt(st.nextToken());
				bridges[b][1] = Integer.parseInt(st.nextToken());
			}

			while (trees[B] < 0) {
				int time = Integer.MAX_VALUE;
				for (int b = 0; b < B; b++) {
					if (trees[b] > 0 && groups[b][0] == 0) {
						groups[b][0] = Math.min(trees[b], bridges[b][0]);
						groups[b][1] = bridges[b][1];
						trees[b] -= groups[b][0];
					}
					if (groups[b][1] > 0) {
						time = Math.min(groups[b][1], time);
					}
				}

				totalTime += time;

				for (int b = 0; b < B; b++) {
					if (groups[b][1] > 0) {
						groups[b][1] -= time;
						if (groups[b][1] == 0) {
							trees[b + 1] += groups[b][0];
							groups[b][0] = 0;
						}
					}
				}
			}
			sb.append(totalTime).append("\n");
		}

		System.out.println(sb);
	}
}

https://www.acmicpc.net/problem/2565

백준 사이트의 2565번 전깃줄이라는 문제입니다.

문제 설명은 간단하지만 막상 풀이 방법을 떠올리려면 떠오르지 않는 문제입니다.

솔직히 말하면 저도... 검색을 통해 다른 사람들의 풀이를 보고 풀었는데, 이 문제는 LIS(Longest Increase Subsequence)의 응용문제로 DP와 이분 탐색 두 가지의 방법으로 풀이가 가능합니다. 

DP의 경우 구현과 이해가 쉽지만 입력의 갯수가 많으면 시간 초과로 문제를 틀릴 가능성이 있다는데,

마침 문제가 입력의 갯수가 100개인 전깃줄 1과 10만 개인 전깃줄 2로 나뉘어 있으니 두 가지 방법을 각각 활용해서 풀어보도록 하겠습니다. 먼저 DP를 활용한 풀이 방법을 보겠습니다.

개념은 간단합니다, 전깃줄이 같은 곳에 걸쳐있지 않는다는 조건을 활용하여 입력을 정렬하고, 사용할 전깃줄의 갯수를 하나씩 늘려가며 전깃줄의 부분집합이 만들 수 있는 최댓값을 기록합니다. 이때 구한 최댓값을 DP 배열에 저장하고, 다음 풀이에서 활용할 수 있습니다.

예제 입력을 통해 확인해 보겠습니다.

(1,8), (3,9), (2,2) ,(4,1), (6,4), (10,10), (9,7), (7,6) 이렇게 8개의 전깃줄이 들어왔습니다.

이를 전깃줄의 시작 위치를 기준으로 정렬하면

(1,8), (2,2) ,(3,9), (4,1), (6,4), (7,6), (9,7), (10,10)와 같은 형태가 됩니다. 진행 방향은 상관이 없지만, 저는 뒤에서부터 쌓아가며 진행하도록 하겠습니다.

(10,10) 하나를 추가하고 -> 이때의 LIS길이는 당연히 1이 됩니다.

(9,7)를 추가하고 -> 9,7 전깃줄과 10,10 전깃줄은 겹치지 않으므로 아까 구한 LIS 길이에 1을 더해 2가 됩니다.

같은 방법으로 (4,1), (6,4), (7,6), (9,7), (10,10) 까지는 전깃줄이 겹치지 않고 LIS길이가 계속 늘어 5가 됩니다.

이 상태에 (3,9) 전깃줄을 추가하면 겹치는 부분이 발생하게 됩니다.

겹치는 영역은 (4,1), (6,4), (7,6), (9,7) 네 전깃줄로 (3,9)와 공존이 가능한 전깃줄은 (10,10) 뿐이고 그때의 LIS 길이에 1을 더한 2가 (3,9)를 포함한 LIS의 길이가 됩니다.

같은 방법으로 (2,2)를 추가했을때는 (2,2)다음으로 올 수 있는 전깃줄이 (6,4)로 (6,4)때 구한 값 4에 1을 더한 5를 얻고

(1,8)을 추가했을때는 (1,8), (3,9), (10,10)의 LIS가 구해집니다.

모든 경우에서 최댓값을 찾으면 예제에서 구할 수 있는 LIS의 길이는 5로 두가지 경우인 것을 알 수 있습니다.

이를 코드로 구현하면,

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[][] wires = new int[N][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			wires[n][0] = Integer.parseInt(st.nextToken());
			wires[n][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(wires, (e1, e2) -> {
			return e1[0] - e2[0];
		});

		int[] dp = new int[N];

		for (int n = N - 1; n >= 0; n--) {
			dp[n] = 1;
			int end = wires[n][1];
			for (int m = n; m < N; m++) {
				if (wires[m][1] > end) {
					dp[n] = Math.max(dp[n], 1 + dp[m]);
				}
			}
		}

		int max = 0;

		for (int n = 0; n < N; n++) {
			max = Math.max(max, dp[n]);
		}

		System.out.println(N - max);

	}
}

이렇게 작성 할 수 있을것 같습니다. 감사합니다.

곧 전깃줄2 문제도 풀도록 하겠습니다.

https://www.acmicpc.net/problem/1958

계속 이어서 LCS의 세 번째 문제입니다.

LCS를 충분히 이해했다면 쉽게 접근이 가능합니다.

최소공배수처럼 접근해서 두 문자열의 LCS를 먼저 구하고, 구한 문자열과 비교하면 구현이... 틀립니다!

예외가 존재하기 때문인데, 쉽게 생각해 낼 수 있는 예외는 

처음 구한 LCS와 길이가 같은 다른 문자열이 존재하는 경우도 있을 것 같고, 3개 문자열의 LCS가 두 문자열의 LCS와 다른 문자를 갖는 경우도 있을 것 같네요.

AAAAAAAD

ADAAAAA

AD

3개의 문자열이 있을 때 세 문자열의 LCS는 AD가 되겠지만 1번과 2번 문자열의 LCS는 AAAAAA가 되어 두 문자열의 LCS를 먼저 구할 경우 오답이 나오게 됩니다.

그럼 어떻게 구현해야할까요?

LCS를 구하던 방법과 똑같이 하되, 문자열이 세 개가 되었으니 3차원 배열로 확장해서 구현하면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] str1 = br.readLine().toCharArray();
		int l1 = str1.length;
		char[] str2 = br.readLine().toCharArray();
		int l2 = str2.length;
		char[] str3 = br.readLine().toCharArray();
		int l3 = str3.length;

		int[][][] dp = new int[l3 + 1][l2 + 1][l1 + 1];

		for (int i = 1; i <= l3; i++) {
			char c3 = str3[i - 1];
			
			for (int j = 1; j <= l2; j++) {
				char c2 = str2[j - 1];
				
				for (int k = 1; k <= l1; k++) {
					if (c3 == c2 && c2 == str1[k - 1]) {
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					} else {
						dp[i][j][k] = Math.max(dp[i][j][k - 1], Math.max(dp[i - 1][j][k], dp[i][j - 1][k]));
					}
				}
			}
		}
		System.out.println(dp[l3][l2][l1]);
	}
}

바로 이렇게요.

감사합니다!

(String의 순서를 거꾸로 비교한 건 LCS 1번, 2번에서 사용한 코드를 수정해서 작성했기 때문입니다! index만 맞는다면 어떤 식으로 반복문을 작성해도 상관없습니다.)

https://www.acmicpc.net/problem/9252

LCS 2번을 풀어보겠습니다.

혹시 LCS에 대한 이해가 부족하시거나, LCS 1번 문제를 아직 풀지 않은 분은

https://nodingco.tistory.com/9

이 글을 확인해주시면 감사하겠습니다.

문제는 LCS 1번과 아주 유사합니다. 하지만 단순히 LCS의 길이를 구하는 것 뿐 아니라 LCS의 내용까지 구해야합니다.

쉽게 생각하면 그저 LCS를 구하는 기존의 과정에 더해 여태까지의 String을 저장해도 될 것 같지만, String이 메모리나 연산시간을 많이 잡아먹는걸 감안하면 살짝 위험해 보입니다.

그래서 LCS를 구했던 과정을 역산해서 LCS를 알아내 보겠습니다.

예제의 풀이과정이 기록되는 DP 배열을 실제 표로 나타내어 봅시다. (실제로는 계산의 편의를 위해 좌측과 상단에 0이 들어간 배열이 더 존재합니다.)

정답 LCS인 ACAK는 위와같은 과정을 통해 구해졌다는걸 알 수 있고

최종 정답이 위치한 DP[L2][L1]의 값부터 역순으로 찾아 가는 방법도 알 수 있습니다.

위, 좌측, 대각선 좌상방향 세개의 값을 비교하여

나와 같은 값이 있으면 그 쪽으로, 나와 값이 전부 다를땐 좌상방향으로 이동하면서

그때의 Character를 역순으로 담으면 자연스럽게 답이 찾아집니다.

Stack을 이용해 역순으로 저장하는 방법을 구현하면, 코드는 아래와 같아집니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<Character>();

		char[] str1 = br.readLine().toCharArray();
		int l1 = str1.length;
		char[] str2 = br.readLine().toCharArray();
		int l2 = str2.length;

		int[][] dp = new int[l2 + 1][l1 + 1];

		for (int i = 1; i <= l2; i++) {
			char C = str2[i - 1];
			for (int j = 1; j <= l1; j++) {
				if (C == str1[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}
		sb.append(dp[l2][l1]).append("\n");

		int now = dp[l2][l1];
		int x = l2;
		int y = l1;

		while (isIn(x, y) && now > 0) {
			if (dp[x - 1][y] == now) {
				x--;
			} else if (dp[x][y - 1] == now) {
				y--;
			} else {
				x--;
				y--;
				now--;
				stack.push(str1[y]);
			}

		}

		while (!stack.isEmpty()) {
			sb.append(stack.pop());
		}

		System.out.println(sb);
	}

	static boolean isIn(int x, int y) {
		if (0 < x && 0 < y) {
			return true;
		}
		return false;
	}
}

주의)

LCS가 0일때 아무것도 출력하지 않아야합니다.

탐색 도중 x와 y가 ArrayIndex를 벗어나는걸 주의해주세요.

https://www.acmicpc.net/problem/9251

안녕하세요!

오늘부터 LCS(최장 공통부분 수열) 문제 3개를 연속으로 풀어보겠습니다!

부분 수열 문제지만 오늘 가져온 9251번 문제처럼 String을 찾는 유형으로도 나오는데요,

0-1 배낭 문제 (Knapsack Problem)과 더불어서 DP의 대표 유형 격인 문제입니다.

그럼 천천히 풀어보겠습니다.

예제를 기준으로 함께 풀어보겠습니다. 

DP의 풀이방법은 정말 다양하고, Dynamic Programming이란 말 그대로 모든 게 가능하기 때문에 딱 잡아 말할 순 없지만, 분할 정복과 유사하게 문제를 잘게 쪼개어 그 결과를 기억하고 이를 통해 답을 만들어낸다고 볼 수 있습니다.

LCS문제도 같습니다.

ACAYKP를 String1이라고 하고 이걸 기준으로 놓고 아래의 CAPCAK, String2 의 부분수열을 만들어서 비교해보면,

1. C 일때

A-> 0

AC -> 1

ACA-> 1

ACAY ->1

ACAYK ->1

ACAYKP ->1

String2가 C라고 가정했을 때 만들 수 있는 LCS는 길이가 1이라는 사실을 알 수 있습니다.

2. CA 일 때

A->1

AC -> 1   (A도 가능하지만 가독성과 이해를 위해 C를 bold 처리했습니다.)

ACA -> 2

ACAY ->2

ACAYK ->2

ACAYKP ->2 String2가 CA일때 만들 수 있는 LCS는 2의 길이라는 사실을 알 수 있습니다.

3. CAP 일때

A-> 1

AC -> 1

ACA-> 2

ACAY ->2

ACAYK ->2

ACAYKP ->3

두번째 String이 CAP일 때 LCS는 길이가 3입니다.

슬슬 규칙이 보이시나요? 비교하는 String이 길어질 때,

LCS의 값은 이전에 이 길이까지와 비교한 값과 같거나, 이번에 비교하면서 만들어진 현재의 LCS값이거나,

String1의 이번 Character와 String2에 방금 더해진 문자가 같을 때 1이 커집니다.

이걸 코드로 표현해 보면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main{
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		int l1 = str1.length();
		String str2 = br.readLine();
		int l2 = str2.length();
		
		int[][] dp = new int[l2+1][l1+1];
		
		for(int i = 1; i <= l2; i++) {
			char C = str2.charAt(i-1);
			for(int j = 1; j <= l1; j++) {
				if(C == str1.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}else {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
				}
			}
		}
		System.out.println(dp[l2][l1]);
	}
}

이렇게 나타낼 수 있을것 같네요.

위에서 설명한 것과 같이 String2의 길이를 1씩 늘려가면서 String1과 비교해주고

이번에 비교하는 문자가 같다면 LCS의 값은 이전 비교에서 1만큼 짧았을때의 최댓값 + 1

다르다면 이전 비교에서의 값과 이번 비교에서의 값 중에 큰 값으로 결정됩니다.

대부분의 DP문제는 아이디어를 끌어내기가 어렵지, 풀이 방법만 안다면 구현은 쉬운 경우가 많습니다.

DP를 잘 풀기 위해서는 역시 여러 유형을 경험해 익숙해지고 직접 그려가면서 규칙을 찾아내는 방법 뿐 입니다.

이어서 거의 비슷한 문제인 LCS2도 풀어보겠습니다.

안녕하세요!

드디어 SSAFY 1년 과정이 거의 마무리 되었고, 시간이 꽤 생길것 같기 때문에!

본격적으로 블로그에 포스팅을 작성하게 되었습니다.

제가 알고리즘 문제풀이 (Problem Solving)에 주로 사용하는 언어는 JAVA이지만

C++. Python 등으로도 종종 풀이가 올라갈 것 같습니다.

https://www.acmicpc.net/problem/1000

아주 간단한 문제입니다.

백준에서 가장 많은 제출이 이루어진 문제기도 하고, 브론즈~실버 등급 대표 문제들의 정답률이 50%는 가뿐히 넘기는걸 생각하면 생각보다 정답률이 낮은 문제기도 합니다.

1000번 문제를 틀리는 이유는 여러개가 있습니다.

1. 진짜 프로그래밍 언어에 대해 하나도 모른다. 

2. 테스트케이스의 존재를 모르고 3을 출력하는 프로그램을 작성한다.

3. 자신이 작성한 언어가 아닌 다른 언어로 제출한다.

4. Main 함수, 또는 클래스의 이름을 잘못 설정한다.

5. 코드를 붙여넣는 과정에서 package, import등을 누락한다.

아무튼..

문제는 아주 간단합니다. 두개의 숫자를 입력받고, 덧셈연산의 결과값을 출력하면 됩니다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		System.out.println(a+b);
	}
}

이렇게요.

java 라이브러리 util 패키지의 Scanner 클래스를 import해주고

시스템의 입력인 System.in을 parameter로 새로운 Scanner 객체를 생성해주면 됩니다.

Scanner의 이름은 어떻게 정하셔도 상관없지만, 가독성과 다른 사람에게 코드를 공유할 때를 대비해 많이 사용하는 이름으로 선언해주시는게 좋습니다.

보통 기능적인 요소에서 따온 input, in 을 쓰기도 하고 Scanner 객체는 한 번 선언하고 계속 재사용하기 때문에 간단하게 scan, sc로 선언하기도 합니다. 

Scanner 클래스 안에는 여러가지 메소드가 들어있는데요.

간단한 문제이므로 입력으로 들어오는 다음 숫자를 반환하는 nextInt()를 통해 A와 B값을 받고

JAVA의 기본적인 출력함수인 System.out.println()을 통해 A+B를 출력했습니다.

조금 더 효율적인 입출력을 하고싶다! 하시는 분은

https://nodingco.tistory.com/7

이 글을 참고해주시면 감사하겠습니다!