collections의 Counter 활용

여지까지 리스트내의 값을 key:value(등장 횟수) 형태인 dictionary 자료형으로 만들때 일일이 for문으로 순회를 하면서 value 값을 증가 시켜주었는데, 이번 커뮤러닝을 통해 참여하신 분 중 한 분이 내 코드에 리뷰를 해주셨는데, collections의 Counter를 활용하면 더 간결하게 코드를 작성할 수 있다고 해서 코드를 다시 작성해보았는데, 리뷰해주신 내용대로 코드가 훨씬 간결해졌다.

DFS(Depth-First-Search) 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 가장 단순한 방법이다.
현재 정점과 인접한 간선들을 하나씩 검사하다가 방문하지 않은 정점으로 향하는 간선이 있다면 해당 간선을 따라가 정점을 검사하고, 더 이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고 마지막에 따라왔던 간선으로 되돌아간다.
거쳐왔던 모든 정점들에 대한 정보를 저장하기 위해서는 재귀호출을 이용해서 간단하게 해결할 수 있다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이다.

무엇을 하든 기초가 정말 중요하다. 이전에 한 번 이 트리순회를 공부했을때에는 단순히 코드작성과 단순 이해만 했기 때문에 문제에 제대로 응용이 되지 않았던 것 같다.
그래서 이번에는 한 번 직접 손으로 스택 내부에 스택 프레임이 어떻게 쌓이는지 그려보며 내부의 재귀형태의 함수 호출은 어떻게 이루어지는지 살펴보았다. 또 스택과 함께 트리 구조도 어떻게 가지치기를 하는지 살펴보았다.

나중에 다시 복습을 위해 직접 그려 본 스택의 프레임과 트리구조를 아래에 첨부한다.

재귀함수의 동작을 스택 프레임과 연관지어 이해

아래에 작성한 간단한 재귀함수의 동작방식을 스택 프레임과 연관지어 설명해보려고 한다.
이미 재귀함수는 문제풀이나 기본적인 개념이해는 되었지만, 스택과 연관지어 기본적인 동작방식을 설명해본적은 없기 때문에 이번 포스팅을 계기로 한 번 정리를 해보려고 한다.

결정 알고리즘은 이분검색을 기반으로 한다.

알고리즘 문제에서 주어진 조건에서의 최대값 혹은 최소값을 구하는 문제 중에 몇 몇 문제는 결정 알고리즘(Decision algorithm)을 활용해서 풀이해야 한다.
결정 알고리즘은 이분 검색을 기반으로 하는 문제로, 전체 데이터를 순회하면 시간 복잡도 O(N)을 갖지만 이분 검색으로 데이터를 검색하면 O(logN)만큼의 시간 복잡도를 갖는다.

예시문제
길이가 N인 숫자 리스트가 있다고 가정했을때, 총 T 개의 그룹으로 리스트를 나눠야 한다.
T개의 그룹으로 리스트를 나눴을때 한 그룹당 최소 얼마의 숫자합이여야 하는지 구하시오.

기본 정렬 알고리즘 구현하기

이 기본 정렬 알고리즘은 직접 손 코딩 할 수 있을 정도로 코드를 익혀야 하기 때문에 반복 복습을 위해 블로그 포스팅을 해두기로 했다.
코딩 테스트 문제를 풀때 내장된 sort 함수를 사용해서 간편하게 정렬을 해서 문제 해결을 하지만, 기존에 있는 정렬 알고리즘의 구현을 이해하고 필요에 따라 기존 정렬 알고리즘을 응용해서 새로운 알고리즘을 만들어 낼 수 있는 능력도 필요하다.
그럼 자바스크립트 언어로 코딩테스트를 준비하고 있기 때문에 자바스크립트로 각 기본 정렬 알고리즘을 구현 및 정리를 해보겠다.

선택정렬(Selection sort) - O(N^2) 시간복잡도/정수 6만개 기준, 10.842(sec)

우선 선택 정렬에 대해서 코드 구현을 하기 전에 간단하게 선택정렬을 어떻게 구현해야 되는지 설명을 하겠다.
선택정렬은 버블정렬과 같이 1회 순회에 한 개 요소의 위치가 결정이 된다. (가장 작은 값(왼쪽부터 오른쪽으로) 결정)
이중 for-loop의 형태로 i: 0 ~ arr.length, j: i+1 ~ arr.length로 순회를 한다.
그리고 j의 범주로 순회를 하면서 가장 작은 값의 index를 찾는다. 가장 작은 값의 index를 찾았다면, 최소값의 index위치와 i번째 index위치를 바꿔준다. 이 과정을 i의 범주로 순회를 하면 정렬이 완료된다.
그럼 코드로 한 번 구현을 해보겠다.

1
2
3
4
5
6
7

for (let i = 0; i < arr.length; i++) {
  let index = i;
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[index]) index = j;
  }
  [arr[i], arr[index]] = [arr[index], arr[i]];
}

큐를 활용한 문제풀이

이번 포스팅에서는 자바스크립트로 큐(queue)를 이용한 문제풀이에 대해서 사용되는 배열의 메서드에 대해서 간단하게 정리하고 관련 문제를 풀이해보려고 한다.

우선 pop과 push의 경우에는 배열의 맨 마지막 요소를 빼거나(pop) 추가(push)할때 사용하고, shift는 배열의 맨 앞 요소를 빼고, unshift는 맨 앞에 요소를 추가할때 사용한다.

• 배열을 일정 길이로 초기화하는 두 가지 방법

1
2
3
4

// index를 값으로 갖는 길이가 10인 배열 만들기
new Array(10).fill(null).map((v, i) => i);
// Array의 정적 메서드 from을 사용하여 길이 및 내부 요소값 초기화하기
Array.from({ length: 10 }, (v, i) => i + 1);

• 문제풀이

  길이가 N개인 배열에서 0번째 인덱스부터 M번째 떨어진 숫자를 배열내에 한 개의 숫자가 남을때까지 반복해서 제거한다고 했을때 최종적으로 남을 단 하나의 숫자는 무엇인가?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

const fs = require('fs');
const stdin = (process.platform === 'linux' ?
  fs.readFileSync('/dev/stdin').toString() :
  `8 3`).split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

{
  const [n, m] = input().split(' ').map(n => +n);

  const queue = Array.from({ length: n, (v, i) => i + 1});
  let answer;

  while(queue.length){
    for(let i = 1; i < m; i++){
      queue.push(queue.shift());
    }
    // 세 번째 요소는 그냥 shift
    queue.shift();
    if(queue.length === 1) answer = queue.shift();
  }
  console.log(answer);
}

이번 포스팅에서는 Sliding window, Map, Two pointer algorithm을 복합적으로 사용하여 풀이한 알고리즘 문제에 대해서 정리를 해보려고 한다.

효율성을 전혀 고려하지 않은 이중 for문의 사용을 자제하고 앞의 세 가지 개념을 활용하여 코드를 구현한다면 효율성을 극대화시켜서 코드를 작성할 수 있을 것이라고 생각한다.

우선 하나의 문제를 예시로 내가 처음에 구현한 코드와 다른 사람이 구현한 코드 두 가지를 비교분석해보자.

문제는 문자열 S와 T가 주어졌을때 문자열 S에서 T문자열과 아나그램이 되는 부분 문자열의 갯수를 출력하는 문제이다.

이 문제를 처음 보았을때 Sliding window, Map, Slice method를 사용하여 문제를 풀이해야 겠다고 생각했고 아래와 같이 코드를 작성했다.

우선, 아나그램인지 아닌지 판별하기 위한 개별함수를 선언(checkAnagram() function)한다.
그 다음에 초기에는 입력받은 문자열(is)를 검색 문자열(ss)의 길이만큼 slice해서 확인용 문자열 변수에 별도로 저장을 해준다.

Consecutive number subsequence(연속 부분수열)과 Number subsequence(부분수열)

이번 포스팅에서는 연속 부분수열과 부분수열에 대해서 이야기해보려고 한다.

위 두 개념에 대해서는 알고리즘 문제풀이를 하면서 접하게 되었는데, 그 풀이방법에 대해서 왠지 정리해두면 나중에 유용할 듯 싶어 블로그 포스팅하기로 했다.

우선 연속 부분수열에 대한 문제풀이에서 사용한 코드 패턴을 살펴보자.
이름에서 예상할 수 있듯이 연속된 수들의 부분집합으로 이해할 수 있다. 만약에 N개의 숫자가 주어졌을때 수들의 합이 주어진 값인 S와 같은 연속 부분수열의 갯수를 구해야 한다면 어떻게 코드 구현을 해야할까?
바로 아래와 같이 코드를 구현할 수 있다.

알고리즘 효율성 (Two pointer algorithm, Sliding window, Hash)

이번 포스팅에서는 알고리즘의 효율성에 대해서 이야기해보려고 한다.

아래의 코드는 주어진 두 배열을 합쳐서 합쳐진 배열을 오름차순으로 정렬하는 문제를 구현한 코드이다.
처음에 이 문제를 보았을때 들었던 생각은 spread 문법을 사용해서 주어진 두 배열을 하나의 배열로써 unpacking한 다음에 sort() 함수를 사용해서 오름차순 정렬하는 방법을 생각했다. (solution 1)

그런데 sort()함수를 사용해서 N개의 숫자를 정렬하는 경우에는 시간복잡도 O(NlogN)만큼의 시간 복잡도를 갖는다.

그렇다면 좀 더 시간복잡도상 효율적인 코드를 작성할 수는 없을까?

단순히 결과값이 나왔다고 좋아하지 말고 좀 더 효율적인 코드를 작성할 수 있도록 생각하고 또 생각해야 한다.