스터디룸

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #55 Jump Game

문제 풀이

dp로 풀어야 한다는 생각은 들었으나 생각보다 풀이가 너무 간단하면서도 명확해서 당황했다.

0좌표에서 시작하여 현재 좌표 + 현재 값이 점프할 수 있는 최대 위치이며 마지막 위치까지 점프할 수 있다면 true를 반환, 그렇지 않으면 false를 반환해야 한다.

• 초기값은 0좌표 값을 기준으로 시작
• 다음 좌표들에 대해 탐색한 좌표가 탐색 가능한 최대 위치보다 크다면 범위가 초과되어 마지막 위치까지 도달할 수 없음을 의미하므로 false 리턴
• 범위 내에 있으나 현재 위치 + 현재 값이 이동할 수 있는 최대 위치보다 크다면 갱신
• 만약 현재까지 기록된 최대 이동 위치가 주어진 배열길이-1과 같거나 더 크다면 true 반환

python 코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        limit = nums[0]
        for i, num in enumerate(nums):
            if i > limit:
                return False
            limit = max(limit, i + num)
            if limit >= len(nums) - 1:
                return True
        return True

2021 Dev-Matching: Silicon Valley 코딩테스트 후기 후속 포스팅입니다. 2021 데브매칭: 실리콘밸리에 지원한 기업들 중 합격하여 추가 전형을 진행한 내역을 기록합니다.

1차 진행 상황 : 기업을 3군데만 지원할 수 있어서 어떻게 될지는 모르겠습니다.

- 팀블라인드(Node.js) : 서류 탈락했습니다. '-` node.js 써보지도 않았으면서 여긴 또 왜 지원했는지....

- MOLOCO Software Engineer : 서류 합격해서 추가 이력서 및 몇 가지 질문에 대한 답변 요구받았습니다. 개인적으론 놀랐습니다. 내심 MOLOCO는 세미 구글급으로 어려운 기업이라고 인지했는데 기회가 의외의 곳으로부터 주어졌습니다. 온라인 테스트 - 기술 인터뷰 순으로 진행 예정입니다. 다만, 영문 이력서랑 커버레터를 써본 적이 없는데 얼른 써서 제출해야겠습니다...

 - MOLOCO 온라인 테스트 : 코드시그널에서 진행했습니다. 문제 난이도는 그리 높아보이진 않았으나 수시채용 포지션이라는 점, 화면공유가 되었다는 점에서 인터뷰어께서 그 과정까지 평가할 수 있겠다는 생각이 들었습니다. 4문제 중 4문제 모두 correct 사인 받고 제출했습니다.

 - MOLOCO 인터뷰 : 온라인 테스트 통과했음을 통보받고 다음 절차 진행하기로 했습니다. 폰스크리닝을 옵셔널하게 진행할 수 있다는데 개인적으로 제발 진행해줬으면 좋겠네요... 이제까지 전해들은 외국계 기업의 알고리즘 면접 매운맛에 아직 대비가 안된 것 같은데 큰일입니다.

- MOLOCO 결과 : 불합격했습니다. DP가 나올줄은 알고있었는데 뭔가 화이트보드 코딩의 개념이 아직 몸에 익숙치 않아서 정말 모든 곳에서 실수를 범했습니다. 면접관님이 제가 너무 못 풀어서 당황하신 듯한 느낌이...'-` 그래도 어떤 느낌인지 알았으니 문제를 풀 때 항상 면접에 임한다는 생각으로 풀어야겠습니다. 겸사겸사 DP도 연습하고... 면접관님꼐서 최대한 트라우마로 남지 않도록 배려를 해주신 덕에 알고리즘 라이브 코딩 면접이 처음이었음에도 좋은 경험했다 정도로 감상평을 남길 수 있겠네요.

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

작성 계기

SNS로그인을 구현했던 때에 Google, Naver, Kakao 3사가 모두 토큰 인증 방식을 채택했으며 각 회사의 API 명세에 어떤 형태의 토큰이 오고가는지 명세가 되어있기도 했다. 특히 네이버는 전송받은 Token을 콘솔에 출력해보면서 어떤 정보가 들어있는지 실제로 볼 수 있었다. 그 당시엔 오류가 발생하지 않게끔만 구현했으나 왜 Token 기반 인증방식을 채택했는지 등 각 인증방식과 비교하여 기록해두면 좋지 않을까 생각이 들어 이번 기회에 정리하게 되었다. 특히 토큰 기반 인증은 SNS 로그인 이후 추가적인 내부 인증을 요구할 때도 JWT 정보를 활용하면 커뮤니티 글 작성 시 실제 valid한 유저가 작성했는지 여부 등 여러 용도로 쓰일 수 있다. 이와 관련된 내용은 추후 정리해보려 한다.

전통적인 인증(Traditional Authentication)

아주 기본적인 인증은 base64 인코딩 등으로 이루어졌었다. 키:값 형태로 주어진 데이터를 인코딩하여 HTTP header에 제공한 후 전송하는 방식이다. 그러면 HTTP 서버는 해당 값을 기존 키-값으로 디코딩하여 valid한 지 판별할 수 있었다. 그러나 이 방법은 모든 request마다 password가 기본적으로 포함된 상태이기 때문에 쉽게 intercept된다는 문제가 있다.

request마다 password를 전송하여 중간에 스니핑 당할 수 있다는 위험을 방지하기 위해 새로운 방법이 도입된다. id, pw 등 사용자 개인정보뿐만 아니라 다른 별개의 값도 함께 섞어서 암호화된 값을 생성한 뒤 서버에 전송하고 서버 또한 동일한 암호화 과정을 수행해 생성한 값을 비교한다. 이 방법은 네트워크에 비밀번호 등 보안이 요구되는 데이터를 어떠한 형태로든 전송하지 않았다는 점에서 기존 방법과 차별점이 있다. 그러나 서버 또한 유저가 갖고 있는 추가 정보에 대해 동일하게 보유하고 있어야 한다. 보안 측면에선 개선이 이루어졌으나 HTTP 통신 특성 상 Stateless하다는 특징으로 인해 매 request마다 인증을 요구한다는 점에서 많은 비용이 필요하다.

매번 인증을 해야한다는 단점을 극복하기 위해 사용되는 대표적인 개념이 바로 세션(Session)과 토큰(Token)이다.

세션 인증(Session Authentication)

세션 인증에는 서버에 저장하는 세션(Session)과 유저 클라이언트에 저장하는 쿠키(Cookie)가 있다. 유저가 인증을 수행한 뒤 그 정보를 저장한다고 했을 때, 먼저 서버에서 사용자들의 정보를 보관해야 한다. 사용자의 정보 보관을 위해 서버에서는 세션(Session)의 형태로 기록을 하는데 사용자마다 고유한 세션을 식별하기 위해 Session Id를 부여한다. 그리고 인증을 마친 사용자에게 쿠키로 Session Id 등을 전달하여 다음 인증 때 재인증할 필요 없이 Request에 Session Id만 담아 보내면 된다. 서버는 클라이언트가 보낸 Session Id와 서버 메모리에 기록해둔 Session Id를 비교하여 인증절차를 수행한다.
Session 기반 인증은 서버에서 인증 요청자의 상태 확인이 빠르며 클라이언트는 쿠키에 기록된 Session Id만을 보낼 뿐 인증 절차의 대부분은 서버에서 담당하기 때문에 안전하다. 그러나 문제는 서버 메모리에 Session 정보를 저장하는 데 있다. 클라이언트로부터 인증 요청을 수행하고 해당 사용자의 인증 상태를 서버에 계속 유지시키면서 서비스에 사용하므로 Stateful한 상태이다. 소규모 서비스에서는 Stateful하게 동작해도 부하가 발생할 여지가 적겠지만 서비스가 발전하면서 인증을 요구하는 사용자가 늘어나고 서비스를 확장하려면 몇 가지 문제를 고려해야 한다. 우선, 서버 메모리에 Session을 저장한다는 점이 모든 문제의 근원이 된다.

세션 인증의 장점

• 인증 절차의 안전
  세션 정보를 서버 측에서 관리하기 때문에 중간에 탈취되어도 공격자에게 유의미한 정보를 제공하지 않는다. 또한, 클라이언트가 변조되어 세션 Id 값이 변경되어도 재인증을 요구하면 그만이다. 따라서, 클라이언트의 변조나 인증 데이터의 손상에도 타격이 크지 않다.

• 인증 상태 확인
  서버 메모리 혹은 데이터베이스에서 세션 Id를 비교하는 작업을 수행하기 때문에 실제 서버에서 인증 여부를 확인하기가 쉽다.

세션 인증의 단점

• 세션 유지의 문제(Stateful)
  서버 메모리에 세션을 유지하는 경우 임의로 만료(expire) 시점을 지정하지 않았다면 사용자가 시스템에 활성화된 상태가 유지되었을 때 계속 인증된 상태로 남겨두고 사용자가 시스템에서 떠나면 세션을 만료시켜 다시 재인증을 요구해야 한다. 그러나, HTTP 요청 특성이 stateless하다는 점으로 인해 사용자가 정말 활성화된 상태인지 결정하기 위한 별도의 로직이 필요하다. 만약, 사용자 활성화 여부를 서버 접근 시간을 기준으로 임계 시간이 초과되었을 때 세션을 해제한다고 가정했을 때 인증용 서버가 여러 대인 경우 여러 서버에 접속한 경우에는 각 서버들 간의 동기화 문제 등등 고려할 점이 너무나도 많다.

• 세션의 부하와 확장의 문제
  사용자가 늘어나면 더 많은 트래픽 처리를 위해 서버 메모리에 Session을 더욱 많이 저장한다. 서버 메모리에 저장하기도 하고 메모리 부하를 줄이기 위해 데이터베이스를 이용한다. 데이터베이스를 사용하더라도 세션 조회 및 수정에 어마어마한 양의 R/W작업이 필요하고 DB도 메모리와 마찬가지로 많은 부하를 견뎌내야 한다. 따라서, 서버는 저장된 Session 관리 로직 최적화를 위해 여러 프로세스를 생성하거나 서버 사양을 업그레이드 하거나 분산하는 Scale 문제가 발생한다. 서버를 여러 대 둔다고 하더라도 세션 정보가 존재하지 않는 서버에 인증 요청 시 재인증을 요청하는 문제를 해결하기 위해 session clustering 등 다양한 방법의 시도가 있음에도 그 비용으로 인해 결국 대규모 서비스에서는 세션 기반 인증이 불리한 점이 많다.

• CORS(Cross-Origin Resource Sharing) 설정
  쿠키는 단일/서브 도메인에서만 동작한다. 그런데 한 회사가 여러 서비스로 확장하고자 하며 대신 인증 과정에서 그 회사의 인증 정보를 사용하고자 한다면 여러 서비스에 대한 통합된 인증을 구현해야 한다. 그러나, 도메인이 다를 수 밖에 없는 상황에서 쿠키는 방해요소가 된다. 이를 해결하기 위해 별도의 절차를 수행해야 하는데 꽤나 번거로운 작업이 요구된다.

• 멀티 디바이스 문제
  여러 디바이스에서 동일한 사용자에 대한 인증이 발생했을 때 상황을 생각해야 한다. 동시에 인증을 요구할 경우 이를 허용할 것인지에 대한 정책 수립이 필요하다. 게다가 모바일 서비스인 경우 별도의 컨테이너를 구상해야 한다는 점 또한 쿠키를 도입하기 어렵게 만드는 요인으로 작용한다.

토큰 인증(Token Authentication)

쿠키를 사용해서 기존 로그인 시 수행했던 작업을 저장하곤 하지만 대부분의 서비스에서 "인증"만큼은 토큰 기반으로 수행하는 경우가 많다. 특히 JWT(Json Web Token)이라는 키워드로 많이들 등장한다. 클라이언트가 인증에 성공하면 특별한 토큰을 제공해 사용자가 이미 인증을 수행했음을 증명하는 방식이다. 일반적으로 서버가 발급한 토큰을 "접근 토큰(Access Token)"이라 부르며 클라이언트가 서버에 해당 토큰만을 제시하여 모든 인증 절차를 수행할 수 있어야 한다.
우선 클라이언트가 인증절차를 수행하면 서버는 signed 토큰을 발급한다. 클라이언트는 이후 토큰을 갖고있다면 해당 토큰을 서버로 전송하여 인증을 수행한다. 다만, 해당 토큰을 인증 과정마다 전송하면 중간에 탈취되는 경우가 발생할 수 있다. 토큰이 탈취되는 문제를 해결하기 위해 일반적으로 signed 토큰의 유효기간을 짧게 설정한다. 네이버의 경우 1시간으로 설정되어 있다. 대신 비교적 유효기간이 긴 refresh 토큰을 발급하여 signed 토큰의 유효기간이 만료되면 refresh 토큰을 서버로 전송하여 새로운 signed 토큰을 발급받는다. 이로써 클라이언트의 토큰이 탈취되더라도 유효기간이 지나면 새로운 토큰을 확보해야 하는데 새로운 토큰은 refresh 토큰으로 생성되므로 탈취된 토큰을 무한정으로 사용할 수 없다는 이점이 있다. 다만, refresh 토큰이 탈취될 수 있다는 위험이 존재하며 signed 토큰이 만료되었을 때만 refresh 토큰이 전송되므로 빈도를 낮춤으로써 대응한다고 볼 수 있다.

그림에서는 Resource Server에서 Verification을 수행한다고 표현하였는데 Token Server로 요청을 보내 valid 여부를 체크하는 방법도 사용할 수 있다.

토큰 인증의 장점

• 무상태성(Stateless)으로 인한 서버 확장 용이
  세션과는 달리 인증 정보의 저장을 클라이언트에 맡김으로써 서버는 유효 스트링 여부와 기간만료 여부만 검증하면 된다. 따라서 클라이언트와 서버가 서로 연결되지 않고 Stateless한 상태임이 보장된다. 따라서, 확장 시 scale out 방식을 채택하더라도 검증 로직만 제대로 동작한다면 별다른 비용 없이 수행할 수 있다.

• 확장성
  쿠키가 단일/서브 도메인에 대한 정보만 저장할 수 있는 문제점으로 인해 CORS 설정을 추가적으로 고려하는 문제가 있었다. 그에 반해 토큰은 도메인과 상관없이 토큰 인증 서버로만 제대로 요청한다면 인증 절차 상 문제가 발생하지 않는다. 즉, 서비스 확장이 용이하다. 실제로 Google, Naver, Kakao 등 소셜 계정을 제3의 서비스 인증에 사용할 수 있는 이유가 토큰 기반 인증을 도입했기 때문이다.

• 멀티 디바이스 환경
  모바일 환경에서도 Json 데이터(JWT)만 핸들링하면 별다른 조치할 것 없이 인증 절차를 수행할 수 있어 세션 기반 인증방식보다 유리하다.

토큰 인증의 단점

• 토큰의 크기 문제
  토큰은 기본적으로 Session Id보다 크기가 크다. 사용자 식별 텍스트, 유효기간, 검증용 스트링 등 인증에 필요한 정보들을 JWT에 담아서 주고받기 때문이다. 그에 따라 HTTP Request가 무거워질 수 있으나 유의미한 차이는 아니다.

• 토큰 검증의 서버 부하
  유효한 토큰인지 검증하기 위해 검증용 스트링을 제때 생성하지 않는다면 DB에 검증용 정보를 저장하여 조회함으로써 수행하거나 토큰 발급 기관의 인증서버로 valid 여부를 검증 요청할 것이다. 그렇다면 DB에 검증정보를 저장한다면 blacklist 기반으로 접근하여 일치 여부를 판별할텐데 조회요청이 많아지면 결국 DB에 부하가 발생할 수 있고 발급 기관에 인증 요청을 한다면 발급 기관의 인증 서버에 부하가 발생할 수 있다.

• 토큰의 탈취 문제
  클라이언트에 인증 정보를 저장하기 때문에 탈취되는 경우 공격자에 의해 악용될 수 있다. 다만, 이 문제는 토큰의 유효시간을 짧게 설정함으로써 해결할 수 있다.

참고자료

• API Authentication – Tokens vs Sessions
• Session 기반 인증과 Token 기반 인증
• [Server] 토큰 기반 인증 VS 서버(세션) 기반 인증

벌써 두 번째로 참가하는 데브매칭 코딩테스트다. 이번에는 실리콘 밸리를 테마로 미국 실리콘 밸리에 본사를 둔 회사들을 대상으로 진행되었다. 물론 대부분 한국 서비스를 위주로 운영하고 있는데 미국에 본사가 재소하고 있는지 여부에 추후 엑시트 시 단가가 거의 10배는 뛴다는 점으로 최근 많은 회사들이 실리콘 밸리로 본사를 이전하고 있다. 10시 코테는 역시 뭔가 참가하기가 버겁다. 일어나고 씻고 밍기적대다가 결국 15분이나 지각해버렸다. 늦게 자서 늦게 일어나는 버릇을 얼른 고치던가 해야겠다.

문제는 엄청 쉽진 않으나 또 엄청 어렵지도 않았다. 다만, 구현에 있어 생각해야 할 점이 조금 있고 엣지 케이스 고려가 선행되지 않으면 테스트케이스를 전부 통과시키기가 어려웠다. 그래도 히든케이스 채점결과를 공개해주는 코테는 볼 때마다 항상 감사한 마음이다. 히든케이스를 공개하지 않으면 테스트케이스를 제출해도 영 찜찜하다. 순위를 기록하는 리더보드를 지원했던데 다른 여타 알고리즘 대회보다는 역시 참가풀 수준이 그렇게 높진 않았나보다. 필자는 종료 50초 전에 모든 문제 100점을 받아 간신히 총 300점으로 올솔하였다. 결과를 보니 36등인걸 봐선 300점 만점자가 36-7명 쯤 될 것이다. 참가인원이 1200명인데 36등이라는 결과가 굉장히 고무적이라 기분은 좋다. 물론, 다른 대회였다면 어림도 없을 풀이속도였다. 난이도를 평가하자면 일반 국내기업 코딩테스트 수준으로 나왔다 생각한다. 여기서 한 문제가 더 나왔으면 무난하게 2-3솔이 합격컷이었을 것이다.

1번은 구현, 2번은 정렬을 위한 데이터 전처리, 3번은 약간의 수학과 구현이 요구되었다. 파이썬으로 풀어서 그런지 2번 정렬은 labmda 표현식으로 한번에 정리되어 버리는 바람에 너무 빠르게 풀었고 1, 3번은 나름의 수학적 직관을 요구했어서 은근 만점을 받는 인원이 별로 없었다.

물론 데브매칭 특성 상 지원서를 받은 기업이 서류통과 사인을 줘야 면접까지 진행을 하겠지만 일단 모두 풀었다는데 의의를 둬야지. 최근 면접 및 자바 관련 공부를 진행하면서 알고리즘에 소홀한 감이 있었는데 아직 실력이 많이 죽진 않았나보다.

후속 포스팅

2021 Dev-Matching: Silicon Valley 추가 전형 진행 후기

제대로 시간을 들여 공부한 뒤 응시한 첫 번째 기술면접이었다. 이전 올거나이즈 기술면접은 스스로도 전혀 공부하지 않고 응시했기에 처참했으나 이번엔 그런 수치스러운 상황은 면해야 한다는 각오로 준비했었다. 그러나... 음... 모르겠다 솔직히

결론부터 말하자면 대참사는 벌어지지 않았으나 그렇다고 잘 봤다는 확언도 못하겠다. 빨리 푼다면 6-7문제도 풀 수 있다는데 3문제만 제시받았고 추가로 cs 지식 검증도 내가 제일 약하다고 생각했던 개념이 나와서 멘붕한 채로 어떻게 이걸 구조화해서 답변할 지 전혀 감도 잡히지 않은 채로 뇌에 남아있는 지식을 필터없이 토해내고 말았다. 이 cs문제를 낸 면접관님은 다른 문제에서도 내가 약하다고 생각한 부분들만 콕콕 찝어내는 걸 보아하니 우연이 아니라 기록, 제출한 내용들을 보고 좀 약할 거 같은데 싶은 항목들을 골라내는 아주 강력한 고수가 아니었을까 하는 의심이 든다. 3문제 중 두 문제는 완전히 헤매다가 면접관님이 힌트를 한 개 주셔서 해결했고 한 문제는 힌트없이 해결했으나 심화 문제에서 막히고 말았다.

출제된 문제는 전반적으로 기본적인 직관과 센스가 있나 보는 것 같고 문제 난이도는 그렇게 어렵다고 생각이 들진 않는다. 다만 긴장된 상황이라 당당히 힌트를 요구할 생각도 들지 않았고 사소한 실수나 놓친 부분이 발생하면서 잘 봤다는 판단이 서지 않는 요인이 되었다.

자소서는 자신이 없다면 아예 내용을 빼버리고 당당하게 해봤다는 내용만 작성하길 바란다. 문항 하나를 그 당시 진짜 어려웠다고 생각해서 썼는데 생각해보니 그걸 극복하기 위해 어마어마한 공부를 한 건 또 아니라서 면접관에게 솔직히 그거 잘못 썼다고 시인했다 '-`...

1차 면접의 목적은 지원자 개인에 대해 역량을 구체적으로 파악하고 능력을 검증한다기 보다는 평준화된 문제들을 제시하면서 지원자의 직관이 얼마나 좋고 높은 포텐셜을 가지고 있는 지원자인지 본다고 생각한다. 그런데 생각보다 나의 의욕있는 모습과 발전에 대한 열의를 잘 보여주지 못한 것 같아 일단 결과를 지켜봐야겠다. 애초에 긴장감은 자신이 그만한 실력을 키우지 못했다는 스스로의 의심에서 비롯된 감정이니 내 스스로 아직 부족함을 알고 노력해야지. 기대가 크면 실망도 큰 법이니 내일부터는 다시 마저 하던 공부나 이어나가야겠다. 그래도 면접관님들이 분위기를 풀어주기 위해 리액션을 엄청 열심히 하시고 좋게 진행해주셔서 트라우마로 남지 않았다. 개인적으로는 너무 좋았던 경험을 받아 감사했다.

결과: 기술면접 2차 통보받았습니다. 솔직히 반반이라 생각했습니다만 면접 복기하면서 풀이가 아쉬웠다거나 제대로 말하지 못한 내용들이 계속 뇌리에 스쳤습니다. 어쩌면 불합격일 가능성도 있겠다고 마음의 준비를 했으나 다행히 좋게 봐주신 듯합니다. 2차는 인성면접이라고들 말하지만 1차에 기술검증을 제대로 하지 못한 경우 기술질문도 들어올 수 있다하니 광범위하게 준비해봐야겠습니다.

- 후속 포스팅

2021 하반기 네이버 2차 면접 후기