hyeonnnnn

 📌 정규화(Normalization)란?

관계형 데이터베이스에서 중복을 최소화하고 이상현상(삽입이상, 갱신이상, 삭제이상)을 없애는 것

 📌 1차 정규화

테이블의 컬럼이 원자값을 가지도록 하는 것

<정규화 전>

현재 한소희와 천우희의 취미를 보면 원자값이 아닌 다중값으로 들어가있기 때문에 1차 정규형을 만족하지 못한다.

따라서 1차 정규화를 진행한다.

<정규화 후>

 📌 2차 정규화

1차 정규화를 한 테이블이 완전 함수 종속을 만족하도록(= 부분 함수 종속이 없도록) 테이블을 분해하는 것

즉, 후보키가 복합키(다중칼럼)로 설정되어 있을 때 복합키의 일부칼럼에 다른칼럼들이 결정되어서는 안된다.

완전 함수적 종속과 부분 함수적 종속을 그림으로 나타내면 다음과 같다.

* 제1정규형 테이블의 기본키가 복합키가 아닌 단일키이면 자동으로 제2정규형을 만족한다.

테이블로 더 자세히 알아보자

<정규화 전>

현재 테이블에서 기본키를 (이름, 과목)으로 했을 때, 이 기본키는 전화번호, 강의실, 성적을 결정한다.

이 테이블은 위의 그림과 같이 완전 함수적 종속과 부분 함수적 종속이 모두 존재한다. 

성적 -> 완전 함수적 종속

- 이름만 봤을 때 결정되지 않음 (한소희라는 이름을 가지는 성적값은 A+, B+ 두 개)

- 과목만 봤을 때 결정되지 않음 (데이터베이스 과목의 성적 값은 A+, A0 두 개)

전화번호, 강의실 -> 부분 함수적 종속

- 이름만 봤을 때 전화번호가 결정됨 (과목을 볼 필요 없음)

- 과목만 봤을 때 강의실이 결정됨 (전화번호를 볼 필요 없음)

따라서 부분 함수적 종속을 없애기 위한 제2 정규화가 필요하다.

<정규화 후>

이름, 과목 -> 성적

이름 -> 전화번호

과목 -> 강의실

 📌 3차 정규화

제 2정규형을 만족하는 테이블에 대해 이행 함수 종속이 없는 것

이행 함수 종속은 A -> B, B -> C가 성립할 때 A -> C가 성립 되는 것을 말한다.

이행 함수 종속을 그림으로 나타내면 다음과 같다.

상품번호가 기본키라고 했을 때 상품번호는 상품명, 가격, 판매자, 판매자 전화번호를 결정한다.

여기서 이행 함수 종속을 따져보면, 판매자는 판매자 전화번호를 결정한다.

따라서 상품번호 -> 판매자 -> 판매자 전화번호이기 때문에

판매자 -> 판매자 전화번호를 결정한다.

<정규화 전>

이 테이블에서 상품번호에 따라 상품명, 가격, 판매자, 판매자 전화번호가 결정되지만,

판매자에 따라 판매자 전화번호도 결정된다.

이행 함수 종속을 삭제하기 위한 3차 정규화를 쉽게 하기 위해

이렇게 나눠주면 된다.

<정규화 후>

 📌 보이스코드 정규화

3차 정규화를 진행한 테이블에 대해 모든 결정자가 후보키가 되도록 테이블을 분해하는 것

즉, 식별자로 쓰이는 속성이 일반 속성에 종속되지 않아야 한다.

식별자로 쓰이는 속성이 일반 속성에 종속되는 것을 그림으로 나타내면 다음과 같다.

기본키를 (이름, 거주지)로 설정했을 때 기본키는 학교를 결정한다.

하지만 학교는 다시 거주지를 결정할 수 있을 때 보이스코드 정규화가 필요하다.

2차 정규화와 비슷해 보일 수 있는데,

2차 정규화는 복합키의 일부가 일반 속성을 결정하는 것이다.

보이스 코드 정규화를 테이블로 보면 다음과 같다.

<정규화 전>

(이름, 거주지)는 학교를 결정한다.

하지만 학교도 거주지를 결정할 수 있다.

<정규화 후>

 📌 참고

https://jhnyang.tistory.com/360

https://developer111.tistory.com/10

https://mangkyu.tistory.com/110

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/150367

🛎️  풀이 과정

두 가지의 과정이 필요하다.

1. 포화 이진 트리 만들기
2. 부모, 자식 관계 재귀적으로 확인하기

포화 이진트리를 만들기 위해서는 2^n - 1꼴의 자릿수를 가져야한다.
그리고 확인할 리스트(num)와 해당 리스트의 부모(parent)를 재귀적으로 확인한다.
해당 리스트의 가장 탑노드(child)는 파라미터로 보낸 부모(parent)의 자식이다.
따라서 왼쪽, 오른쪽의 child를 확인해서 parent와 비교한다.

두 가지의 과정이 필요하다는 것까지 확인했지만,
구현에 어려움을 느껴 블로그를 참고하였다.

💻  풀이

import math

def is_tree(num, parent):
  if num:
    mid = len(num) // 2
    # 자식이 있는지 없는지 확인
    child = num[mid] == "1"
  else:
    return 1

  if child and not parent:
    return 0
  else:
    return is_tree(num[:mid], child) and is_tree(num[mid+1:], child)

def check(num):
  if num == 1: return 1

  # 2진수 변환
  b_num = bin(num)[2:]

  # 2^n - 1꼴의 자릿수를 가져야함.
  digit = 2 ** (int(math.log(len(b_num), 2)) + 1) - 1
  b_num = "0" * (digit - len(b_num)) + b_num

  # 자식이 있는 부모가 0이 아닌지 확인
  if b_num[len(b_num) // 2] == "0":
    return 0
  else:
    return is_tree(b_num, 1)

def solution(numbers):
  answer = []
  for num in numbers:
    answer.append(check(num))
  return answer

print(solution([63, 111, 95, 1, 0]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/152995

🛎️  풀이 과정

근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬한다.
그리고 동료 평가 점수의 max값을 저장하기 위한 변수를 선언하고 가장 첫번 째 동료 평가 점수를 넣어준다. (여기서는 max_y)
이 max_y값은 현재 보다 근무 태도 점수가 높은 직전 동료들 중 가장 높은 동료 평가 점수를 가지고 있다.

여기서 동료 평가 점수를 오름차순으로 정렬하는 이유가 나타나는데,
오름차순으로 정렬했을 때 max_y값을 가지고 비교하게 되면
[2, 1], [2, 2] -> 둘 다 인센티브 후보
[2, 2], [2, 1] -> [2, 1]은 후보에서 탈락
으로 오류가 생긴다.

따라서 내림차순 / 오름차순으로 정렬하면
[[3, 2], [3, 2], [2, 1], [2, 2], [1, 4]]
다음과 같고, max_y의 초기값에는 2가 들어간다.

여기서 만약 현재 반복문의 위치가 [1, 4]라고 했을 때, 현재까지의 max_y는 2가 된다.
근무 태도 점수인 1은 작지만 max_y인 2보다 동료 평가 점수인 4가 크기 때문에 인센티브 후보가 된다.

완호의 등수를 구하기 위해 인센티브 후보일 시, 완호의 점수 합과 비교한다. (answer)

💻  풀이

def solution(scores):
  wanho = scores[0]
  wanho_sum = sum(scores[0])
  scores.sort(key=lambda x: (-x[0], x[1]))
  answer, max_y = 1, scores[0][1]

  for index, score in enumerate(scores):
    if score[1] < max_y:
      if score == wanho:
        return -1
      scores[index] = [-1, -1]
    else:
      max_y = score[1]
      if wanho_sum < sum(score):
        answer += 1

  return answer

print(solution([[2,2], [1,4], [3,2], [3,2], [2,1]]))

💻  풀이 (시간초과)

def solution(scores):
  # 완호의 점수 합
  wanho = scores[0][0] + scores[0][1]
  rank = 0
  for index, score in enumerate(scores):
    if index != 0 and score[0] + score[1] <= wanho:
      continue
    for s in scores:
      if score[0] < s[0] and score[1] < s[1]:
        if index == 0:
          return -1
        break
    else:
      rank += 1
  return rank

print(solution([[2,2], [1,4], [3,2], [3,2], [2,1]]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

🛎️  아이디어

- 기본 bfs + 끝까지 직진

1. 다음 위치가 범위 안에 있는지, 장애물이 있는 곳인지 확인

2-A. 다음 위치로 이동이 가능하다면 계속 이동 (continue)

2-B. 다음 위치로 이동이 불가능하다면 직전 위치 queue에 append, cost + 1 (break)

💻  풀이

from collections import deque

def bfs(board):
  row, col = len(board), len(board[0])

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  visited = [[False] * col for _ in range(row)]

  queue = deque()

  # 출발점 찾기
  for i in range(row):
    r_index = board[i].find("R")
    if r_index != -1:
      queue.append((i, r_index, 0))
      visited[i][r_index] = True
      break

  while queue:
    x, y, cost = queue.popleft()

    if board[x][y] == "G":
      return cost

    for i in range(4):
      nx, ny = x, y

      while True:
        nx += dx[i]
        ny += dy[i]

        # 계속 갈 수 있으면
        if 0 <= nx < row and 0 <= ny < col and board[nx][ny] != "D":
          continue
        # 갈 수 없으면 바로 직전 자리 append
        else:
          if not visited[nx - dx[i]][ny - dy[i]]:
            queue.append((nx - dx[i], ny - dy[i], cost + 1))
            visited[nx - dx[i]][ny - dy[i]] = True
            break
          else:
            break

  return -1

def solution(board):
  return bfs(board)

print(solution(["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/118667

🛎️  아이디어

- 1차 아이디어
  queue이기 때문에 둘다 list -> queue 형태로 만들어서 popleft() 사용

- 2차 아이디어
  queue1, queue2를 연결해서 하나의 리스트로 만든 후 그 안에서 규칙을 찾는다.
  -> 예외 내용으로 인해 정규식이 나오지 않음.

- 3차 아이디어
  블로그 참고해서 합이 큰 큐 -> 합이 작은 큐로 원소를 하나씩 이동시키는 아이디어를 얻음
  + while True로 시간초과 걸려서 찾아본 결과 300000로 제한 걸거나 중간에 count를 넣어서하는 방법이 있음.

💻  풀이

from collections import deque

def solution(queue1, queue2):
  q1, q2 = deque(queue1), deque(queue2)
  sum1, sum2 = sum(q1), sum(q2)

  for i in range(300000):
    if sum1 == sum2:
      return i
    elif sum1 > sum2:
      num = q1.popleft()
      q2.append(num)
      sum1 -= num
      sum2 += num
    else:
      num = q2.popleft()
      q1.append(num)
      sum2 -= num
      sum1 += num
  return -1

print(solution([3, 2, 7, 2], [4, 6, 5, 1]))

❓  문제

🛎️  아이디어

1. 출차 기록이 없는 차 번호를 찾는다.
    a. 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우가 없기 때문에 입출차 개수가 홀수라면 출차 기록이 한 개 부족한 것이다.
    b. 23:39로 출차 기록을 추가해준다.

2. 차량 번호 - 시간 - 내역 순으로 정렬을 한다.
    a. 내역 정렬을 하면 알파벳 순으로 IN - OUT이 정렬된다.

3. 차량 별 주차 누적 시간을 계산한다.
    a. 출차 시간인 경우 앞 인덱스의 시간(입차)의 차이를 구해서 더해준다.

4. 최종 요금을 구해준다.
    a. 올림을 사용한다고 했기 때문에 math를 임포트해서 ceil 함수를 사용한다.

💻  풀이

import math
from collections import Counter

def solution(fees, records):
  default_time, default_fee, unit_time, unit_fee = fees

  # 차 번호 별 입출차 갯수 계산
  car_numbers = dict(Counter(map(lambda x: x.split()[1], records)))

  # 출차 기록이 없는 번호는 23:59 추가
  for car in car_numbers.items():
    if car[1] % 2 != 0:
      records.append(f'23:59 {car[0]} OUT')

  # 차량 번호, 시간, 내역 순으로 정렬
  records.sort(key=lambda x: (x.split()[1], x.split()[0], x.split()[2]))
  # ['06:00 0000 IN', '06:34 0000 OUT', '18:59 0000 IN', '23:59 0000 OUT', '07:59 0148 IN', '19:09 0148 OUT', '05:34 5961 IN', '07:59 5961 OUT', '22:59 5961 IN', '23:00 5961 OUT']

  # 차량 별 누적 시간
  sum_time = {}
  for index, record in enumerate(records):
    time, car, history = record.split()

    # 출차 시간인 경우
    if history == "OUT":
      # 입차 시간
      in_time = records[index - 1].split()[0]
      sub_hour = int(time.split(':')[0]) - int(in_time.split(':')[0])
      sub_minute = int(time.split(':')[1]) - int(in_time.split(':')[1])

      # 실제 주차 시간
      sub_time = 60 * sub_hour + sub_minute

      if car in sum_time:
        sum_time[car] += sub_time
      else:
        sum_time[car] = sub_time

  answer = []
  for time in sum_time.values():
    # 최종 요금
    if time <= default_time:
      answer.append(default_fee)
    else:
      answer.append(default_fee + math.ceil((time - default_time) / unit_time)  * unit_fee)

  return answer

print(solution([180, 5000, 10, 600], ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/160585

🛎️  아이디어

1. 3x3에서 3개가 연결될 수 있는 경우의 수는 8개이다.
    a. 8개 뿐이기 때문에 경우의 수를 직접 만들어준다.

2. 경우의 수를 돌면서 해당 인덱스의 데이터들이 같으면 winner list에 저장해준다.

3. board에서 O과 X의 개수를 저장한다.

4. 이 판이 정상적인지 확인한다.
    a. winner_list의 길이는 3 이상일 수 없다. (O 또는 X가 여러 개 완성된 경우)
    b. winner_list에서 중복 제거를 한 후 길이는 2일 수 없다. (O, X 모두 완성한 경우)
    c. winner_list의 길이가 1인 경우
        ㄱ. 승자가 O인 경우 -> O가 선공이기 때문에 O개수가 X개수보다 1이 많아야 한다.
        ㄴ. 승자가 X인 경우 -> " O의 개수와 X의 개수가 같아야한다.
    d. winner_list의 길이가 0인 경우, O의 개수는 X의 개수와 같거나 1개 커야한다.

💻  풀이

def solution(board):
  wins = [[[0,0], [0,1], [0,2]],
         [[1,0], [1,1], [1,2]],
         [[2,0], [2,1], [2,2]],
         [[0,0], [1,0], [2,0]],
         [[0,1], [1,1], [2,1]],
         [[0,2], [1,2], [2,2]],
         [[0,0], [1,1], [2,2]],
         [[2,0], [1,1], [0,2]]]

  # 승자 확인
  winner_list = []
  for win1, win2, win3 in wins:
    if board[win1[0]][win1[1]] == board[win2[0]][win2[1]] == board[win3[0]][win3[1]]:
      winner = board[win1[0]][win1[1]]
      if winner != '.':
        winner_list.append(winner)

  # O, X 각각의 개수
  o_num = sum(map(lambda x: x.count('O'), board))
  x_num = sum(map(lambda x: x.count('X'), board))

  # 3개가 연결된 개수가 2이상이거나 O, X 모두 완성된 경우
  if len(winner_list) > 2 or len(set(winner_list)) == 2:
    return 0
  # 승자가 O 또는 X인 경우
  elif len(winner_list) == 1:
    if winner_list[0] == 'O':
      return 1 if o_num == x_num + 1 else 0
    else:
      return 1 if o_num == x_num else 0
  # 승자가 없는 경우
  else:
    return 1 if o_num == x_num + 1 or o_num == x_num else 0

❓  문제

🛎️  아이디어

1. 캐시 교체 알고리즘인 LRU를 구현하기 위해 deque를 사용한다.

2. 도시 이름을 하나씩 가져온다.
    a. 만약 deque안에 있으면(hit) 제거 후 time += 1
    b. deque안에 없으면(miss) 가장 왼쪽 요소 제거 후 time += 1 (LRU가 가장 오래된 요소를 제거하기 때문)

3. 해당 도시를 큐에 넣어준다.

** cache가 0인 경우 예외 처리가 필요함. -> hit인 경우가 없기 때문에 city개수 * 5를 리턴한다.

💻  풀이

from collections import deque

def solution(cacheSize, cities):
  if cacheSize == 0:
    return len(cities) * 5

  time = 0
  cache = deque([0 for i in range(cacheSize)])

  for city in cities:
    city = city.lower()
    if city in cache:
      cache.remove(city)
      time += 1
    else:
      cache.popleft()
      time += 5
    cache.append(city)
  return time

❓  문제

파일명 정렬

🛎️  아이디어

1. sorted를 사용한다.
    a. lambda 식을 사용해서 key값을 두 개 넣어준다.
    b. 키 두 개는 각각 re를 사용해서 head, number 부분을 가져온다.
        ㄱ. 문자열에서 숫자 부분을 가져와서 해당 숫자 기준으로 자른다. -> 인덱스 0이 head가 된다.
        ㄴ. head 부분은 대소문자 구분을 하지 않기 위해 lower을 사용한다.

💻  풀이

import re

def solution(files):
  # head 기준으로 정렬 -> number 기준으로 정렬
  return sorted(files, key= lambda x: (x.split(re.findall('\d+', x)[0])[0].lower(), int(re.findall('\d+', x)[0])))

❓  문제

피로도

🛎️  아이디어

1. permutations를 사용해서 던전의 수만큼의 range 순열을 만든다.

2. 각각의 순열에서 통과한 던전의 수를 보관할 answer 배열을 만든다.

3. permutations로 생성한 순열들을 돌면서 피로도 계산을 한다.

4. answer 배열에서의 가장 큰 값을 return 한다.

💻  풀이

from itertools import permutations

def solution(k, dungeons):
  permutaion = list(permutations(range(len(dungeons)), len(dungeons)))
  answer = []

  for pmt in permutaion:
    # 통과한 던전 수
    pass_num = 0

    # 초기 피로도
    fatigue = k

    for p in pmt:
      if fatigue >= dungeons[p][0]:
        fatigue -= dungeons[p][1]
        pass_num += 1

    answer.append(pass_num)

  return max(answer)