23/10/10

[SQL]

HackerRank SQL - Occupations

• 테이블의 열이 주어지고, 행을 순차적으로 채우는 문제
• Doctor, Professor, Singer, Actor 순으로 열의 head가 주어진다.
• 각 직업군 별 사람의 이름을 알파벳 순으로 정렬해서 행을 채우고, 더 이상 사람이 없다면 NULL 을 작성
• 너무 어려워서 다른 사람의 풀이를 본 결과 서브쿼리를 활용한다.
  • ROW_NUMBER()를 활용해 각 직업군별 행의 순서 저장
  • 그러면 직업별 등장 순서를 그룹화 하여 행을 채울 수 있고, 직업별 값을 넣기 위해 MAX(CASE WHEN 직업 = 'Doctor' THEN NAME END)를 활용한다.

[알고리즘]

1. 백준 5557 1학년 복습
   • DP 테이블부터 제대로 설계하고 풀어야 한다.
   • 숫자를 +, - 하는 2가지의 선택지가 있다는 점에서 완탐을 돌면 2^100이 되지만, dp 테이블의 크기는 `dp[100][20]` 이 된다.
   • dp의 시간복잡도는 테이블의 칸과 유사하다!! 병철's 삼단논법
     • 탑다운과 보텀업의 시간복잡도는 일정하다
     • 보텀업 코드는 반복문으로 각 칸을 딱 1번씩만 채운다
     • 따라서 테이블의 칸과 시간복잡도가 유사하다
2. 프로그래머스 42885 구명보트
   • 투포인터를 활용하면 효율성까지도 잡을 수 있다.