DCP란?

Daily Coding Problem의 가서 subscribe를 하면 매일 한 개의 코딩 문제를 이메일로 보내준다.

실제 회사에서 개발자들이 받았던 면접 문제들을 기반으로 만든 문제라고 하는데 단순히 면접을 떠나서 이런 문제들은 사고력과 논리력에 도움이 될거라고 생각해서 한 번 풀어보려고 한다.

문제들은 C/C++와 현재 공부중인 Ruby로 작성할 예정이다.
다만 같은 코드를 다른 언어로 글에 올리는 것은 의미가 없다 생각해서 Ruby 코드만 올리려고 한다.
C 또는 C++로 작성한 코드의 링크는 코드 설명을 할 때 따로 추가하도록 하겠다.

참고로 DCP에서 프리미엄 멤버의 경우 정답 코드를 다음 날 보내주는데 필자는 그렇지 않은 관계로 정답 코드를 확인 할 수가 없다. 그러니 오류 또는 더 좋은 방법이 있다면 피드백과 코드의 공유를 해주면 감사할 따름이다.

참고로 문제들은 전부 영어라서 미숙하게나마 한국어로 번역을 했다. 문제 설명에서 애매한 부분이나 어색한 부분이 있어 이해가 안간다면, 블로그에 원문으로 올린 링크를 첨부하니 가서 원문을 확인하면 된다.

그럼 첫 번째 문제를 풀어보자.

DCP #1

이 문제는 실제 구글 면접에서 나온 질문이다.

정수 배열과 정수 k가 주어졌을 때, 배열 속 두 정수의 합이 k가 되는지 확인하는 프로그램을 작성하라. 예를들어, 배열의 값으로 [10, 15, 3, 7] 그리고 k17이 주어질 경우, 10 + 7k 이므로 참을 반환한다.

보너스: 원 패스(one pass)로 문제를 풀 수 있는가?

원문 읽기


코드 & 설명

C++ 코드 보기

Bruteforce

일차원적으로 접근한다면 배열의 모든 원소를 하나하나 확인하는 브루트포스 방법이 있다.

def bruteforce(arr, k)
    n = arr.size

    for i in (0 ... n - 1)
        for j in (i + 1 ... n)
            if arr[i] + arr[j] == k
                puts "found: #{arr[i]} + #{arr[j]} = #{k}"
                return
            end
        end
    end
    puts "none exists"
end

배열의 첫 번째 원소부터 시작해 나머지 원소들과 하나 씩 더해가면서 k와 일치하는지 확인한다.
여기서는 puts를 사용했지만 일치하면 참을 아니면 거짓을 반환한다.

시간복잡도는 O(n^2).
연산 하면서 사용되는 추가적인 메모리는 없기 때문에 공간 복잡도는 O(1)이다.

One-Pass

브루트포스는 아무래도 데이터의 크기가 커지면 커질수록 느려질 수 밖에 없다.
이 문제를 one-pass로 다시 한 번 구현해보자. 해시맵를 사용한다.

def one_pass(arr, k)
    m = Hash.new(0)

    arr.each do |n|
        if m.has_key? (k - n)
            puts "found: #{k - n} + #{n} = #{k}"
            return
        else
            m[n] = (k - n)
        end
    end
    puts "none exists"
end

새로운 원소(a)에 접근하는 순간순간 n의 key가k - n인지 확인하고 맞으면 참을, 그렇지 않으면 nk - n를 각각 key, value로 해시에 추가한다.

시간복잡도를 계산해보자.

Hash[] 메소드는 아래와 같이 구현되어 있다.

# 출처: https://apidock.com/ruby/v2_5_5/Hash/%5B%5D

VALUE
rb_hash_aref(VALUE hash, VALUE key)
{
    st_data_t val;

    if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
        return rb_hash_default_value(hash, key);
    }
    return (VALUE)val;
}

정확히 st_lookup이 어떻게 구현되어 있는지 모르겠지만 lookup table하면 보통 O(1)인걸로 알고있으니 O(1)으로 봐도 무방하지 않을까 싶다.

has_key의 구현은 아래와 같다.

# 출처: https://apidock.com/ruby/v2_5_5/Hash/has_key%3F

VALUE
rb_hash_has_key(VALUE hash, VALUE key)
{
    if (!RHASH(hash)->ntbl)
        return Qfalse;
    if (st_lookup(RHASH(hash)->ntbl, key, 0)) {
        return Qtrue;
    }
    return Qfalse;
}

마찬가지로 O(1)이다.

고로 one-pass로 작성한 위 코드의 시간복잡도는 O(n)이고 공간복잡도는 최소 O(1), 최대 O(n)이다.

etc

  • 코드 하이라이팅에 ruby가 없다 :(
  • 문제에서 같은 숫자를 써도 되는지에 대한 제약이 없어서 일단 써도 되는걸로 간주하고 풀었다.
  • C++코드의 경우는 같은 숫자를 쓰지 않는걸로 가정하고 풀었다 (뭐야?).
  • C++코드의 시간 복잡도는 map의 find를 써서 O(nlogn)이다.

Blog: https://muicode.github.io
DCP Github: https://github.com/muicode/DCP