알고리즘 문제 풀어보기

덧칠하기

문제 설명

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.

벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

롤러가 벽에서 벗어나면 안 됩니다.
구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

제한사항

1 ≤ m ≤ n ≤ 100,000
1 ≤ section의 길이 ≤ n
1 ≤ section의 원소 ≤ n
section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
section에서 같은 원소가 두 번 이상 나타나지 않습니다.
section의 원소는 오름차순으로 정렬되어 있습니다.

풀이 코드

function solution(n, m, section) {
    let answer = 0;
    let part = 0;
  
    section.forEach((n) => {
      if (n > part) {
        part = n + m - 1;
        answer++;
      }});
  
    return answer;
  }

풀이 과정

현재까지 칠한 구역 part를 만들고 section을 forEach메서드로 하나씩 확인한다. 현재 구역이 현재까지 칠한 구역보다 크면 구역을 칠하고 현재까지 칠한 구역을 업데이트 해준다. 이후 페인트를 칠했으니 answer을 1증가 시킨다.

인증과 인가

인증(Authentication)

서비스를 이용하려는 사용자가 인증된 신분을 가진 사람이 맞는지 검증하는 작업.

• ex) 신분증 검사 작업.

일반적인 사이트의 로그인 기능에 해당.

인가(Authorization)

이미 인증된 사용자가 특정 리소스에 접근 하거나 특정 작업을 수행할 수 있는 권한이 있는지 검증하는 작업.

• ex) 놀이공원에서 자유 이용권을 소지하고 있는지 확인하는 작업.

Access, Refresh Token

Access Token

사용자의 인증이 완료된 후 해당 사용자를 인증할 용도로 발급하는 토큰.

• ex) 쿠키에 jwt를 설정하고, 만료기간이 지나면 인증이 만료되는 구조.

• 인증 요청시에 사용하면 토큰을 생성할 때 사용한 비밀키로 인증을 처리함.
  => 복잡한 설계나 여러 분기 처리 없이 코드를 구현할 수 있음.
• Node.js 서버가 재시작되더라도 동일하게 작동. - Stateless(무상태)
  => jwt를 이용해 사용자의 인증 여부는 확인할 수 있지만, 처음 토큰을 발급한 사용자가 정말 그 사용자인지는 확인할 수 없음.
• 존재 자체로 사용자 인증에 필요한 모든 정보를 가지고 있음.
  => 토큰을 가지고 있는 시간이 늘어날 수록 탈취되었을 때 피해규모가 커짐.
• 토큰이 탈취되어도 서버에서 해당 토큰이 탈취되었는지 알 수 없고 만료시킬 수도 없음.
  => 언제나 토큰을 탈취될 수 있다는 가정하에 피해를 최소화 시킬 방향으로 개발해야함.

Refresh Token

특정 사용자가 Access Token을 발급받기 위한 목적으로만 사용.

• 사용자의 인증 정보를 검증하는데 사용되며 이를 서버에서 관리.
• 서버는 Refresh Token을 디코딩해서 사용자의 정보를 확인.
  => 필요시 서버에서 강제로 토큰을 만료시킬 수 있고, 사용자의 인증 상태를 언제든 서버에서 제어할 수 있음.
• 토큰이 탈취된 경우에 대비해 피해를 최소화하기 위해 Refresh Token을 통해 Access Token을 발급받음.
• 사용자가 서버와 최초 인증시에 발급 받음.

• 프로젝트를 신속히 구현하거나 사용자의 요청에 대한 인증을 최소화하려는 목표가 있으면 Access Token만 사용.
• 보안성을 중요히 여기고 서버를 견고하게 구성해야 하면 Refresh Token의 사용을 고려.

로그 미들웨어(Log Middleware)

클라이언트의 모든 요청 사항을 기록해 서버의 상태를 모니터링하기 위한 미들웨어.
=> 문제 발생시 빠르게 진단 가능. 로그 데이터는 사용자의 행동을 분석하는 등 데이터 분석작업에 활용 가능.