재시민

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 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솔

2024 하반기 신한카드 ict 개발 인적성검사 + 코딩테스트 후기

거짓말 같이 서류를 합격해버리기

인적성검사

프로그래머스 플랫폼을 사용한 인적성 검사 환경이었다. 공지된대로 언어, 수리, 공간지각, 문제해결이었다. 총 60문제 1시간안에 풀어야한다. 비슷한 시험으로는 SKCT가 있다.

인적성 준비

우선, 신한카드 인적성에 관한 정보가 부족해 시중에 판매하고 있는 기업별 인적성 모음집을 구매해서 시간을 재며 풀었다. 유형에 관한 준비가 필요하다고 생각했다. 온라인 환경에서 준비해야하다보니 온라인으로 연습해야한다. 프로그래머스에서 메모장은 지원해주니 암산하는 실력을 기를 수 있다면 좋다.

인적성 난이도

시험 난이도는 대체적으로 무난했다. 문제해결 과목이 인적성 ‘추리’ 느낌인 줄 알았는데 NCS ‘문제해결’ 스타일이었다. 직급 관리도? 에서 상황을 제시했을 때 올바른 문항을 고르는 문제가 많았다. 공간지각은 주사위 전개도, 블럭쌓았을 때 예상되는 상하좌우 모습, 블럭 두개를 주고 만들 수 있는 블럭 이런 문제가 나왔다. 수리는 그냥 무난한 수리 문제들, 언어도 대체적으로 비슷한 문제들이었다. (기억이 안나서 비슷하다고 둘러댄건 비밀)

결과

코딩테스트

프로그래머스 플랫폼을 사용한 코딩테스트 환경이었다. 트렌드와는 조금 다르게 서울역 근처에서 오프라인 시험을 봤다. 개인 노트북 지참에 랜 젠더도 가져와야하는 환경에 조금 낯설었지만 쿠팡에서 괜찮은 놈으로 하나 장만했다.

사용 가능한 언어로는 왠만한 언어는 다됐다. 시험 구성은 4문제 (알고리즘 3 + SQL 1) 이었다.

시험 난이도

1. 맵을 사용해 문자열 횟수를 세고 규칙에 따라 제거하는 문제였다. 난이도는 예상 실버 4~5
2. 이분탐색을 사용한 문제였다. 평소에 이분탐색이 약해 전날 준비 했는데 준비하길 잘한 것 같다. 난이도는 실버 1~2
3. DFS를 사용한 문제였다. 지금 생각해보면 크기가 150이었던 것같은데 시간초과 날 것 같다. 아마도 DP를 사용해야하는 것 같은데 ㅠㅠ 아멘.. 예상 난이도는 골드 4
4. union all ,group by, join 전부다 활용된 문제였다. 문제가 맞았는지는 모르겠다. 여튼 고생많이해서 풀긴했는데 맞았으면..

예상 결과 : 3 ~ 3.5 솔