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

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

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

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

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

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

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

이번에 풀어 본 기본 알고리즘 문제는 완전탐색 알고리즘으로 이름에서 유추해 볼 수 있듯이 가능한 모든 경우의 수를 비교해서 풀이하는 방법의 알고리즘 기법이다.

이전에 이 Brute force 알고리즘에 대해서 포스팅한 적이 있다.

오늘 풀어 본 멘토링 문제도 이 완전탐색을 기반으로 풀어야 해결할 수 있는 문제였다.

문제의 조건은 다음과 같다.

총 4명의 학생이 N번의 테스트를 응시해서 각 테스트 별로 등수가 매겨진다. A와 B학생이 있다고 가정했을때, A학생이 B학생의 멘토가 되기 위해서는 시행된 모든 테스트에서 A학생은 B학생보다 등수가 우위에 있어야 한다.
이러한 조건으로 각 테스트별 해당 학생의 등수가 비교되는 학생보다 등수가 우위에 있는지 비교를 하고 우위에 있다면 count값을 증가시켜 count값이 응시하는 테스트 수와 같다면 멘토, 멘티의 관계가 성립되기 때문에 결과로 출력할 answer값을 증가시켜 값을 누적하도록 하면 해결할 수 있는 문제였다.

기본 알고리즘 문제 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);

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

백준 저지 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])

백준 저지 1236번 성 지키기 문제 Pseudo code + Python code

손 코딩에서 이중 for문 처리하는 부분에서 수정이 필요하다. 이중 for문에서 i,j를 이용해서 내부 반복처리를 해야하는데, 손 코딩할때 n과 m을 넣어 처리를 했다. 이 부분을 i와 j로 수정해서 넣어줘야 한다.

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

n, m = map(int, input().split())
security_in_castle_list = []
for _ in range(n):
    security_in_castle_list.append(input())
castle_row = [0]*n
castle_column = [0]*m
for i in range(n):
    for j in range(m):
        if security_in_castle_list[i][j] == 'X':
            castle_row[i] += 1
            castle_column[j] += 1
castle_zero_row = 0
for row in castle_row:
    if row == 0:
        castle_zero_row += 1
castle_zero_column = 0
for col in castle_column:
    if col == 0:
        castle_zero_column += 1
print(max(castle_zero_row, castle_zero_column))