재시민

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 c++에는 내장 라이브러리로 존재하는 binary_search, lower_bound, upper_bound가 존재하지 않느다. 따라서, 우리는 이분탐색을 "직접" 만들어야한다. 이분탐색에 대해 알아보자

Binary Search

const binarySearch =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left <= right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] === target){
            return mid;
        }else if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return -1;
}

Lower Bound

const lowerBound =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

• lower bound 는 배열에서 타겟값 이상이 처음으로 나타나는 위치를 찾는다.
• 이분탐색 하다가 target 값 이상인 left 값이 타겟값을 넘는 첫 위치다.

Upper  Bound

const upperBound =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] <= target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

• upper bound 는 배열에서 타겟값보다 큰 값이 나타나는 첫 위치를 찾는다.
• 타겟값을 초과하는 인덱스를 반환한다.

이분탐색 vs lower, upper

• 이분탐색은 탐색값을 찾는것 이므로 while의 조건이 left<=right다.
• lower, upper 는 탐색값의 바운더리를 찾는 것 이므로 while의 조건이 left < right다.

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 흔하디 흔한 우선순위큐는 내장되어있지 않다. 따라서, 우리는 우선수위큐를 "직접" 만들어야한다. 우선순위큐에 대해 알아보자

우선순위 큐

생성자

constructor(){
    this.heap = [];
}

• heap 배열을 초기화하는 생성자다.

삽입 enqueue

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }

• heap 배열에 value를 push하고 힙정렬을 진행한다.

삭제 dequeue

dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
}

• 삭제하려는 값은 맨위의 최소값이므로 (현재 코드는 최소힙을 기준으로 작성) 0번째 인덱스와 마지막인덱스를 교환한다.
• 다시 힙정렬을 진행한다.

heapifyUp() 위쪽으로 재정렬

_heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
       //우선순위큐는 이진트리를 기반으로 하기때문에 
       //parentIndex 는 자식 노드의 인덱스에 절반과 비슷하다.
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];
        //부모보다 크기때문에 최소힙 성립
      if(element >= parent) break;
        //그렇지 않으면 부모와 자리바꾸기
      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
 }

• 값을 삽입하면 오름차순으로 정렬해야한다. (삽입한 값이 맨뒤에 있다.)
• 삽입된 위치(index) 값부터 (heap 배열에 push 했으므로 맨끝값) 부모 노드를 탐색하면서 바꿀 값을 찾는다.

heapifyDown() 아래쪽으로 재정렬

_heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
    //자식 인덱스를 확인
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;
    //왼쪽자식부터 부모가 더 크다면 바꿔야할 인덱스로 판명
      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }
    //오른쪽자식
      if(rightChildIndex < length){
      //왼쪽을 안바꿔도되고(null), 오른쪽 자식의 값이 부모보다 작다면 바꿔야한다.
      //왼쪽을 바꿔도되고, 오른쪽 자식의 왼쪽 자식의 값보다 작다면 오른쪽 자식을 바꿔야한다.
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

    //바꿀게없다면 패스
      if(swapIndex === null) break;
    //부모와 자식을 바꾼다.
      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }

• dequeue 를 하게 되면 맨위에 값이 최대값으로 바뀌기 때문에 자식을 탐색하면서 정렬해야한다.

전체 코드

class PriorityQueue{
  constructor(){
    this.heap = [];
  }

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }

  dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
  }

  _heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];

      if(element >= parent) break;

      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
  }

  _heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;

      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }

      if(rightChildIndex < length){
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

      if(swapIndex === null) break;

      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }
}

필기 전형

필기 전형에는 LG way fit, 코딩테스트를 본다. 

LG Way Fit

인적성 검사 결과를 1년이나 가지고 있는줄 몰랐다.. 작년 유플러스 시험볼때 가뜩이나 무참히 망쳤는데.. 이걸 다시 쓰다니 ㅠㅠ 코테를 엄청 잘보지 않는 이상 괜찮을까??

이번에 20문제에 20분으로 바뀌었다는데.. SKCT 보다 더 어려웠다는 후기가 들린다. 오히려 좋을지도??

코딩테스트

1. Set 을 사용한 일반 구현 문제 (실5)
   1. 두가지 정수를 곱한 후 그 값이 곱한 두가지 값이 포함이 되어있는지? 에 대한 문제였다. 그냥 문자열로 바꾸고 set에 모든 경우의 수를 넣은 후 사이즈를 출력했다.
2. 시뮬레이션 (실2)
   1. 관람차를 타는 문제. 몇 초동안 기구를 타고싶어하는 사람들과 그 사람들이 관람차 다 타고 내려왔을 때 시간을 구하는 문제.
   2. 삼성 시뮬레이션으로 단련된 나의 실력 덕분에 무난히 풀 수 있었다.
3. DFS + dijkstra (골4)
   1. 노드간 간선을 만들고, 조건을 만족하는 노드를 찾은 후 그 위치에서 처음 위치로 가장 빠르게 돌아오는 최단시간
   2. 조건을 만족하는 노드 찾기 - dfs
   3. 찾은 노드에서 되돌아오기 - dijkstra

후기

전체적인 문제 난이도가 평이했다. 1,2 번 40분 정도 풀었고, 나머지 1시간 20분은 3번 문제에 투자했다. 평소에 다익스트라 알고리즘 자꾸 까먹어서 시험 보기 전날 몇문제 풀었는데 3번 문제가 나와서 너무 반가웠다.. 그래도 알고리즘을 정확히 기억 못해서 몇번 애먹었지만 dfs와 다익스트라를 결합하니 테스트케이스에 통과했다. 스몰케이스도 넣어가면서 정확성을 확인했는데 라지 케이스에서는 어떻게 될지 모르겠다.

예상결과 : 3솔

코딩 테스트 합격!

코딩 테스트에 합격하니 신한카드 본사에서 1차 면접 일정이 발표되었다. 면접 발표 일주일 바로 뒤라니..! 정말 짧은 시간 이었다. 1주일이라는 시간 동안 학교 선배에게 자문을 구하고, 싸피 컨설턴트님에게 방향성을 제시받고, 취업 스터디에서 모의 면접을 하며 기다렸다.

내가 부족한게 왜 카드사인지에 대한 목적의식과 싸피와의 직무 연결성이 부족하다고 느꼈고 두가지 위주로 준비했다.

면접 당일

8시 30분까지 신한카드 본사로 이동하니 문앞에 시큐리티분들과 컨택후 마치 회사원인 것 처럼 게이트에 입장했다. 같이 타는 직원들에게 인사라도 해야하나 생각이 들 때쯤 3층에 도착했다. 3층에서 명창을 수령하고, 강당에 입장했다.

강당에서는 1시간 30분 가량 신한카드 소개, 데이터 팀, AI 팀 발표를 진행했다. 가뜩이나 당일 긴장이 좀 덜되었는지 졸음을 참느라 진짜 죽을 뻔 했다. 길고 긴 소개 시간을 지나 5개의 조로 나뉘어 면접실로 이동했다. 우리팀은 다른팀에 비해 두명정도 적었다.

오전

• 오전에는 1분 자기소개 후 팀 프로젝트를 진행했다.

1분 자기소개

• 간단하게 자기소개 후 팀을 두개로 나누어 짠다.

팀 프로젝트 발표 면접

• 나뉘어진 팀마다 공통 주제에 따라 발표자료를 작성한다.
• 이번 주제는 ‘멀티앱과 슈퍼앱 그리고 당사가 취해야할 방향’ 이었다.
• 챗지피티를 총 3번 사용할 수 있다.
• 50분 준비 후 5분 발표 5분 질의응답을 진행한다.

점심

• 면접관님들과 즐거운 점심시간! 나는 재미있긴했는데 친구들한테 면접관이랑 점심 먹었다니까 부담된다고 하긴하더라.. 나는 그냥 좀 나이든 형이랑 밥먹는 느낌 ㅋ

오후

• 오후에는 개인 면접과 토론 면접이 진행됐다.

All That Sales, 개인 면접

• 세일즈 문항을 면접 대기 직전에 받고 10분간 문항에 대한 답변을 작성한다.
• 면접에 들어가자마자 문항에 대한 답변을 얘기한다.

개인 면접

• 자기소개서에 Next, React 에 관한 내용을 작성했더니 질문 폭탄이 아닌 질문 핵폭격 수준으로 들어왔다. 하지만, 개념 공부는 js 에 그친 나에게는 모르쇠로 일관할 대답밖에.. 정말 너무 아쉬운 면접 경험 이었다……..
• 다른 면접자들 얘기들어보니 기술 질문 많이 안들어왔다고 했는데 나는 처음부터 끝까지 기술 면접이었다. ㅠㅠ

토론면접

• 개인면접 대기 시간에 3문항의 토론 주제를 준다. 문항에 대해 찬 반 의견을 정리하고 있는것이 좋다.
• 개인 면접 종료 후 두개의 팀으로 다시 나뉜다. 두개의 주제를 정해서 토론을 진행한다. 토론 준비는 5분밖에 주어지지 않는다.

나는 정말 토론을 못한다. 준비가 제대로 되어있지 않은 상태에서 논리적으로 상대의 주장에 반박하지 못한다. 따라서, 토론면접에서 너무 힘들었다. ㅠㅠ .. 그래도 열심히 들으며 정리한 상대방의 내용 중 궁금하거나 말이 안되는 부분을 질문했지만 자꾸 딴길로 새서 토론이 이상해졌다 ㅋㅋ ㅠㅠ

마무리

모든 면접이 끝나고 신한카드로 만들어진 5만원 기프트카드와 베이글 샌드위치를 받았다. 나는 저녁 약속이 있어 베이글은 먹지 않았다. 면접관들에게 궁금한 점 물어보면서 6시까지 시간을 보냈다.

후기

• 프론트엔드 개발자로서 아직 많은 부분이 준비가 되어있지 않다는 것을 알게해준 면접이었다. 그 덕분인지 기술 준비에 더 불이 붙게되었다.
• 솔직히 기대는 되지 않는다. 그래도 면까몰이라지만 ㅠㅠ 내가 너무 보여준게 없었다.
• 준비 더 해서 다른 면접에서는 이런식의 대답을 하지 않기를..