항해 99 5기 TIL_65

▶ Today I Learned

 

<알고리즘>

 

[정수삼각형]

 

소요 시간: 53분

해결 여부: 미해결

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

다이나믹 프로그래밍

 

처음 문제를 접했을 땐 그리디라던가 완전탐색에 더욱 가깝다고 생각했다.

다이나믹 프로그래밍이 어쩌면 완전탐색과 비슷한 부류일지도 모르겠다.

 

처음 짰던 코드

// 입력 예제

let n = 5
let nums =[[7],[3, 8],[8, 1, 0],[2, 7, 4, 4],[4, 5, 2, 6, 5]]

// 답은 30이 나와야 함
// 자기 인덱스가 i라면 i 또는 i+1인 경우의 수만 고를 수 있음

// dp 생성

let dp = []
for (let i = 0 ; i <= nums ; i ++) {

  dp[i] = []
  for (let j = 0 ; j <= nums ; j++) {
    dp[i][j] = 0
  }
}

maxNum = arr => {

  for (let i = 1 ; i <= nums ; i++) {
    for (let j = 0 ; j <=nums ; j++) {
    arr[i][i-1] arr[i][i]  
    }
  }
}

 

기존에 풀어왔던 dp 방식처럼 똑같은 차원의 테이블을 만들어 놓고 거기에 값을 다 대입하면서 경우의 수를 따지면 될거라 생각했는데

생각보다 쉽게 정리가 되질 않았다.

 

그리하여 다른 풀이법을 참조해본 결과 조금 다른 모양새가 나왔다.

 

const N = 5

const input =[[7],[3, 8],[8, 1, 0],[2, 7, 4, 4],[4, 5, 2, 6, 5]]

const sum = Array.from(new Array(N), () => new Array());
sum[0].push(Number(input[0][0]));
// [ [ 7 ], [], [], [], [] ]


if (N > 1) { // n이 1이면 input[0][0]이 최댓값이기에 조건에 포함시키지 않음
  for (let r = 1; r < N; r++) {
    for (let c = 0; c < input[r].length; c++) {
      if (c === 0) {
        sum[r].push(Number(sum[r - 1][c]) + Number(input[r][c]));
        //
      } else if (c === r) {
        sum[r].push(Number(sum[r - 1][c - 1]) + Number(input[r][c]));
      } else {
        sum[r].push(
          Math.max(Number(sum[r - 1][c - 1]), Number(sum[r - 1][c])) +
            Number(input[r][c])
        );
      }
    }
  }
}
console.log(Math.max(...sum[N - 1])); // 인덱스를 맞춰주기 위해 -1

가장 핵심이 되는 아래 if절 부분들을 보면 대략적으로는 구조가 이해가 가지만

구체적으로 머리에 그려지지 않는다.

현재 구체적으로 이해한 것은 주석을 달아놓은 부분 정도이며

이 풀이를 완전히 내 것으로 만들기 위해서는 철저한 이해가 필요하다.

내일 다시 한 번 이해해보아야겠다.

 

출처:

https://nyang-in.tistory.com/m/269

 

 

<실전 프로젝트>

 

뱃지 지급과 관련하여 검색을 하기가 생각보다 쉽지 않았다.

그나마 당근마켓에서 그런 종류의 뱃지를 지급한다는 말이 있었지만

짧은 기간 내에 모르는 기술 스택들이 가득한 당근마켓 코딩클론 강의를 (물론 일부분만 듣겠지만) 듣는다는 것도

쉽사리 결정내릴 일은 아니었다. 이해가 쉽지 않으며 듣더라도 막상 내가 원하는 내용이 없을 수도 있기 때문이다.

깃허브에서도 간간히 코드를 찾아볼 수 있었지만 아직 그닥 참고할 만한 것은 찾지 못했다.

 

그래서 우선은 내가 스스로 코드를 구현해보고 세세하게 필요한 부분들만 그때 그떄 찾아보기로 했다.

질문이 구체적일 수록 검색하기도 더 쉬우니까 :)

 

그렇게 Controller에 코드를 구현하면서 다음과 같이 2가지 생각을 하게 되었다.

 

 create: {
      newBadges: asyncWrapper(async (req, res) => {
        const { userId } = req.params;
        
        const user = await User.findOne({
          where: { id: userId },
        });

        // 특정뱃지를 가지고 있는지 체크할 때 사용할 배열 미리 생성
        const badgeList = user.UserBadge

        // 1) DB에서 유저와 뱃지 간의 관계가 join되어있다. 여기서 특정 유저가 특정 뱃지를 가지고 있는지를 확인하기 위해 무엇이 필요한가?
        // 어떤 식으로 코드를 작성해서 DB에서 가져올 것인지를 공부할 필요가 있다.
        // 해당하는 부분의 mysql과 sequelize 찾아보고 workbench 작동시켜보자.

        // 2) 어느 시점에 뱃지를 지급하게 할건가?
        // batch를 이용하여 매 5초마다 확인하는 방법도 있겠지만 몇 개 안되는 뱃지를 위해 많은 작업을 하는 것은 불필요해 보인다.
        // 따라서 출석을 했을 때나 방을 나갔을 떄 해당 이벤트를 발생시켜 체크하게 하는 것이 어떨까?
        // 보통은 방 안에서 활동을 하고 기록이 쌓이므로 방을 나갈 때 기록 측정 후 지급하기로 한다. 다만 출석을 했을 떄도 체크하는 이유는 간혹 사용자가 강제종료를 할 수 있기 때문이다.
        
        // 그 외 버그 제보와 같은 특이 케이스는 해당 버튼을 누르면 뱃지를 지급하는 방식을 채택한다.
        // 결국 실시간으로 바로 뱃지를 지급하기 위해서는 해당 기준을 충족하고 어떤 이벤트를 발생시킬 때가 가장 좋다.

        // ex) 운동 뱃지 - 운동 카테고리 누적 참여 시간이 100시간 이상일 경우

        // <뱃지의 분류>
        // 1. 출석과 관련된 것 - > 로그인을 했을 때 지급할만한 것
        // 2. 시간과 관련된 것 -> 방을 나갈 때 시간 체크하여 지급할만한 것
        // 3. 버그 제보와 같은 특이케이스
        // 1) admin 페이지 - 관리자만이 접근 가능한 페이지에서 지급하기 2) 해당 이벤트 발생하자마자 지급 (ex: 버그 제보 버튼 누르자마자 제출))
        
      })
  },

 

<CS>

 

[DB에서 Join]

 

데이터베이스 내의 여러 테이블에서 가져온 행('레코드', 또는 '튜플'이라고도 함)을 조합하여 하나의 테이블이나 결과의 집합을 만들어 주는 것, 주로 SELECT문과 함께 사용됨

ex) User 테이블에서 id를 가져오고 Bagde 테이블에서 id를 가져와 userId badgeId를 라는 columns를 가진

User-Badge라는 하나의 테이블을 만들어 내는 것,

Reservation 테이블의 Name 필드와 Customer 테이블의 Name 필드가 서로 일치하는 레코드만으로

하나의 테이블을 만들어 내는 것

 

표준 SQL에서 행을 조합하는 방식에 따라 JOIN을 구분

 

INNER JOIN

: ON 절과 함께 사용되며, ON 절의 조건을 만족하는 데이터만을 가져옴

(cf. 표준 SQL과는 달리 MySQL에서는 JOIN, INNER JOIN, CROSS JOIN이 모두 같은 의미로 사용됨)

(MySQL에서는 INNER JOIN을 ON 대신 Where 도 사용 가능, 둘에는 차이가 존재하며 자세한 건 하단 링크 참조)

 

LEFT JOIN

: LEFT JOIN은 첫 번째 테이블을 기준으로, 두 번째 테이블을 조합하는 JOIN,

ON 절의 조건을 만족하지 않는 경우에는 첫 번째 테이블의 필드 값은 그대로 가져옴,

하지만 해당 레코드의 두 번째 테이블의 필드 값은 모두 NULL로 표시됨

 

RIGHT JOIN

: LEFT 조인과는 반대로 두 번째 테이블을 기준으로, 첫 번째 테이블을 조합하는 JOIN

(두번째 테이블을 기준으로 합치기 때문에 합쳐진 테이블에서 두번째 테이블이 첫번째 자리인 왼쪽에 위치하게 됨)

ON 절의 조건을 만족하지 않는 경우에는 두 번째 테이블의 필드 값은 그대로 가져옴,

하지만 해당 레코드의 첫 번째 테이블의 필드 값은 모두 NULL로 표시됨

 

 

출처:

http://www.tcpschool.com/mysql/mysql_multipleTable_join

https://jaehoney.tistory.com/55

 

mysql On vs WHERE 의 차이 

https://codingdog.tistory.com/entry/mysql-on%EC%A0%88-vs-where%EC%A0%88-%EC%96%B8%EC%A0%9C-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%84%ED%84%B0%EB%A7%81-%EB%90%98%EB%8A%94%EA%B0%80

 

▶ 느낀 점

 

드디어 MySQL과 Sequelize에 대해 좀 더 알게 되었다.

물론 실습을 통해 활용해본 적은 없기에 코드를 구상하는 단계에서는 미숙할 수 있지만

팀원 분이 이미 짜놓으신 코들 참고삼아 필요한 뱃지 지급 코드를 맞춰 끼워볼 예정이다.

 

해당 코드도 구현해야 하고 중간 발표 준비, 마케팅 전략 구상도 하여야 한다.

내가 맡은 기능을 어서 구현하고 팀원 분들의 진도 현황, 현재 구현 정도를 체크하자.

 

▶ 공부 시 참고 링크들

https://sequelize.org/master/manual/model-querying-basics.html

Manual | Sequelize