내일은 알고리즘

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

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

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

public class Main {
	static StringTokenizer st;
	static int[] parent;

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

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

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}

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

또 다른 투 포인터 문제입니다. 

정확히는 슬라이딩 윈도라고 할 수 있겠네요. 

기본적인 투 포인터가 데이터의 양 쪽 끝에서 좁혀 들어오면서 탐색한다면, 슬라이딩 윈도는 한쪽 끝에서 시작해서 연속된 특정 범위를 찾습니다.

조금 더 상세히 설명해 볼까요?

N길이의 수열에서 연속된 부분을 구한다는 것은, 연속된 부분합의 시작점과 끝점을 정한다는 뜻입니다.

즉 N*N개의 경우가 존재한다는 뜻입니다.

슬라이딩 윈도우는 이 시작점과 끝점을 모든 경우에 대해 계산해보지 않고, 현재 부분에서 조건보다 작으면 연속된 부분을 늘리고 크면 연속된 부분을 줄이면서 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 S = Integer.parseInt(st.nextToken());

		int[] num = new int[N];

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

		int left = 0;
		int right = 1;
		int sum = num[0];
		int answer = 100_001;

		while (left < N) {
			if (sum >= S) {
				answer = Math.min(answer, right - left);
				sum -= num[left];
				left++;
			} else {
				if (right == N) {
					break;
				} else {
					sum += num[right];
					right++;
				}
			}
		}
		if(answer == 100_001) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}

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

정석적인 투포인터 문제입니다.

투포인터 알고리즘에 대해선 나중에 포스팅을 작성해 보도록 하겠습니다.

투포인터 알고리즘을 통해 절댓값이 0에 가장 가까운 두개의 특성값을 기록하고 출력하면 간단히 풀립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] num = new int[N];
		int value = Integer.MAX_VALUE;
		int[] answer = new int[2];

		st = new StringTokenizer(br.readLine());

		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = N - 1;

		while (left < right) {
			int sum = num[left] + num[right];
			int abs = Math.abs(sum);

			if (abs < value) {
				value = abs;
				answer[0] = num[left];
				answer[1] = num[right];
			}

			if (sum <= 0) {
				left++;
			} else {
				right--;
			}

		}
		System.out.println(answer[0] + " " + answer[1]);
	}
}

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

신발끈 공식을 이용한 문제입니다.

고등학교때 배웠는지, 대학와서 선형대수학에서 배웠는지 모르겠지만...

워낙 간단하고 유용한 공식이라 아직 머릿속에 남아있어서 쉽게 해결했습니다.

공식에 대해 잘 모르시는 분은 아래의 킹무위키를 참고해 보셔도 될 것 같습니다! 흐흐...

https://namu.wiki/w/%EC%8B%A0%EB%B0%9C%EB%81%88%20%EA%B3%B5%EC%8B%9D

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		long[][] points = new long[N + 1][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			points[n][0] = Long.parseLong(st.nextToken());
			points[n][1] = Long.parseLong(st.nextToken());
		}
		points[N] = points[0].clone();

		long sum1 = 0L;
		long sum2 = 0L;

		for (int n = 0; n < N; n++) {
			sum1 += points[n][0] * points[n + 1][1];
			sum2 += points[n][1] * points[n + 1][0];
		}

		System.out.println(String.format("%.1f", Math.abs(sum1 - sum2) / 2D));
	}
}

입력의 범위가 10만이고, 둘을 곱하면 int의 크기를 넘어가는 것만 주의하시면 쉽게 풀 수 있습니다!

저는 눈치 못채서 걸렸습니다!! 으아아악!!

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

처음 문제를 보고, 뭐지 하는 생각이 들었습니다.

문제의 지문 자체는 간결하고 이해도 되는데 이 문제를 어떻게 구현할지 엄두가 안 나더라고요.

그나마 추측할 수 있는 부분은 입력의 크기가 고정되어있고 10x10 사이즈로 작다 보니 완전탐색으로 될 것 같다 정도였습니다. 고민을 좀 해봤지만 명쾌한 아이디어가 안 떠올라, 검색을 통해 접근 법을 찾았고 구현 자체는 어렵지 않았습니다.

핵심아이디어는 이것입니다.

한 줄씩 불꺼진 상태를 고정시키자.

불 켜진 줄을 누르게 되면, 좌 우의 전구가 동시에 on off되기 때문에 확실하게 불이 꺼진 줄을 만드는 방법은 해당 줄의 위나 아래의 전구를 누르는 것 뿐입니다.

이 방법을 9개의 줄에 적용합니다.

이제 1~9번줄의 전구는 모두 꺼졌다는 명제는 자명합니다. 따라서 10번째 줄의 전구만이 켜져있을 가능성이 있습니다.

10번째 줄의 전구가 모두 꺼졌다면 모든 전구가 꺼져있는 상태입니다.

여기서 우리는 의문을 갖습니다.

위에서 생각한 방식을 그리디하게 적용하면 놓치는 케이스가 생기지 않을까?

네! 놓치는 경우가 생깁니다!

첫 번째 줄의 현재 상태에서만 그리디하게 진행하면 불을 다 끌수 있는데도 놓치는 경우가 생깁니다. 그렇다고 모든 전구에 대해 가능한 경우를 계산하면 2^100가지의 경우가.. 각 케이스마다 적용해야 하는 추가연산이 있는데 10억개의 경우는 너무 가혹합니다.

하지만, 위의 방식을 잘 생각해보면 첫 줄의 전구 상태에 따라 다음 작업들은 종속적으로 일어남을 알 수 있습니다.

따라서 우리가 찾아봐야 할 경우의 수는 첫번째 줄에서 일어날 수 있는 모든 경우인 2^10가지, 1024가지에 불과한것입니다.

1024가지 경우를 모두 돌려보는데엔 여러 방법이 있을텐데,

저는 개인적으로 비트마스킹 기법에 꽤나 익숙한 터라 해당 방법을 통해 구현했습니다.

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

public class Main {
	static int answer = Integer.MAX_VALUE;
	static int[][] delta = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static boolean[][] testmap = new boolean[10][10];

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

		boolean[][] map = new boolean[10][10];

		for (int n = 0; n < 10; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < 10; m++) {
				if (line[m] == 'O') {
					map[n][m] = true;
				}
			}
		}

		for (int i = 0; i < 1024; i++) {
			copy(map);
			int count = 0;

			for (int j = 0; j < 10; j++) {
				if (((1 << j) & i) != 0) {
					on(0, j);
					count++;
				}
			}

			for (int n = 0; n < 9; n++) {
				for (int m = 0; m < 10; m++) {
					if (testmap[n][m]) {
						on(n + 1, m);
						count++;
					}
				}
			}

			if (checkLight()) {
				answer = Math.min(answer, count);
			}
		}

		if (answer < Integer.MAX_VALUE) {
			System.out.println(answer);
		} else {
			System.out.println(-1);
		}
	}

	static boolean checkLight() {
		for (int i = 0; i < 10; i++) {
			if (testmap[9][i]) {
				return false;
			}
		}
		return true;
	}

	static void copy(boolean[][] map) {
		for (int i = 0; i < 10; i++) {
			testmap[i] = map[i].clone();
		}
	}

	static void on(int x, int y) {
		for (int i = 0; i < 5; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY)) {
				testmap[nX][nY] = !testmap[nX][nY];
			}
		}
	}

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

감사합니다!!

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 문제도 풀도록 하겠습니다.