내일은 알고리즘

2NF(Second Normal Form) 정규형

2NF 정규형을 만족하려면 릴레이션에서 부분적 함수 종속이 사라지고 완전 함수 종속이 되어야 합니다.

함수 종속성에 대해서는 이전에 정리했으니 릴레이션으로 예시를 들며 설명해 보도록 하겠습니다.

함수종속성에서 예를 들었던 아래와 같은 릴레이션이 있습니다.

이 릴레이션의 기본키는 수업번호입니다.

하지만 과목명은 과목번호에 종속되어 있습니다. 과목번호가 당연히 기본키가 아니기 때문에 이는 부분적 함수 종속성이 있음을 의미합니다.

함수종속성의 설명에서 보았듯 이런 종속성 때문에 튜플의 삽입, 삭제, 갱신에서 이상현상이 발생합니다.

수업이 사라지면 과목의 정보가 사라지기도 하고, 과목명이 바뀌면 해당하는 모든 튜플을 전부 갱신해주어야 합니다.

2NF 정규형을 만족하도록 부분 종속성을 가지는 과목번호와 과목명을 따로 빼어 릴레이션을 나누면

DB를 조작함에서 이상현상이 사라지는것을 알 수 있습니다.

3NF 정규형에 대해서는 다음 글에서 설명해 보도록 하겠습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXZuaLsqz9wDFAST 

어떤 점이 원 안에 포함되는지 여부를 묻는 문제입니다.

입력에 따라 받을 수 있는 점수를 계산하고, 점수의 누적합을 리턴하면 됩니다.

표적판의 원들은 전부 동심원(중심이 같음)이기 때문에 (0,0) 점을 기준으로 화살이 꽂힌 위치의 거리가 원의 반지름보다 작으면 그 원 안에 들어있는 상태입니다. 

if문을 통해 바깥쪽부터 범위를 좁혀가며 해당하는 점수를 찾았고 굳이 제곱근을 씌워 계산하지 않고 제곱을 한 채로 풀어주었습니다.

1년도 더 전에 풀었던 코드라서 새롭게 짜 보았는데 실행시간이나 메모리면에서 엄청난 차이를 보았습니다. 

예전 코드를 보면 무슨 생각으로 짰나 싶은 부분이 많네요. 비교해보시라고 둘 다 첨부합니다.

import java.util.Scanner;

class q11285_SWEA_다트게임 {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int T, TC, sum; 
		long x, y;
		T = sc.nextInt();

		for (int testcase = 1; testcase < T + 1; testcase++) {
			TC = sc.nextInt();
			sum = 0;

			for (int i = 0; i < TC; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				
				if (40000 < x * x + y * y)
					sum += 0;

				else if (32400 < x * x + y * y)
					sum += 1;

				else if (25600 < x * x + y * y)
					sum += 2;

				else if (19600 < x * x + y * y)
					sum += 3;

				else if (14400 < x * x + y * y)
					sum += 4;

				else if (10000 < x * x + y * y)
					sum += 5;

				else if (6400 < x * x + y * y)
					sum += 6;

				else if (3600 < x * x + y * y)
					sum += 7;

				else if (1600 < x * x + y * y)
					sum += 8;

				else if (400 < x * x + y * y)
					sum += 9;

				else
					sum += 10;
			}
			
			System.out.println("#" + testcase + " " + sum);
		}
	}
}

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

public class q11285_SWEA_다트게임Re {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T, TC, sum, x, y;
		T = Integer.parseInt(br.readLine());

		for (int t = 1; t < T + 1; t++) {
			TC = Integer.parseInt(br.readLine());
			sum = 0;

			for (int tc = 0; tc < TC; tc++) {
				st = new StringTokenizer(br.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				int far = (x * x) + (y * y);

				if (40000 < far)
					sum += 0;

				else if (32400 < far)
					sum += 1;

				else if (25600 < far)
					sum += 2;

				else if (19600 < far)
					sum += 3;

				else if (14400 < far)
					sum += 4;

				else if (10000 < far)
					sum += 5;

				else if (6400 < far)
					sum += 6;

				else if (3600 < far)
					sum += 7;

				else if (1600 < far)
					sum += 8;

				else if (400 < far)
					sum += 9;

				else
					sum += 10;
			}

			sb.append("#").append(t).append(" ").append(sum).append("\n");
		}
		System.out.println(sb);
	}
}

정규형에는 1부터 5까지의 정규형(Normal Form)과 BCNF(Boyce and Codd Normal Form)가 있습니다.

4NF와 5NF는 간단히 개념만 설명하고 나머지 4개의 정규형을 정규화과정의 예시를 들어 하나씩 설명해 보도록 하겠습니다.

1NF (First Normal Form) 정규형

1NF정규형이 되려면 도메인이 원자값만 가져야 합니다.  

예를 들어 정규화가 되지 않은 아래와 같은 릴레이션이 있습니다.

수강자 어트리뷰트에 학생들의 이름이 여러개 들어있는 걸 볼 수 있습니다.

그런데 김땡땡씨가 조기졸업을 해서 수강자에서 지워져야 한다고 생각해 봅시다.

김땡땡 씨가 있는 튜플을 지우면 다른 수강자들의 정보까지 지워지며 이상현상이 발생합니다.

(과목의 정보도 사라지지만 이건 다음 정규화에서 말하도록 하겠습니다.) 

1NF를 만족시키게 릴레이션을 바꿔 보겠습니다.

수강자 어트리뷰트의 값이 하나만 되도록 튜플을 나누어 주었습니다.

이제 어떤 수강생이 듣는 강의 정보를 지우거나 갱신할 일이 생기더라도 다른 수강자들의 정보엔 영향을 끼치지 않습니다.

2NF에 관해서는 다음 글에서 이어서 설명해 보도록 하겠습니다.

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

예전에 풀었던 문제들을 복습하면서 정리중입니다.

아이디어를 떠올리기 어렵지만 구현은 간단한 문제입니다.

A에 있는 수와 B에 있는 N개의 수를 하나씩 뽑아 곱해 더하고 그 누적합을 최소로 만드는 문제입니다.

해결방법은 간단합니다.

A에서 가장 작은수를 B에서 가장 큰수, 그 다음으로 작은 수를 다음으로 큰 수와 곱하는 식으로 계산해주면 됩니다.

문제의 조건에선 B를 재배열하지 말라고 하지만... 요구하는 정답이 A의 배열이었다면 몰라도 누적합이기 때문에 그냥 신경쓰지 않고 정렬해줘도 상관없습니다.

아이디어가 맞는지 생각해 보겠습니다.

A에서 기존의 가장 작은 수를 a 라고 하면 a가 아닌 어떤 수는 a+c로 나타낼 수 있을겁니다. (a와 같을 수 있음, 즉 c≥0)

B에서 가장 큰 수를 b라고 하면 b가 아닌 어떤 수는 b-d로 나타낼 수 있을겁니다. (마찬가지로 d≥0)

아이디어가 틀리다면 다른 순서로 수를 배열했을때 합이 더 작아져야합니다.

다른 순서로 수를 배열한다면 기존의 (a * b) + ((a+c) * (b-d))가 (a * (b-d)) + ((a+c) * b)로 대체될겁니다.

각 식을 계산해 풀어주면 1. ab + ab + cb - ad - cd 와 2. ab - ad + ab + cb가 됩니다.

다른 수를 선택해서 합이 더 작아지는 케이스가 있다면 1번 식보다 2번 식이 더 작아야합니다.

즉 1번식 - 2번식 > 0 이 성립해야하는데, 계산해보면 cd < 0이 되고 c와 d는 각각 0 이상의 정수이기 때문에 성립하지 않습니다. (c와 d가 둘 다 0이라면 같은 크기일 순 있지만, 이때의 선택도 정답 조합의 하나가 됩니다.)

따라서 A에서 가장 작은 a와 B에서 가장 큰 b를 곱하는게 최소값이 되는 조합이고, 이렇게 fix된 a와 b를 제외한 A' B'로 다시 최소합을 구한다고 생각하면 같은 증명으로 A와 B의 크기가 1이 될 때까지 적용이 가능합니다. 

둘의 크기가 1이라면 당연히 곱할 수 있는 방법이 하나밖에 없겠죠.

따라서 위와같이 정렬된 A와 역정렬된 B를 순서대로 곱한 합이 최소값입니다.

(제가 수학전공이 아니기 때문에 증명은 틀릴 수 있습니다... )

n = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

A.sort()
B.sort(reverse=True)

answer = 0

for i in range(0,n):
    answer += int(A[i]) * int(B[i])

print(answer)

https://programmers.co.kr/learn/courses/30/lessons/1831

원래는 이분탐색의 Lv.4 문제를 풀려고 했는데, 저도 구현하다가 애매한 부분이 있어 확인해보니 문제에 오류가 있다는 얘기가 많아서 다른 Lv.4 문제를 가져왔습니다.

연산후의 값이 주어지고 그 값이 연산을 통해 만들 수 있는가를 검증하거나 가능한 경우의 수를 찾는 문제는 주어진 값부터 연산을 거꾸로 짚어가며 풀이하면 쉽고 빠르게 풀리는 경우가 많습니다. 이번 문제도 그런 유형이었는데요.

처음엔 3단고음이라는 연산이 중첩되어 계산되는 것을 stack처럼 중첩의 갯수를 카운팅해서 풀이하려고 했는데 구현 난이도가 어마어마 했을 뿐만 아니라 통과도 실패했습니다.

QnA의 도움을 얻어, 이 3단고음이라는 연산은 뒤에서부터 읽어들어갈때, +의 갯수가 2개보다 큰 경우 *하나와 묶어서 사라질 수 있다는걸 알았습니다. 즉, 거꾸로 3단고음 연산이 동작할때 1을 뺄때 +의 갯수를 늘려주고 (+를 역산), +의 갯수가 두개이상이면 3으로 나눠지면서 두개와 소멸하고, 초기값인 1에 도달했을때 +와 *가 모두 상쇄되었으면 카운트를 1 늘려주었습니다.

재귀호출 중간에 ++의 갯수만큼 *의 역산이 이루어져야 하는데 불가능한 경우 가지치기 했습니다.

해당 아이디어를 바탕으로 dfs를 응용한 재귀문을 작성해 테스트케이스를 통과했습니다.

테스트케이스가 하나뿐이라 예외에 걸릴지는 잘 모르겠네요.

public class q1831_Programmers_4단고음 {
	static int answer;

	public static void main(String[] args) {

//		int[] input = { 15, 24, 41 };
		int[] input = { 15, 24, 41, 2147483647 };

		for (int i = 0; i < input.length; i++) {
			System.out.println(solution(input[i]));
		}
	}

	private static int solution(int n) {
		answer = 0;

		dfs(n, 0);

		return answer;
	}

	private static void dfs(int now, int depth) {
		//System.out.println("now:" + now + "   depth:" + depth);
		
		if (now == 1 && depth == 0) {
			answer++;
			return;
		}
		
		if (now < Math.pow(3, (depth / 2))) {
			return;
		}

		dfs(now - 1, depth + 1);
		
		if (depth >= 2 && now >= 3 && now % 3 == 0) {
			dfs(now / 3, depth - 2);
		}

	}

}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXYmjC8adSkDFAST 

같은 평면위에 놓인 원과 사각형이 겹치는 관계를 체크하는 문제입니다.

주어진 조건하에서 원과 사각형이 같은 모양일 수가 없기 때문에 가능한 경우는 세개입니다.

1. 원 안에 사각형이 포함됨 = 빨간 셀로판지만 보임

2. 사각형 안에 원이 포함됨 = 파란 셀로판지만 보임

3. 원과 사각형간에 포함관계가 없음 (일부만 겹치거나 아예 겹치지 않음) = 두가지 색이 모두 보임

입력에 따라 조건만 잘 나누어주시면 해결됩니다.

제 풀이에서는 사각형의 네개의 꼭짓점 (a,b) (a,d) (c,b) (c,d)이 하나라도 원 밖에 있는지를 체크하고 (모두 안쪽인 경우 1번 케이스에 해당), 다음 조건문으로 사각형의 모든 꼭짓점이 원 밖에 있는지를 체크(2번 케이스) 아니라면 3번 케이스가 됩니다.

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

class q11112_SWEA_셀로판지 {
	public static void main(String args[]) throws Exception {
		int T, a, b, c, d, p, q, r;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case < T + 1; test_case++) {
			st = new StringTokenizer(br.readLine());
			p = Integer.parseInt(st.nextToken());
            q = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken()); 

			if ((p - a) * (p - a) + (q - b) * (q - b) > r * r 
					|| (p - a) * (p - a) + (q - d) * (q - d) > r * r
					|| (p - c) * (p - c) + (q - b) * (q - b) > r * r 
					|| (p - c) * (p - c) + (q - d) * (q - d) > r * r) {
				if (p + r > c || p - r < a || q + r > d || q - r < b) {
					System.out.println("#" + test_case + " YY");
				} else {
					System.out.println("#" + test_case + " NY");
				}
			} else {
				System.out.println("#" + test_case + " YN");
			}

		}
		 br.close();
	}
}

네... 발표는 2주 쯤 지났는데 면접으로 바빠서 이제야 글을 씁니다.

백수가 되어서 공부할 시간이 많았기에 붙을거라고 생각은 했습니다만...

시험장에 가보니 예상과 다른 처음보는 문제들이 많았습니다.

처음 보는 개념의 약자를 묻거나 최신 IT 트렌드의 키워드를 묻는 문제가 많았어요.

그래도 기출유형 문제와 코딩문제에서 큰 실수를 안하고 새로운 문제들을 몇개 건져서 넉넉하게 통과한 것 같습니다. 

공부는 대략 하루 2시간정도씩 2주정도 했고 시중에서 파는 문제집을 읽고 예전 시험 기출을 풀면서 자주 나오는 키워드를 정리했습니다.

전공자라 코딩문제는 자주 사용 안하는 C언어 포인터 부분만 복습했습니다. 

시험 3일 전 부터는 정리해놓은 요약본을 출력해서 들고다니면서 달달 외웠습니다. 

합격률이 25%정도 나왔던데 아마 예상못한 문제들 때문에 탈락하신 분들이 많을 것 같습니다.

저도 학부생 시절에 배운 전공내용이 머릿속에서 겨우 떠올라서 두문제 정도 찍다시피 맞췄습니다...  (레이드 0, DB 오류)

엄청나게 도움이 되는 자격증은 아니지만 작년에 두번을 날린 기억이 있어서 올해 첫 시험에 한번에 따니 마음은 좀 편하네요.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST 

간단한 BFS응용 문제입니다. 모든 땅들을 기준으로 물까지의 거리를 생각하면 재귀나 백트래킹으로 계산해야겠지만, 물을 시작점으로 놓고 BFS를 돌리면 땅과의 거리를 쉽게 알 수 있습니다.

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

public class q10966_SWEA_물놀이를가자 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int N, M;

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

		int T = Integer.parseInt(br.readLine());
		int answer;

		for (int tc = 1; tc <= T; tc++) {

			answer = 0;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			boolean[][] visit = new boolean[N][M];

			Queue<int[]> queue = new LinkedList<>();

			for (int n = 0; n < N; n++) {
				String str = br.readLine();
				for (int m = 0; m < M; m++) {
					if (str.charAt(m) == 'W') {
						visit[n][m] = true;
						queue.add(new int[] { n, m, 0 });
					}
				}
			}

			while (!queue.isEmpty()) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				int l = now[2];
				answer += l;

				for (int i = 0; i < 4; i++) {
					int nX = x + delta[i][0];
					int nY = y + delta[i][1];
					
					if(isIn(nX,nY) && !visit[nX][nY]) {
						visit[nX][nY] = true;
						queue.offer(new int[] {nX,nY,l+1});
					}
				}
			}

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}

	static boolean isIn(int x, int y) {

		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}

		return false;
	}
}

https://programmers.co.kr/learn/courses/30/lessons/43238

이분탐색의 기본적인 응용문제입니다.

가능한 정답의 최소시간 = 1과 확실하게 가능한 정답중의 하나 = ((대기자의 수 / 심사관의 수) + 1 ) * 가장 느린 심사속도 두개를 시작점으로 해서 이분탐색을 돌리면 됩니다.

이분 탐색 문제는 언제나 탐색을 멈추는 조건을 정하는게 어려운데, 문제가 보통 정답의 최댓값이나 최솟값을 요구합니다. 우리는 문제에 따라 확실하게 가능한 정답과 확실하게 정답이 아닌 것+1을 줄여가다가 둘이 겹치는 곳에서 문제가 요구하는 답을 찾을 수 있습니다.

public class q43238_Programmers_입국심사 {

	public static void main(String[] args) {

		int n = 6;
		int[] times = { 7, 10 };

		System.out.println(solution(n, times));
	}

	private static long solution(int n, int[] times) {
		long answer = 0;

		long max = 0;

		for (int t = 0; t < times.length; t++) {
			max = Math.max(max, times[t]);
		}

		long left = 1;
		long right = ((n / times.length) + 1) * max;

		while (left < right) {
			long center = (left + right) / 2;
			long count = 0;

			for (int t = 0; t < times.length; t++) {
				count += (center / times[t]);
			}
			
			if(count >= n) {
				right = center;
			}else {
				left = center + 1;
			}

		}

		answer = right;
		return answer;
	}
}

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

정렬이 곁들여진 시뮬레이션 문제입니다.

핵심아이디어는 돈이 허락하는 범위 안에서 5000원짜리 메뉴를 먹었을때 얻는 상대적 만족도가 가장 큰 경우를 선택해야 한다는 것입니다.

예를 들어서, 극단적으로 5000원짜리 메뉴의 만족도가 1만이라고 해도 1000원짜리 메뉴의 만족도가 9999라면 상대적 만족도는 1에 불과합니다. 또 역으로 1000원짜리 메뉴가 더 만족스러운 경우도 가능할 수 있습니다.

가장 만족스러운 식사를 하려면 날짜와 만족도에 상관없이 상대적 만족도가 큰 5000원짜리 메뉴부터 골라서 가능한만큼 선택하는것이 해결방법입니다.

따라서 A메뉴와 B메뉴의 만족도의 차이를 기준으로 입력된 데이터를 정렬해주고, 돈이 허락하는 한에서 A메뉴를 선택했습니다. 돈이 가능한지 여부는 (골라야하는 남은 메뉴의 갯수 * 1000) + 4000 보다 현재 자금이 크거나 같으면 가능하다고 조건문을 잡아두었고 메뉴를 하나 고를때 마다 자금에서 5000원씩을 빼 주었습니다.

또, 정렬을 통해서 B메뉴의 만족도가 더 큰 시점이 오면 이후로는 전부 B메뉴를 선택했습니다. B메뉴를 선택하기 시작한 경우는 두가지입니다.

1. 돈이 부족해서 남은 모든 식사는 B메뉴로 골라야 한다. (조건문을 통해 보장됨)

2. 남은 모든 식사들은 B메뉴가 A메뉴보다 맛있다. (정렬을 통해 보장됨)

따라서 이후로는 돈 계산을 하지 않고 B메뉴의 만족도를 계속 더해주었습니다.

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));
		long answer = 0;

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int money = Integer.parseInt(st.nextToken());
		int[][] menu = new int[N][2];

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

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

		int n = 0;

		while (money - ((N - n) * 1000) >= 4000) {
			if(menu[n][1] > menu[n][0]) {
				break;
			}
			answer += menu[n][0];
			money -= 5000;
			n++;
		}
		while (n < N) {
			answer += menu[n][1];
			n++;
		}
		
		System.out.println(answer);
	}
}

1. 함수종속성

함수적 종속성은 속성들의 집합 두 개 사이의 제약조건입니다.

다시 말해 어떤 릴레이션의 속성 X와 Y가 있을때, 튜플 Y의 값이 X에 의해 결정되거나 종속된다는 것입니다. (X→Y)

또 이 함수 종속성은 세개로 나뉘는데,

완전 함수 종속 : 속성이 기본키에만 종속되고, 기본키가 여러 속성으로 구성된 경우 기본키의 모든 속성에 종속되는 경우. 

부분 함수 종속 : 기본키가 아닌 속성에 종속되거나, 기본키의 일부 속성에 종속된 경우.

이행 함수 종속 : (X→Y) 종속관계이고 (Y→Z) 종속관계일때 (X→Z)도 성립하는 경우.

EX)

대학생의 학생정보를 담은 이런 릴레이션이 있다고 했을때, 이름 학년 학과의 정보는 학번에 종속됩니다. (완전 함수 종속)

이름에도 종속되는게 아니냐 생각할 수도 있지만, 동명이인이 있어 아래와 같은 학생이 존재한다면 이름만 가지고선 학년과 학과 정보를 알 수 없습니다.

따라서 이름은 종속관계를 가지지 않습니다.

대학교 강의 정보를 담은 위와 같은 릴레이션이 있다고 했을때 기본키는 수업번호입니다.

하지만 과목명은 과목번호만 알아도 알아낼 수 있습니다. (부분 함수 종속)

또한 강의실이 수업마다 배정된다면, 강의실도 수업번호에 부분 함수 종속이 됩니다.

2. 이상현상(Anomaly)

이상현상은 릴레이션 안에 같은 데이터가 불필요하게 중복되어 발생하는 현상으로 삽입이상, 삭제이상, 갱신이상의 세가지 종류가 있습니다.

위의 대학교 강의정보 릴레이션을 예로 들어서 설명하겠습니다.

다음 학기부터 새로운 과목인 [데이터사이언스]과목이 신설될 예정입니다. 하지만 아직 수요조사가 끝나지 않아 몇개의 강의가 열릴지 미정된 상태입니다. 그럼 우리는 이 과목을 릴레이션에 등록할때 두 개의 NULL값을 가지게 됩니다. 

또한 강의가 여러개 열린다면 같은 내용의 튜플을 여러개 등록해야겠죠. (삽입이상)

운영체제 강의가 신청자 미달로 폐강되었다고 합시다. 우리는 릴레이션에서 운영체제 수업을 삭제했습니다.

수업이 없어졌을 뿐이지만, 과목번호와 과목명까지도 함께 삭제되었습니다. (삭제이상)

학과 교육과정의 변경으로 과목번호 S100에 해당하는 과목이 데이터베이스에서 [C언어 입문]으로 변경되었습니다.

우리는 과목번호가 S100인 모든 튜플을 찾아서 값을 바꿔주어야 합니다. 예시에선 해당되는 튜플이 단 두개 뿐이지만 수억개의 데이터가 들어있는 실제 사용되는 DB라면 어마어마한 추가 작업이 필요합니다.

3. 정규화

릴레이션에 정보가 중복저장되어 있다면 DB의 가용공간을 낭비할 뿐만 아니라 위에서 보았듯 이상현상이 발생합니다. 이런 문제를 방지하기 위해 정규화 과정을 거칩니다.

예를 들어 위의 강의정보 릴레이션을 정규화 한다면,

이렇게 두개의 릴레이션으로 쪼갤 수 있습니다.

위에서 발생했던 이상현상들을 정규화된 후에 적용시켜 본다면, 새로운 과목을 신설할땐 과목 릴레이션에 S103 - 데이터사이언스 라는 튜플을 추가하면 됩니다. (삽입이상이 발생하지 않음)

또 수업이 폐강되는 경우에도 수업 릴레이션에서 해당하는 수업의 튜플만 지우면 됩니다. 그 수업의 과목정보는 과목 릴레이션에 그대로 남아있습니다. (삭제이상이 발생하지 않음)

과목명이 바뀌는 경우에도 과목 릴레이션에서 해당하는 정보 튜플 하나만 수정하면 그 과목의 수업이 몇개든 상관없이 수정이 완료됩니다.

정규화 단계에 대해선 다음 글로 설명하도록 하겠습니다.

https://programmers.co.kr/learn/courses/30/lessons/64064

Lv.3치고 간단한 조합 응용문제입니다.

전체 사용자 리스트 Y개에서 불량 사용자 리스트에 대하여 대입이 가능한 X개를 뽑아 만들면 됩니다. (yCx)

조합과 다른 점은 아이디를 넣을 수 있는 경우가 제한되어 있어 사용자 Y가 아닌 불량 사용자 X에 대해 찾는다는 점입니다. 

모든 경우(Y x X)에 대하여 가능 여부를 미리 계산한 뒤, 재귀를 통해 불량 사용자 리스트마다 사용자를 대입하고 X개를 뽑았을 때 저장했습니다.

입력 데이터의 최대 사이즈가 8개이기 때문에 중복체크는 bitmask를 이용해 간단히 구현했습니다. 

가능한 리스트 최대 길이가 64이기 때문에 HashMap을 이용해도 구현이 가능할 것 같습니다. 

package programmers;

public class q64064_Programmers_불량사용자 {

	public static void main(String[] args) {
		String[] user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
		String[] banned_id = { "fr*d*", "*rodo", "******", "******" };
		System.out.println(solution(user_id, banned_id));
	}

	private static int solution(String[] user_id, String[] banned_id) {
		int answer = 0;
		boolean[] bitmask = new boolean[1 << user_id.length];

		boolean[][] possible = new boolean[user_id.length][banned_id.length];

		for (int u = 0; u < user_id.length; u++) {
			for (int b = 0; b < banned_id.length; b++) {
				boolean flag = true;

				if (user_id[u].length() != banned_id[b].length()) {
					flag = false;
				} else {
					for (int i = 0; i < user_id[u].length(); i++) {
						if (banned_id[b].charAt(i) == '*')
							continue;
						else if (user_id[u].charAt(i) != banned_id[b].charAt(i)) {
							flag = false;
							break;
						}
					}
				}

				possible[u][b] = flag;
			}
		}

		recur(possible, bitmask, 0, 0);

		for (int i = 0; i < bitmask.length; i++) {
			if (bitmask[i])
				answer++;
		}
		return answer;
	}

	private static void recur(boolean[][] possible, boolean[] bitmask, int mask, int idx) {
		if (idx == possible[0].length) {
			bitmask[mask] = true;
			return;
		}

		for (int u = 0; u < possible.length; u++) {
			if (possible[u][idx] && (mask & (1 << u)) == 0) {
				recur(possible, bitmask, mask | (1 << u), idx + 1);
			}
		}
	}
}