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

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

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

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

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

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

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

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

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

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

기본 알고리즘 문제 Pseudo code + JavaScript code

내가 처음 풀이한 코드인데 소수인지 아닌지의 판단을 1부터 자기자신의 숫자 범위내의 숫자로 나눴을때 0으로 나누어 떨어지는 경우의 수가 2인 경우(1과 자기자신)에 결과 리스트에 담아서 정답을 출력하였다.

나의 풀이에서는 1부터 자기자신의 숫자까지 모두 순회를 하였는데 이렇게 순회를 할 필요가 없다.
2부터 자기자신의 제곱근까지의 범위의 숫자로 나눠서 0으로 떨어지는 경우가 있다면 이는 소수(Prime number)가 아니기 때문에 이런 식으로 문제를 해결할 수도 있다.

Solution 1

기본 알고리즘 문제 Pseudo code + JavaScript code

처음 이 문제를 보았을때 생각났던 구현방법으로 Set()자료형이 생각이 났다. 우선 주어진 문자열을 압축하는 것이기 때문에 반복되는 문자를 생략해서 표기해야 되기 때문이다.
그래서 아래에 첨부한 코드와 같이 처음에 입력받은 문자열을 Set() 객체로 만들어서 중복되는 문자를 제거해줬다.

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

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

{
    const inputWord = input();
    let noRepeatWord = new Set(inputWord);
    let noRepeatWordList = [...noRepeatWord];

    for (let i = 0; i < noRepeatWordList.length; i++) {
        let repeatCount = 0;
        for (let w of inputWord) {
            if (noRepeatWordList[i] === w) repeatCount += 1;
        }
        if (repeatCount >= 2) noRepeatWordList[i] += repeatCount;
    }
    console.log(noRepeatWordList.join(''));

기본 알고리즘 문제 Pseudo code + JavaScript code

오랜만에 이런저런 생각을 해 볼 수 있었던 알고리즘 문제인 것 같아 블로그에 포스팅 글로 남기기로 했다. 표면적으로는 매우 간단해보이는 문제이지만 그 접근방식에는 다양한 것 같다.

처음 이 문제를 보았을때 생각났던 구현방법으로 split()과 재귀호출 이 두 가지 방법이 생각이 났다.
주어진 문자열에서 특정 문자를 기준으로 구분되는 각 문자열들의 특정 문자로부터의 거리를 구하는 프로그램을 작성하는 문제인데 처음에는 아래와 같은 방식으로 Pseudo code와 JavaScript 코드를 작성해보았다. 결과값은 정답과 근사하게 출력이 되지만 정답이 되는 코드는 아니다.

다만 이 코드를 첨부하는 이유는 나의 문제해결 접근방식과 또 다른 문제해결 접근방식을 비교하기 위한 목적에 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let word = 'teachermode';
let resultArr = Array.from(word.length).fill(0);
const splitWord = word.split('e');
console.log(splitWord);
const result = splitWord.map((word) => {
  const wordLength = word.length;
  for (let i = 0; i < Math.floor(wordLength / 2); i++) {
    if (wordLength % 2 !== 0) {
      resultArr[Math.ceil(wordLength / 2)] = i + 1;
    }
    resultArr[i] = i + 1;
    resultArr[wordLength - i - 1] = i + 1;
  }
  return resultArr.join('');
});
console.log(result);

우선 위의 코드에서 생각한 방식으로 코드를 구현해서 정답을 구할 수도 있다고 생각한다. 하지만 재귀호출 방식을 사용했기 때문에 시간 복잡도를 고려했을때 효율적이지 않은 코드가 된다.

자바스크립트에서 입력받기

Python으로는 간단하게 input()을 사용해서 키보드의 입력을 받아서 처리할 수 있었다. 하지만 이번에 VSCode에서 JavaScript로 알고리즘 문제를 풀면서 키보드로 받은 입력 값을 처리하려고 했는데 입력 이벤트를 계속 받고는 있지만 입력 이벤트가 끝나지 않았다.
왜 이런지 이해가 되지 않아서 방법을 찾아보던 도중에 해결방법을 찾았다.
바로 입력이 끝났다면 ctrl + D를 눌러서 입력 종료를 알려주는 것이다.

예상하지 못한 JavaScript 입/출력 부분의 문제로 계획하지 않은 입출력 관련된 내용으로 포스팅을 하게 되었다.

JavaScript에서 입출력은 fs(file system) 모듈을 사용한다. fs모듈의 readFileSync() 함수를 사용해서 파일이나 표준 입출력을 입력받게 되는데, 아래 예시 코드에서 0을 입력해주는 이유는 표준입력(stdin: standard input)이 파일 설명자로 0이기 때문이다.

nodejs에서 File system에 관한 공식문서 내용은 아래 링크를 참조하도록 하자.
→ https://nodejs.org/dist/latest-v14.x/docs/api/fs.html#fs_file_system

따라서 별도의 파일을 읽지 않고 표준 입력을 받는 경우에는 내부에 0이라는 인수를 넘겨준다. 0과 함께 encoding을 명시해줘야 하는데 별도로 명시하지 않고 표준입력의 설명자 0만을 넘겨준 경우에는 toString()함수를 사용해서 별도로 String 타입으로 변환을 해줘야 한다.
(변환을 안해주게 되면 <Buffer 31 30 0a>와 같은 raw buffer가 결과값으로 나온다)

1
2
3
4
5
6
7
8
9

const fs = require('fs');

const inputWithNoEncoding = fs.readFileSync(0).toString().split('\n');

const inputWithEncoding = fs.readFileSync(0, 'utf8').split('\n');

const cvtInputToNumber = fs.readFileSync(0, 'utf8').split('\n');
// ['10', '']와 같은 배열의 형태로 값이 반환되기 때문에 [0]번째 인덱스 값을 가져온다.
console.log(Number(cvtInputToNumber[0]));

참고로 readFileSync()의 내부에 작성해준 /dev/stdin은 백준 알고리즘 문제 풀이에서 입력 예제를 넣고 그 파일을 읽어 실행하게 만들기 위해서 작성해준 것이다.

JavaScript에서 입력받는 방법은 앞서 설명한 fs(File System) 모듈을 사용한 방법과 readline 모듈을 사용한 방법이 있다.
readline 모듈은 process.stdin이나 file stream과 같은 Readable stream에서 line by line으로 데이터를 읽어들이기 위한 interface를 제공한다.

1
2
3
4
5
6
7
8
9

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on('line', (input) => {
  console.log(`received: ${input}`);
});

백준 저지 10825번 국영수 문제 Pseudo code + Python code

문제풀이 접근 방식 : 튜플과 리스트 자료형을 사용한 정렬

Pseudo code

본 코드 (통과/PyPy3 - 231312KB / 3372ms) (시간초과/Python3)

시간초과가 발생하는 경우 PyPy3를 사용해서 코드를 테스트해보도록 하자.
이 시점에서 간단하게 PyPy3에 대해서 살펴보자.

1
2
3
4
5
6
7
8
9
10
11

n = int(input())
student_list = []

for _ in range(n):
    (name, korean, english, math) = input().split(' ')
    student_list.append((name, eval(korean), eval(english), eval(math)))

sorted_list = sorted(student_list, key=lambda x: (-x[1], x[2], -x[3], x[0]))

for student in sorted_list:
    print(student[0])

백준 저지 17609번 회문/유사회문 문제 Pseudo code + Python code

문제풀이 접근 방식 : 재귀호출

Pseudo code #1 RecursionError

본 코드 #1

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
26
27

shift_flag = False


def palindrome(input_str):
    global shift_flag
    if len(input_str) <= 1:
        if shift_flag:
            return 1
        return 0

    if input_str[0] != input_str[-1]:
        if input_str[0] == input_str[-2]:
            shift_flag = True
            input_str = input_str[0:-1]
        elif input_str[1] == input_str[-1]:
            shift_flag = True
            input_str = input_str[1:]
        else:
            return 2

    return palindrome(input_str[1:-1])


n = int(input())
for _ in range(n):
    input_str = input()
    print(palindrome(input_str))

백준 저지 2747번 피보나치 수 문제 Pseudo code + Python code

이 문제는 피보나치 수를 구하는 문제로, for-loop와 memoization, recursive 개념을 활용해서 풀이를 해보았다.
피보나치 수열의 값은 이미 계산된 값들의 누적 합으로 구성이 된다. 따라서 이미 계산된 부분은 별도의 변수에 값을 저장했다가 필요할때 참조하게 되면 빠르게 원하는 값을 도출해낼 수 있다.(fibonacci-memoization)

손코딩으로 작성한 코드 중 for-loop로 풀이한 부분의 초기리스트로 [1,1]이 아닌 [0,1]로 초기화를 시켜줘야 한다.(수정)

백준 저지 1302번 베스트 샐러 문제 Pseudo code + Python code

손 코딩을 한 코드에서 sorted로 정렬을 한 뒤에 list로 변환을 하였는데, dictionary type의 데이터를 items()로 하게 되면, 리스트 내에 튜플(key, value쌍)로 변환이 되기 때문에 그럴 필요가 없었다. 정렬된 튜플 데이터 리스트에서 첫번째 요소의 첫번째(book title-(key))를 추출하게 되면 가장 높은 판매 수를 기록한 책의 제목을 추출할 수 있다.

1
2
3
4
5
6
7
8

n = int(input())
sold_book = dict()
for _ in range(n):
    book_title = input()
    sold_book[book_title] = sold_book.get(book_title, 0) + 1
sorted_sold_book = sorted(sold_book.items(), key=lambda x: x[1], reverse=True)
print(sorted_sold_book[0][0])