이번 글에서는 확률론의 기본 개념들을 살펴보도록 하겠습니다. 이 글은 Ian Goodfellow 등이 집필한 Deep Learning Book과 김우철 등이 집필한 일반통계학, 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

Why Probability?

알고리즘은 결정적(deterministic)이고 확실한(certain) 요소들로 구성되지만, 머신러닝은 본질적으로 확률적(stochastic, nondeterministic)이고 불확실한(uncertain) 대상을 다룹니다. 머신러닝 분야에서 발생하는 불확실성에는 다음과 같이 세 종류가 있습니다.

• 모델링하려는 시스템 자체에 내재한 불확실성(inherent stochasticity). 예컨대 양자역학에서는 원자의 움직임을 확률적으로 해석, 설명한다. 마찬가지로 머신러닝에서 카드 게임 모델을 만들 때, 카드가 무작위 순서로 섞여 있다고 가정하고 그 random dynamics를 따지게 된다.
• 불완전한 관측(incomplete observability). 모델링하려는 시스템이 결정적이라 하더라도 모든 데이터를 관측할 수는 없다. 예컨대 몬티홀 문제에서 게임 참가자는 세 개 문(door) 가운데 하나를 고른다. 한 문 뒤에는 자동차가 있고 나머지 두 문 뒤에는 염소가 있다. 참가자의 선택이 주어졌을 때 결과(outcome)는 결정적이다(참가자 선택과 관계없이 자동차나 염소의 위치가 바뀌지는 않기 때문). 그러나 참가자 입장에서 보면, 결과는 불확실하다.
• 불완전한 모델링(incomple modeling). 관측한 정보의 일부를 버려야(discard)하는 모델을 쓸 때, 손실된 정보는 모델 예측의 불확실성을 낳는다. 예컨대 모든 물체의 위치를 정확히 관측할 수 있는 로봇을 만든다고 가정하자. 로봇이 물체들의 미래 위치를 예측할 때 공간을 구분(discretize)하게 된다면, 이러한 구분 자체가 로봇의 위치 예측을 불확실하게 만든다. 각각의 물체는 구분된 셀(discrete cell)과 관계없이 어디에나 존재할 수 있기 때문이다.

확률론

확률론(probability theory)은 사건의 빈도를 분석합니다. 포커 게임을 예로 들어보겠습니다. 이런 종류의 사건은 반복가능하다(repeatable)는 특징이 있습니다. 어떤 확률이 $p$라는 말은, 실험(카드 뽑기)을 무한히 반복하면 관심있는 사건이 나타나는 비율이 $p$라는 이야기입니다. 이 $p$는 사건이 일어날 비율과 직접적인 관련이 있다는 점에서 frequentist probability라 불립니다.

아예 다른 종류도 있습니다. 어떤 의사가 환자를 진찰하고 감기에 걸린 환자가 40%라는 결론을 내렸다고 칩시다. 이 경우는 포커게임과 달리 환자들을 무한히 관측할 수 없습니다. 감기와 증상이 유사해보이지만 환자가 걸린 병이 감기가 아닐 수도 있습니다. 이러한 경우 믿음의 크기(degree of belief)를 표현하기 위한 방안으로 확률을 씁니다. 다시 말해 환자가 정말 확실 하게 감기에 걸렸다고 판단되는 경우를 1, 그렇지 않다고 생각되는 경우를 0으로 둔다는 것이지요. 이는 확실성의 질적 수준(qualitative levels of certainty)과 관련이 있고 베이지안 확률이라 불립니다.

요컨대 확률을 빈도론으로 접근하는 쪽에서는 불확실성을 빈도로 정량화합니다. 반면 베이지안 관점에서는 확률 개념을 빈도가 아닌 믿음의 정도로 고려합니다. 한편 몇 가지 조건을 만족하면 frequentist probability와 베이지안 확률이 동일해 진다고 합니다. 예컨대 특정 조합의 카드를 갖고 있는 사람이 포커 게임에서 이길 확률을 계산하는 과정은 특정 증상이 나타나는 사람이 어떤 질병에 걸렸을 확률을 계산하는 것과 똑같습니다.

확률변수

확률변수(random variable)란 다양한 값(value)을 랜덤(random)하게 가질 수 있는 변수(variable)입니다. 확률변수는 표본공간(sample space)에서 상태공간(state space)으로 보내는 함수(function)이며, 확률적인 과정에 따라 확률변수의 구체적인 값이 결정됩니다. 표본공간이란 어떤 시행(실험)에서 나타날 수 있는 모든 결과들의 모임을, 상태공간이란 해당 확률변수가 취할 수 있는 모든 실수들의 집합을 가리킵니다.

예컨대 동전을 1회 던지는 실험에서 표본공간은 {앞면, 뒷면}이 됩니다. 확률변수 $X$를 동전을 두 번 반복해서 던졌을 때 앞면이 나온 횟수로 정의할 경우 상태공간은 {0, 1, 2}가 됩니다.

확률분포

확률분포(probability distribution)는 개별 확률변수나 확률변수의 집합에 대응하는 확률들의 집합을 가리킵니다. 확률분포는 상태(state)가 얼마나 많이 나타나는가를 나타냅니다.

이산확률변수와 확률질량함수

이산확률변수(discrete random variable)란 상태공간이 유한집합이거나 셈할 수 있는 무한집합인 확률변수를 가리킵니다. 확률질량함수(probability mass function)란 확률변수의 한 상태를 그 상태가 나타날 확률로 대응시켜 주는 함수입니다. 만일 확률변수 $X$가 $x$라는 값일 가능성이 확실하다면 그 확률은 1이 될 겁니다. 해당 확률질량함수를 $P$라 할 때 다음과 같이 씁니다.

[P\left( X=x \right) =1]

여러 확률변수에 대한 확률분포를 결합확률분포(joint probability distribution)이라 합니다. $P(X=x, Y=y)$는 확률변수 $X$, $Y$가 각각 $x$, $y$일 확률을 의미합니다. $P(x,y)$라 적기도 합니다. 확률변수 $X$에 대한 확률질량함수 $P$는 다음과 같은 조건을 만족해야 합니다.

• $P$의 정의역은 $X$의 모든 가능한 상태들로 이뤄진 집합이어야 한다.
• $∀x∈X$, $0≤P(x)≤1$. 발생이 불가능한 사건은 그 확률이 0이고 이보다 작은 확률을 가진 상태(state)는 존재하지 않는다. 마찬가지로 발생이 보장돼 있는 사건은 그 확률이 1이고, 이보다 큰 확률을 가진 상태는 존재하지 않는다.
• $∑_{x∈X}P(x)=1$. 이 성질을 두고 ‘정규화되었다(normalize)’고 표현한다. 이 속성을 만족하지 않을 경우, 많은 사건 가운데 하나가 발생할 확률이 1보다 클 수 있다.

균등분포(uniform distribution)를 예로 들어보겠습니다. 균등분포란 각 상태에 해당하는 확률이 동일한 확률분포를 가리킵니다. $k$개의 서로 다른 상태를 가질 수 있고 균등분포를 따르는 이산확률변수 $X$의 확률질량함수는 다음과 같습니다.

[P\left( X={ x }_{ i } \right) =\frac { 1 }{ k }]

베르누이분포

입시에서 합격과 불합격, 스포츠 경기에서 승리와 패배, 사업에서 성공과 실패, 수술 후 환자의 치유 여부 등 우리가 일상 생활에서 자주 접하는 일들은 두 가지의 가능한 결과만을 가질 때가 많습니다. 어떤 실험이 이와 같이 두 가지 가능한 결과만을 가질 경우 이를 베르누이시행(bernoulli trial)이라고 합니다.

일반적으로 베르누이시행에서 시행의 결과는 성공(s) 또는 실패(f)로 나타냅니다. 따라서 베르누이시행의 표본공간은 {성공, 실패}, 상태공간은 {0, 1}로 원소가 각각 두 개인 집합입니다. 성공을 1, 실패를 0으로 대응시키는 함수를 베르누이확률변수(bernoulli random variable)라 하고 이 확률변수의 확률분포를 베르누이분포라고 합니다. 베르누이분포는 다음 표와 같이 표현할 수 있습니다.

좀 더 간단하게는 다음과 같이 표현할 수 있습니다.

[P\left( X=x \right) ={ p }^{ x }{ \left( 1-p \right) }^{ 1-x }]

베르누이분포의 기대값과 분산은 다음과 같습니다.

[E\left( X \right) =p\ Var\left( X \right) =p(1-p)]

다항분포

다항분포(multinomial distribution)란 $k$개의 서로 다른 상태를 가질 수 있는 하나의 이산확률변수에 대한 확률분포를 가리킵니다. 어떤 시행에서 $k$가지의 값이 나타날 수 있고 그 값이 나타날 확률을 각각 $p_1$, $p_2$, …, $p_k$라 할 때 $n$번의 시행에서 $i$번째의 값이 $x_i$회 나타날 확률은 다음과 같습니다.

[P\left( { x }{ 1 },,…,{ x }{ k },{ p }{ 1 },…,{ p }{ k },n \right) =\frac { n! }{ { x }{ 1 }!{ x }{ 2 }!…{ x }{ k }! } { p }{ 1 }^{ { x }{ 1 } }{ p }{ 2 }^{ { x }{ 2 } }…{ p }{ k }^{ { x }_{ k } }]

시행을 $n$번 했으므로 $x_1+…+x_k=n$이 되어야 합니다. 그렇지 않은 경우의 확률값은 0으로 정의됩니다.

경우에 따라 다항분포는 값이 나타나는 횟수가 아니라 독립시행에서 나타난 값 자체를 가리키기도 합니다. 엄밀하게는 이러한 분포를 categorical distribution이라 합니다. 예컨대 $k$개 범주를 분류하는 뉴럴네트워크를 만들 때 마지막 층의 출력결과물은 $k$차원의 확률벡터가 될 텐데, 이 벡터의 각 요소값들은 해당 인스턴스가 각각의 범주일 확률을 나타낸다고 볼 수 있겠습니다.

어떤 시행에서 $k$개의 서로 다른 범주가 있고 그 범주가 나타날 확률을 각각 $p_1$, $p_2$, …, $p_k$라 할 때 1회 시행에서 $i$번째 범주 $c_i$가 나타날 확률은 다음과 같습니다.

[P\left( { c }{ i };{ p }{ 1 },…,{ p }{ k } \right) ={ p }{ i }]

머신러닝에서 다항분포는 대상이 가질 수 있는 범주(상태)에 대한 확률분포로 쓰입니다. 하지만 각 상태는 숫자로서의 의미는 없습니다. 1번 상태(범주 1)를 숫자 1로 보지 않는다는 겁니다. 이런 이유로 머신러닝에서는 다항분포를 따르는 확률변수의 기대값이나 분산을 대개 계산하지 않습니다.

정규분포

정규분포는 가우스(Gauss, 1777-1855)에 의해 제시된 분포로서 일명 가우스분포(Gauss Distribution)라고 불리며 물리학 실험 등에서 오차에 대한 확률분포를 연구하는 과정에서 발견되었다고 합니다. 가우스 이후 이 분포는 여러 학문 분야에서 이용되었으며, 초기의 통계학자들은 모든 자료의 히스토그램이 정규분포의 형태와 유사하지 않으면 비정상적인 자료라고까지 생각하였다고 합니다. 이러한 이유로 이 분포에 ‘정규(normal)’라는 이름이 붙게 된 것입니다.

정규분포는 특성값이 연속적인 무한모집단 분포의 일종으로서 평균이 $μ$이고 표준편차가 $σ$인 경우 정규분포의 확률밀도함수(Probability Density Function)는 다음과 같습니다.

[N(x;\mu ,{\sigma}^2 )=\frac { 1 }{ \sqrt { 2\pi } \sigma } exp\left( -\frac { { (x-\mu ) }^{ 2 } }{ 2{ \sigma }^{ 2 } } \right)]

평균이 0이고 분산이 1인 표준정규분포의 밀도곡선은 다음과 같습니다. 평균에 대해 좌우 대칭이고 변곡점과 대칭점 사이의 거리가 표준편차(=1)가 됩니다.

데이터 분포에 대한 사전지식이 전혀 없을 때 정규분포를 가정하는 것은 다음 두 가지 이유로 꽤 합리적인 선택입니다. 첫째 중심극한정리(central limit theorem) 덕분입니다. 중심극한정리란 동일한 확률분포를 따르는 $n$개의 독립 확률변수의 평균의 분포는 $n$(대개 30 이상)이 충분히 클 때 정규분포에 가까워진다는 정리입니다. 다시 말해 데이터의 분포가 어떤 형태이든 상관없이 30건 이상의 데이터만 있으면 이들 표본의 평균은 근사적으로 정규분포를 따른다는 사실입니다.

둘째 동일한 분산을 가진 모든 확률분포 가운데 정규분포는 최대 불확실성(uncertainty)을 내포하는 좋은 성질을 가지고 있다고 합니다. 정보이론(information theory)에서 엔트로피(entropy)는 어떤 확률변수의 불확실성을 가리킵니다. 엔트로피를 최대로 만드는 확률함수를 유도하면 정규분포 식이 도출된다고 합니다. 따라서 정규분포를 가정할 경우 모델을 만들 때 사전 지식(prior knowledge)을 최대한 배제한다는 의미 또한 지니게 된다는 것입니다. 정규분포가 최대 불확실성을 내포한다는 것과 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

중심극한정리를 이항분포(Binomial distribution)과 관련지어 이야기해보겠습니다. 성공확률이 $p$인 베르누이시행을 $n$번 반복시행할 때 성공횟수 $X$의 분포를 이항분포라고 합니다. 이때 이항분포의 평균과 분산은 각각 $np$, $np(1-p)$가 되는데요. 중심극한정리는 $n$이 적당히 크다면 $X$는 원래 정규분포를 따르지 않지만 표본의 분포가 평균이 $np$이고 분산이 $np(1-p)$인 정규분포와 유사해진다는 점을 알려줍니다.

아래 그림은 성공확률이 0.5인 베르누이시행을 100번 반복시행했을 때 성공횟수의 분포를 히스토그램으로 그린 것입니다. 실선은 평균이 50, 분산이 25인 정규분포를 그린 것입니다. 두 모양이 비슷한 것을 알 수 있습니다.

지수분포

딥러닝 모델을 만들 때 $x=0$인 지점에서 첨점(sharp point)를 갖는 확률분포가 필요할 수 있습니다. 이를 위해 지수분포를 씁니다. $1_{x≥0}$은 벡터 $x$의 요소 가운데 음수값에 대응하는 확률을 모두 0으로 만들어주는 indicatior function입니다. 지수함수의 식과 그래프는 다음과 같습니다.

[p\left( x;\lambda \right) =\lambda { 1 }_{ x\ge 0 }exp\left( -\lambda x \right)]

라플라스분포는 $μ$인 지점에서 첨점을 갖는 확률분포입니다. $γ$는 분포의 모양을 정하는 파라메터입니다. 식과 그래프는 다음과 같습니다.

시그모이드함수

시그모이드함수의 식은 다음과 같습니다.

[\sigma \left( x \right) =\frac { 1 }{ 1+exp(-x) }]

시그모이드함수는 함수값의 범위가 $[0,1]$이기 때문에 베르누이분포의 파라메터(성공확률) $p$를 만드는 데 주로 사용됩니다. 하지만 $x$가 매우 크거나 작을 경우 그래디언트가 0에 가까워지기 때문에 딥러닝 역전파가 잘 안되어 학습속도가 느려지거나 불가능해진다는 단점이 있습니다. 이와 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

이번 글에서는 순서가 있는 숫자들의 최대 부분합을 구하는 문제인 Maximum Subsequence Sum Problem 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 네 가지 접근을 소개할 예정인데요, 계산복잡성이 차례로 줄어듭니다. 그럼 시작하겠습니다.

접근1

다음과 같은 리스트가 있다고 가정해 보겠습니다.

4, -3, 5, -2, -1, 2, 6, -2

이 문제를 가장 단순하게 푸는 방법은 모든 경우의 수를 하나하나 모두 따져보는 것입니다. $i$는 고려 대상 부분 리스트의 왼쪽 끝 인덱스, $j$는 오른쪽 끝 인덱스, Thissum은 고려 대상 부분 리스트의 합, Maxsum은 이 문제의 최종 결론입니다. 다음과 같습니다.

위 표를 말로 풀어 설명하면 우선 $i$, $j$, Thissum, Maxsum을 모두 0으로 초기화합니다. $i$는 고정시킨 채 $j$를 0부터 리스트 요소 전체 숫자($n$)만큼 훑어가면서 부분 리스트를 만들고 이 리스트의 합을 Thissum으로 정의합니다. 그리고 이를 Maxsum과 비교해 더 큰 값을 Maxsum에 저장합니다. 이를 $i$와 $j$가 모두 $n=7$이 될 때까지 반복합니다. 이 방식의 의사코드는 다음과 같습니다.

Maxsum = 0
for (i=0; i < n; i++)
  {
    for (j=i; j < n; j++)
      {
        Thissum = sum(A[i:j])
      	Maxsum = max(Thissum, Maxsum)
      }
  }

이 방식의 계산복잡성은 $O(n^3)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때 최대 $n$개의 요소를 계산해야 하기 때문입니다.

접근2

접근1보다 계산복잡성을 낮추는 방법은 Thissum을 구할 때 중복을 좀 피하는 것입니다. 예제 리스트와 그 방식을 나타낸 표는 다음과 같습니다.

4, -3, 5, -2, -1, 2, 6, -2

표에서 접근1과의 차이가 느껴지실 지 모르겠습니다. 접근1에서는 Thissum을 구할 때 sum(A[i:j])을 취하여 매번 새로 구하다시피했습니다. 하지만 접근2에서는 직전 계산 결과를 재활용합니다. 예컨대 $i$가 0, $j$가 3일 경우 접근1에서는 4-3+5-2를 계산했다면, 접근2에서는 직전 계산결과인 6에 $j$번째 요소인 -2를 더해 Thissum을 구합니다. 의사코드는 다음과 같습니다.

Maxsum = 0
for (i=0; i < n; i++)
  {
    for (j=i; j < n; j++)
      {
        Thissum = sum(A[i:j])
      	Maxsum = max(Thissum, Maxsum)
      }
  }

이 방식의 계산복잡성은 $O(n^2)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때는 $O(1)$의 계산만 하면 되기 때문입니다.

접근3

접근3은 분할정복(divide-and-conquer)을 활용한 방식입니다. 분할정복이란 원 문제를 작은 부분문제로 나눠 푼 뒤 그 결과를 합쳐서 문제를 해결하는 알고리즘의 한 종류입니다. 접근3은 분석 대상 리스트를 절반씩 두 부분으로 나눕니다. 다시 예제 리스트를 보겠습니다.

4, -3, 5, -2, -1, 2, 6, -2

위 리스트를 두 부분으로 나누면 [4, -3, 5, -2], [-1, 2, 6, -2]가 됩니다. 왼쪽 리스트의 최대 부분합은 6(4-3+5), 오른쪽 리스트의 최대 부분합은 8(2+6)이 됩니다.

그런데 고려해야 하는 경우의 수가 이것만 있는 것은 아닙니다. 예컨대 [5, -2, -1]처럼 자른 곳(-2와 -1 사이)를 포함하는 부분 리스트도 얼마든지 존재할 수 있기 때문입니다.

중간에 존재하는 케이스의 경우 1)왼쪽 리스트의 마지막 요소(left ending)를 끝으로 하는 부분 리스트의 최대 부분합 2)오른쪽 리스트의 첫 요소(right starting)를 시작으로 하는 부분 리스트의 최대 부분합을 각각 구해 이를 더하면 구할 수 있을 것입니다.

1)에 해당하는 수는 4(-2+5-3+4), 2)는 7(-1+2+6)이므로 중간 케이스의 최대 부분합은 11이 됩니다. 결과적으로는 8, 6, 11 가운데 최대값을 취한 것이 접근3의 결과물이 되겠습니다. 접근3의 의사코드는 다음과 같습니다. left와 right는 각각 고려 대상 리스트의 왼쪽 끝, 오른쪽 끝의 인덱스입니다.

Maxsubsum(A[], left, right)
  {
  	// 종료 조건
    if (left == right)
      {
        maxsum = max(A[left], A[right])
        return maxsum
      }
  	// divide&conquer
  	Center = ⌞(left+right)/2⌟
    // [1] 왼쪽
    maxleftsum = Maxsubsum(A[], left, center)
    // [2] 오른쪽
    maxrightsum = Maxsubsum(A[], center+1, right)
    // [3] 중간
    maxleftbordersum = 0
    leftbordersum = 0
    // 1) left ending을 끝으로 하는 부분 리스트의 최대 부분합
    for (i=center; i>=left; i--)
      {
        leftbordersum += A[i]
        maxleftbordersum = max(maxleftbordersum, leftbordersum)
      }
    // 2) right starting을 시작으로 하는 부분 리스트의 최대 부분합
    for (i=center+1; i<=right; i++)
      {
        rightbordersum += A[i]
        maxrightbordersum = max(maxrightbordersum, rightbordersum)
      }
  	// [1], [2], [3] 가운데 최댓값을 취함
  	return (max(maxleftsum, maxrightsum, maxleftbordersum+maxrightbordersum))
  }

그럼 이 코드가 어떻게 작동하는지 예제 리스트를 기준으로 설명해보겠습니다. 다음 그림과 같습니다.

우선 예제 리스트를 $A$, left는 0, right는 7로 정의해 Maxsubsum 함수에 넣어 실행합니다. 종료조건(0≠7)을 만족시키지 못했으므로 $A$를 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 두 개 리스트 가운데 왼쪽 [4, -3, 5, -2] 또한 종료조건(0≠3)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 나눠진 왼쪽 리스트인 [4, -3] 또한 종료조건(0≠1)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다.

[4]가 되어서야 비로소 종료조건(0=0)을 만족하므로 4를 반환합니다. 마찬가지로 [-3]은 -3이 반환될 겁니다.

이번엔 [4, -3]을 볼 차례입니다. 왼쪽 [4]의 최대 부분합은 4, 오른쪽 [-3]은 -3, 중간 최대 부분합은 1입니다. 이 가운데 최댓값 4가 [4,-3]의 결과로 반환됩니다. 동일한 과정을 거쳐 [5, -2]는 5가 반환됩니다.

이번엔 [4, -3, 5, -2]를 볼 차례입니다. 왼쪽 [4, -3]의 최대 부분합은 4, 오른쪽 [5, -2]는 5, 중간 최대 부분합은 6입니다. 이 가운데 최댓값 6이 [4, -3, 5, -2]의 결과로 반환됩니다. 동일한 과정을 거쳐 [-1, 2, 6, -2]는 8이 반환됩니다.

마지막으로 전체 리스트를 고려할 차례입니다. 왼쪽 [4, -3, 5, -2]의 최댓값은 6, 오른쪽 [-1, 2, 6, 2]는 8이며 중간의 최댓값은 11이므로 전체 최댓값을 11이 됩니다.

접근3의 계산복잡성을 따져보겠습니다. 리스트의 요소 수가 $n$이라 할 때 이를 절반씩 나눠 재귀함수를 다시 호출하고, 중간 결과를 계산할 때 $n$개 요소 전체에 대해 따져보게 되므로 다음과 같은 식이 성립합니다. ($c$는 컴퓨터 파워 등에 영향을 받는 상수값)

[\begin{align} T\left( n \right) &=2T\left( \frac { n }{ 2 } \right) +cn\ &=2\times \left[ 2T\left( \frac { n }{ { 2 }^{ 2 } } \right) +c\frac { n }{ 2 } \right] +cn\ &={ 2 }^{ 2 }T\left( \frac { n }{ { 2 }^{ 2 } } \right) +2cn\ &={ 2 }^{ 3 }T\left( \frac { n }{ { 2 }^{ 3 } } \right) +3cn\ &=…\ &={ 2 }^{ i }T\left( \frac { n }{ { 2 }^{ i } } \right) +icn \end{align}]

여기에서 $n/2^i$가 1이 될 때까지 반복해야 하므로 로그의 정의에 따라 $i$는 $\log_2n$이 됩니다. 식은 다음과 같이 다시 쓸 수 있습니다.

[\begin{align} T\left( n \right) &={ 2 }^{ \log _{ 2 }{ n } }T\left( 1 \right) +\log _{ 2 }{ n } \times cn\ &=nT\left( 1 \right) +\log _{ 2 }{ n } \times cn\ &=O(n)+O(n\log _{ 2 }{ n } )\ &=O(n\log _{ 2 }{ n } ) \end{align}]

접근4

접근4는 부분 합이 음수가 될 경우 그 값은 논리적으로 최대값이 될 수 없다는 점에 착안해 계산량을 확 줄인 방법입니다. 복잡하고 현란한 기법을 쓰는 것보다 문제를 잘 이해하고 정의하는 것이 해결의 첫걸음이라는 교훈을 줍니다. 의사코드는 다음과 같습니다.

summax = 0
sum = 0
for i from 0 to n-1
{
  sum = sum + a[i]
  if sum < 0 then sum = 0
  if summax < sum then summax = sum
}

접근4의 계산복잡도는 $i$에 대해 반복 횟수가 $n$이고, 1회당 연산은 $O(1)$이므로 전체적으로는 $O(n)$이 됩니다.

이번 글에서는 한국어의 인용 표현에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의와 ‘한국어문법총론1(구본관 외 지음, 집문당 펴냄)’을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

인용절이란

남의 말이나 글, 말하는 사람의 생각, 판단 등을 나타내는 주술관계가 있는 절을 인용절이라고 합니다. 인용절에는 직접인용절과 간접인용절 둘로 나뉩니다.

직접인용절

본래의 언어형식을 바꾸지 않고 그대로 표현하려는 인용절을 직접인용절이라고 합니다. 대개 ‘-(이)라고’, ‘-하고’로 표시됩니다. 다음 예문과 같습니다.

어떤 사람이 “동사무소가 어디입니까?”라고 물었다.

나는 속으로 ‘이건 너무 어려워’라고 되뇌었다.

진이가 “얘들아, 어서 돌아와!”하고 소리쳤다.

간접인용절

본래의 언어 형식을 화자의 관점에 따라 내용 중심으로 바꾸어 표현하는 인용절을 가리킵니다. 다음과 같습니다.

나는 진이의 말이 옳다가 생각했다.

나는 진이에게 학교에 갈 거냐고 물었다.

의사가 환자에게 담배를 끊으라고 충고했다.

진이가 공원에 놀러 가자고 했다.

예시에서도 알 수 있듯 간접인용절은 화자의 현재 관점에서 기술되는 것이기 때문에 본래 발화로부터 인칭 대명사나 시간 표현, 지시 표현이 달라질 수 있습니다.

또한, 간접인용절로 내포될 경우 상대경어법은 별로 중요하지 않은 요소가 됩니다. 아래처럼 단지 문장의 종류에 따라서만 어미 선택이 달라집니다.

‘생각의 인용’과 ‘간접 인용’

영문법의 영향인지 화자가 직접 말하는 것은 직접 인용, 말로 내뱉지 않고 생각만 하는 것을 간접 인용, 이렇게 구분하는 경향이 있습니다. 물론 한국어에서도 머릿속에 있는 생각을 인용할 때에는 다음과 같이 간접인용을 하는 것이 더 자연스럽습니다.

우리는 선생님께서 건강을 곧 회복하실 것이라고 생각했다.

하지만 한국어에서는 밖으로 나온 말이나 글을 직접 인용하는 경우도 있고 간접 인용을 하는 경우도 있습니다. 또한 구어에서는 생각이라고 하더라도 직접 인용을 하는 경우도 적지 않습니다. 다음과 같습니다.

우리는 ‘선생님께서 건강을 곧 회복하시겠구나.’라고 생각했어요.

이번 글에서는 한국어의 이중주어문에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의와 ‘한국어문법총론1(구본관 외 지음, 집문당 펴냄)’을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

현상 관찰

한국어에는 한 문장에 주격 명사구가 두 번 나타나서 주어가 두 번 실현되는 것처럼 보이는 문장이 흔하다고 합니다. 예를 들어보겠습니다.

(1) 토끼가 앞발이 짧다.

(2) 이 집안이 딸이 귀하다.

(3) 진이가 의사가 되었다.

(4) 진이가 의사가 아니다.

(5) 학생이 세 명이 왔다.

위 예시 문장을 세 가지 유형으로 나누어 살펴보도록 하겠습니다.

1유형

다음 예시는 두번째 명사구만 서술어와 관련되고, 첫째 명사구는 둘째 명사구와 관계를 지니는 경우입니다.

(1) 토끼가 앞발이 짧다.

(2) 이 집안이 딸이 귀하다.

(1)에서 ‘짧다’라는 서술어는 ‘앞발이’라는 명사구와만 관계를 가집니다. (‘토끼가 짧다’는 의미상 성립하지 않습니다.) 그런데 토끼는 앞발보다 넓은 범위를 포괄하는 개념으로 ‘대(大)-소(小)’의 의미관계를 보입니다.

(2)에서 ‘귀하다’라는 서술어는 ‘딸이’라는 명사구와만 관계를 가집니다. ‘집안’은 ‘딸’이 사는 장소를 가리키며, 첫째 명사구가 의미상 장소, 방향 등의 관계를 나타냅니다.

1유형과 관련해 국어학계에 다양한 견해가 존재합니다.

우선 둘 모두 주어로 보는 입장입니다. 이 견해에 따르면 (1), (2) 예시는 주어가 2개이고 서술어가 하나인 단문에 해당합니다. 그러나 주어 사이의 관계를 명쾌하게 설명하지 못한다는 단점이 있습니다.

주제-평언 구조로 보는 입장도 있습니다. 이 견해에 따르면 앞의 명사구를 주제, 뒤의 명사구를 그 주제에 대한 설명을 나타내는 문장의 주어로 봅니다. 따라서 위 예시를 [주제 + [주어 + 서술어]] 구조로 분석할 수 있습니다. 그러나 이 견해는 문장 분석시 정보구조와 통사구조 개념이 혼재돼 있다는 단점이 있습니다. 정보구조와 주제와 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

마지막으로 서술절을 가진 안은 문장으로 보는 입장입니다. 학교문법이 이 견해를 채택하고 있습니다. 이 견해에 따르면 (1)의 ‘앞발이 짧다’는 주어와 서술어를 가지는 절이면서, 동시에 선행하는 주어 명사구 ‘토끼가’를 서술해주는 서술절로 쓰였다고 분석할 수 있습니다. 즉 [토끼가 [앞발이 짧다]]의 구조를 가진 것으로 보는 것입니다. 마찬가지로 (2)에서 전체 문장의 주어는 ‘이 집안이’이고, 그것의 서술어는 ‘딸이 귀하다’라는 절 형식입니다. ‘딸이 귀하다’에서의 주어는 ‘딸이’이고, 서술어는 ‘귀하다’입니다.

2유형

2유형은 서술어 자체가 두 개의 논항(서술어가 요구하는 필수성분)을 요구하여 두 명사구가 실현되며, 그 두 명사구가 서로 다른 의미역(명사구 논항이 서술어와 관련하여 지니는 의미 기능)을 갖는 경우를 가리킵니다. 논항과 관련해서는 이곳을, 의미역과 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

(3) 진이가 의사가 되었다.

(4) 진이가 의사가 아니다.

(3)에서 ‘되다’라는 서술어는 행위주역(Agent)과 결과상태역(Resultant State)을 요구합니다. 각각 ‘진이’, ‘의사’가 여기에 해당합니다. 다시 말해 ‘되다’라는 서술어는 ‘진이가’와 관계를 가지며, ‘의사가’와도 관련을 맺고 있습니다.

(4)에서 ‘아니다’라는 서술어 또한 서로 다른 의미역의 두 개 논항을 요구합니다. ‘아니다’라는 서술어는 ‘진이가’, ‘의사가’ 모두 관련을 맺고 있습니다.

3유형

3유형은 2유형처럼 첫번째, 두번째 명사구 모두 서술어와 관련을 맺고 있지만, 첫째 명사구와 둘째 명사구의 의미역이 동일해보이는 경우입니다.

(5) 학생이 세 명이 왔다.

(5)에서 ‘학생이’와 ‘세 명이’가 둘 다 행위주역으로서 동사 ‘오-‘와 관련되는 것으로 보입니다.

이번 글에서는 이진탐색(binary search) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

개요

이진탐색 알고리즘이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 알고리즘 특성상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 탐색 대상 데이터 수는 직전의 절반이 되므로 속도가 빠르다는 장점이 있습니다.

이진탐색 알고리즘을 직관적으로 나타낸 그림은 다음과 같습니다(그림 출처 : 영문 위키). 아래와 같이 17개 요소로 이뤄진 리스트에서 7의 위치를 찾는 이진탐색 알고리즘은 화살표 방향처럼 수행이 됩니다.

수행방식

위 그림 예시 기준으로 이진탐색 알고리즘 수행방식을 살펴보겠습니다. 우선 리스트의 중앙을 찾습니다. 요소가 17개이므로 중앙값은 여덟번째(리스트 요소가 $n$개라면 $n/2$를 내림한 값)에 있는 요소(14)가 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 작으므로 중앙값보다 큰 값(18, 19, 21, 24, 37, 40, 45, 71)들은 탐색 대상에서 제외합니다.

이번엔 [1, 3, 4, 6, 7, 8, 10, 13, 14]를 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 9개이므로 중앙값은 새로운 리스트의 네번째 요소(원래 리스트의 네번째 요소)이며 그 값은 6이 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 크므로 중앙값보다 작은 값(1, 3, 4)들은 탐색 대상에서 제외합니다.

이번엔 [6, 7, 8, 10, 13, 14]를 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 6개이므로 중앙값은 새로운 리스트의 세번째 요소(원래 리스트의 여섯번째 요소)이며 그 값은 8이 됩니다. 이 중앙값과 찾고자 하는 값(8)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 작으므로 중앙값보다 큰 값(10, 13, 14)들은 탐색 대상에서 제외합니다.

이번엔 [6, 7, 8]을 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 3개이므로 중앙값은 새로운 리스트의 두번째 요소(원래 리스트의 다섯번째 요소)이며 그 값은 7이 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 같으므로 이 중앙값의 위치(원래 리스트의 다섯번째)를 최종 산출물로 반환합니다.

파이썬 구현

이진탐색 알고리즘의 의사코드(pseudo code)는 다음과 같습니다. 아래 코드에서 item은 찾고자 하는 값, sorted_collection는 주어진 정렬된 리스트, left는 이 리스트의 왼쪽 끝 인덱스, right는 오른쪽 끝 인덱스를 의미합니다.

def binary_search(sorted_collection, item):

    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        midpoint = (left + right) // 2
        current_item = sorted_collection[midpoint]
        if current_item == item:
            return midpoint
        else:
            if item < current_item:
                # 주어진 리스트의 오른쪽 절반은 탐색 대상서 제외
                right = midpoint - 1
            else:
                # 주어진 리스트의 왼쪽 절반은 탐색 대상서 제외
                left = midpoint + 1
    return None

계산복잡도

이진탐색의 계산복잡도 $T(n)$을 따져봅시다. 의사코드를 보면 재귀적으로 자신을 호출하는 부분을 제외하면 상수배 복잡도를 가집니다. left와 right가 같은지, A[left]가 num과 같은지, A[center]가 num과 같은지 등을 따져보고 그 조건에 맞는 몇 가지 기본 연산을 수행하면 되기 때문입니다. 아울러 이진탐색이 반복될 때마다 고려 대상이 되는 리스트의 요소 수는 절반씩 줄어듭니다. 이를 식으로 나타내면 다음과 같습니다.

[\begin{align} T\left( n \right) &=T\left( \frac { n }{ 2 } \right) +c\ &=T\left( \frac { n }{ { 2 }^{ 2 } } \right) +c+c\ &=T\left( \frac { n }{ { 2 }^{ 3 } } \right) +c+c+c\ &=…\ &=T\left( \frac { n }{ { 2 }^{ i } } \right) +c\times i\ &=…\ &=T\left( 1 \right) +T(1)+…+T\left( 1 \right)+c\times \log _{ 2 }{ n }\&=O\left( \log _{ 2 }{ n } \right) \end{align}]

위 계산식에서 $\log_2n$이 도출되는 이유는 이렇습니다. 최악의 경우를 고려하면 $n/2^i$가 1이 될 때까지 이진탐색을 수행해야 합니다. $n/2^i=1$이므로 로그의 정의에 따라 $i=\log_2n$이 됩니다. big O 표기법에 관련해서는 이곳을 참고하시면 좋을 것 같습니다.