0326 TIL

looggi·2023년 3월 26일

DP 데이터베이스 반정규화 정규화 코테

TILs

목록 보기

46/114

데이터베이스

1차 정규화

기본 키 판별 = 식별자 판별
중복성 제거 및 종속성 제거로 확인할 수 있음

하나의 칼럼으로 구분했을 때 중복되는 속성이 없는지 확인,
중복되는 속성이 있다면 다른 칼럼과 함께 식별자가 되었을 때는 중복되는 속성이 없는지 확인
= 구성된 식별자가 유일하게 다른 속성들을 종속하는지 확인

2차 정규화

식별자가 2개 이상의 칼럼으로 구성된 경우 시행
아닌 경우 생략 가능
구성하는 칼럼 중 하나에 종속되는 칼럼이 있는 경우 부분 종속성이 있으므로 테이블을 분리해야한다

3차 정규화

기본키를 제외한 칼럼간의 종속성을 제거
이행 종속성 제거

BCNF

후보키가 있는 경우, 후보키가 기본키를 종속시키면 분해한다

4-5차 정규화는 실질적으로 수행하지 않는다

4차 정규화

여러 칼럼들이 하나의 칼럼을 종속시키는 경우 분해하여 다중값 종속성을 제거한다

5차 정규화

조인에 의해 종속성이 발생하는 경우 분해한다

반정규화

정규화를 하게 되면 테이블이 모두 분리되어 독립성, 유연성이 증가하는 대신 SELECT시 많은 JOIN이 발생할 수 있다. 조인을 하게되면 테이블 간의 일치되는 데이터를 찾기 위한 다중 반복문이 돌아가게 되고 데이터의 양이 증가할수록 쿼리의 비효율성이 증가한다 (실제로는 인덱스나 옵티마이저를 사용하기 때문에 이런 비효율적인 실행은 없다고 함)
따라서 자주 사용되는 범위의 데이터는 반정규화를 통해 빠른 데이터 조회를 하는 것이 좋다
반정규화는 반드시 정규화 이후에 진행해야하며
클러스터링, 파티션, 튜닝 등으로 해결할 수 있는지 먼저 확인하는 절차가 필요하다
그리고 필요에 따라 해도 되고 하지 않아도 된다

스터디 문제 풀기

N으로 표현

어떻게 풀 것인지 생각해내는 게 정말 중요한 문제인 것 같다
'임의의 숫자 number를 만드는데 사용하는 N의 갯수를 최소화한다'고 생각하면 풀 수 없는 문제였던 것 같다
심지어 숫자를 8개 이하로 만드는 방법은 여러가지라서 내가 생각한 로직이 맞는지 판단하기도 어려웠다
DP문제라는 걸 알았기때문에 일정 로직이 반복된다는 것을 알았지만 어느 부분에서 어떻게 반복을 적용해야하는지 찾기가 어려웠다

핵심은 사용할 수 있는 N의 갯수가 8개를 넘지 않아야한다는 것이었고 그걸 이용해서
N을 1~8번 사용해서 만들 수 있는 숫자들의 집합을 구성해야한다

N을 n개만 사용해서 만들 수 있는 수의 집합이 결국 이전의 집합으로 구성되기때문에 이 집합들의 합집합으로 이후의 집합을 만들어나갈 수 있다

N을 1개만 사용해서 만들 수 있는 수의 집합을 합집합해서 2개를 사용해서 만들 수 있는 집합을 구성하고
N을 2개만 사용해서 만들 수 있는 집합과 N을 1개만 사용해서 만들 수 있는 집합, 그 반대 순서(빼기와 나누기때문에 고려해야함)에 의해 3개를 사용해서 만들 수 있는 집합을 만들 수 있다

number를 n개의 N으로 구성하는 방법은 이전에도 해봤듯이 여러개지만 (1<=n<=8)
사용할 N의 갯수n를 고정시켜놓은 채로 number를 만들기때문에 number가 이후에 더 많은 갯수로 만드는 경우에 중복되어 나올 수 있지만, N이 작은 것부터 오름차순으로 계산된 number가 먼저 나오기때문에 답이 틀릴 수 없다

만약에 DP리스트를 완성시켜서 그 안에서 number를 찾는다고 해도 기본적으로 오름차순으로 찾기때문에 문제가 없다

def solution(N, number):
    answer = -1
    DP = [[] for _ in range(9)]
    for i in range(1, 9):
        numbers = set()
        numbers.add(int(str(N)*i))
        for j in range(1, i//2+1):
            for x in DP[j]:
                for y in DP[i-j]:
                    numbers.add(x+y)
                    numbers.add(x-y)
                    numbers.add(y-x)
                    numbers.add(x*y)
                    if y != 0:
                        numbers.add(x//y)
                    if x != 0:
                        numbers.add(y//x)
        if number in numbers:
            answer = i
            break
        DP[i]=numbers
    return answer

solution(9,2)
[[], {9}, {99}, {0, -90, 999, 11, 108, 90, 891}, [], [], [], [], []]

1번 set의 9와 3번 set의 11의 차로 number2를 구할 수 있다

*범위를 i-1까지로 했을 때

테스트 1 〉	통과 (0.68ms, 10.5MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (15.57ms, 11.3MB)
테스트 5 〉	통과 (10.13ms, 11.2MB)
테스트 6 〉	통과 (0.26ms, 10.3MB)
테스트 7 〉	통과 (0.16ms, 10.3MB)
테스트 8 〉	통과 (15.58ms, 11.1MB)
테스트 9 〉	통과 (0.02ms, 10.4MB)

*범위를 i//2까지로 했을 때
범위를 줄인 게 근소하지만 더 빠르다

테스트 1 〉	통과 (0.56ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.5MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (11.14ms, 11.3MB)
테스트 5 〉	통과 (8.27ms, 11MB)
테스트 6 〉	통과 (0.12ms, 10.4MB)
테스트 7 〉	통과 (0.13ms, 10.1MB)
테스트 8 〉	통과 (11.37ms, 11.2MB)
테스트 9 〉	통과 (0.02ms, 10.4MB)