이번 글에서는 유니그램 모델(unigram model)을 중심으로 통계적 언어모델(Statistical Language Model, 언어모델)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

정의

언어모델이란 단어 시퀀스에 대한 확률분포(probability distribution)를 가리킵니다. 언어모델은 $m$개 단어가 주어졌을 때 $m$개 단어 시퀀스가 나타날 확률, 즉 $P(w_1, w_2, …, w_m)$을 할당(assign)합니다. 예컨대 다음과 같습니다.

(1) $P(Today\ is\ Wednesday)=0.001$

(2) $P(Today\ Wednesday\ is)=0.0000000001$

언어모델은 context-dependent 성격을 지닙니다. 일상적인 대화 말뭉치로 언어모델을 구축했다면 일상 대화가, 수학 컨퍼런스의 말뭉치로 언어모델을 구축했다면 수식 표현이 나타날 확률이 클 겁니다. 다시 말해 언어모델은 학습데이터에 민감합니다.

언어모델의 이점

자연언어에는 기본적으로 불확실성(uncertainties)이 존재합니다. 그런데 언어모델은 이러한 불확실성을 단어 시퀀스의 출현 확률로 정량화(quantify)할 수 있는 장점을 가집니다. 예컨대 언어모델의 힘을 빌리면 앞선 예제에서 (1)이 나타날 확률은 (2)보다 $10^7$배 크다고 ‘숫자’로 말할 수 있게 됩니다.

언어모델이 주어지면, 우리는 확률분포를 가지고 단어의 시퀀스를 뽑을 수(sample) 있습니다. 다시 말해 해당 언어모델로 텍스트를 생성(generation)해낼 수 있다는 뜻입니다. 이런 취지에서 언어모델은 종종 생성모델(generative model)이라고도 불리는데요.

예컨대 ‘John’이라는 단어와 ‘feels’라는 단어가 주어졌다고 칩시다. 그러면 그 다음 단어는 ‘happy’일 가능성이 높을까요? 아니면 ‘habit’일 확률이 클까요? 사실 ‘happy’와 ‘habit’은 말소리가 비슷하지만, 언어모델의 힘을 빌리면 그 확률이 높은 ‘happy’를 뽑게 됩니다. 응답(answer) 생성에 도움이 된다는 이야기입니다.

유니그램 언어모델

가장 단순한 언어모델은 유니그램 언어모델(unigram language model)입니다. 각 단어가 서로 독립(independent)이라고 가정합니다. $n$개 단어가 동시에 나타날 확률은 다음과 같습니다.

[P\left( { w }{ 1 },{ w }{ 2 },…,{ w }{ n } \right) =\prod _{ i=1 }^{ n }{ P\left( { w }{ i } \right) }]

유니그램 모델에서는 단어의 시퀀스를 고려한다기보다는 단어 셋(set)을 상정한다는 것이 더 정확한 표현입니다. 단어 시퀀스의 등장확률이 각 단어 발생확률의 곱으로 정의돼 있기 때문입니다. 다시 말해 각 단어의 등장 순서가 바뀌어도 개별 단어 확률의 곱은 변하지 않는다는 이야기입니다.

유니그램 모델은 다음과 같은 테이블로 구성됩니다. 학습말뭉치에 등장한 각 단어 빈도를 세어서 전체 단어수로 나누어준 것입니다. 물론 확률의 총합은 1이 됩니다.

텍스트마이닝 논문 말뭉치로 학습한, 위와 같은 유니그램 모델 $θ_1$이 주어진 상황에서 ‘text’와 ‘mining’, ‘clustering’이라는 세 개 단어로 구성된 첫번째 문서 $D$의 출현확률을 구해보겠습니다.

[\begin{align} P\left( D|{ \theta }_{ 1 } \right) &=P\left( text\quad mining\quad clustering|{ \theta }_{ 1 } \right) \ &=P\left( text|{ \theta }_{ 1 } \right) \times P\left( mining|{ \theta }_{ 1 } \right) \times P\left( clustring|{ \theta }_{ 1 } \right) \ &=0.2\times 0.1\times 0.02=0.0004 \end{align}]

유니그램 모델에서는 말뭉치 등장 빈도가 높은 단어가 많이 포함된 문서일 수록 해당 문서의 출현확률이 높아집니다. 바꿔 말해 등장빈도 높은 단어를 해당 문서의 주제(topic)으로 볼 여지가 있다는 얘기입니다. 위 예시에선 ‘text’를 $D$의 주제로 볼 수도 있습니다. 아울러 당연한 이야기겠지만, 만일 다른 단어로 구성된 문서가 존재한다면 이 유니그램 모델은 해당 문서에 다른 확률을 할당하게 될 겁니다.

이번에는 건강/식이요법 관련 논문 말뭉치로 학습한, 유니그램 모델 $θ_2$가 아래처럼 주어졌다고 가정해 보겠습니다. 그렇다면 $P(D$|$θ_1)>P(D$|$θ_2)$일 겁니다. 같은 단어로 구성된 문서라도 모델이 다르면 그 확률값이 크게 달라지게 됩니다(context-dependent).

최대우도추정

언어모델 $θ$를 학습한다는 것은 각각의 단어 $w$의 등장확률을 추정(estimate)한다는 의미입니다. 다시 말해 위와 같은 단어-확률 테이블을 만드는 과정이라고 볼 수 있습니다. 그런데 문제는 우리에게 주어진 데이터(말뭉치)가 모집단 전체를 포괄하는 게 아니라 일부라는 점이라는 사실입니다. 데이터 확보에 한계가 있기 때문입니다. 한정적인 데이터를 바탕으로 그럴듯한 언어모델 $θ$를 추정해내는 것이 관건이 되겠습니다.

통계학에서 모수(파라메터)를 추정하는 데에는 여러가지 기법이 있습니다. 이 가운데 가장 많이 쓰이는 것이 바로 최대우도추정량(the maximum likelihood estimator)입니다. 우도($θ$가 주어졌을 때 관측치가 나타날 확률)를 최대로 만드는(=데이터를 가장 잘 설명하는) 모수 $θ$를 선택하는 것입니다. 바꿔 말해 관측치들이 $θ$라는 분포에서 샘플링됐다고 가정하고, 이를 바탕으로 $θ$를 추정하는 방법인데요. 결과(데이터)를 보고 원인($θ$)을 추정하는 방법이라고 이해하면 좋을 것 같습니다.

우리가 가지고 있는 말뭉치가 $D$, 우리가 추정하려는 언어모델이 $θ$라고 할 때 최대우도추정량은 다음과 같습니다.

유니그램 모델의 경우 적당한 수식 정리 과정을 거치면 단어 $w$의 우도 $P(w$|$θ)$가 다음과 같을 때 전체 단어 우도의 곱이 최대가 됩니다. $c(w, D)$는 말뭉치 $D$에 있는 단어 $w$의 빈도, |$D$|는 말뭉치 $D$의 전체 단어 개수(중복 포함)입니다.

언어모델의 한계와 극복 노력

언어모델의 단점은 학습말뭉치에 존재하지 않는 단어의 경우 그 확률이 0이 되어 문제가 됩니다. 이미 언급했던 것처럼 학습말뭉치에 의존적이기 때문에 범용적인 모델을 구축하기가 어렵습니다. 아울러 조사, 어미 등 기능적 단어(functional words, 영어의 경우 관사 등)가 우리가 관심이 있는 주제 단어(topic words)보다 훨씬 빈도가 높아 원하는 결과를 내기가 쉽지 않을 수 있습니다.

이같은 문제를 극복하기 위해 평탄화(smoothing) 등 다양한 기법이 제안됐는데요, 그 중 한 가지 방식은 다음과 같습니다.

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

부사절 내포

부사절이란 부사 역할을 하는 절이 내포된 경우를 가리킵니다. 예문을 보겠습니다.

주어+서술어 형태의 ‘절’처럼 보이진 않지만 다음과 같은 예문도 부사절 내포 구성이라고 볼 수 있습니다.

꽃$i$이 [$e_i$ 아름답게] 피었다.

위 예문은 (1) 꽃이 아름답다 (2) 꽃이 피었다 두 문장이 합쳐진 형태라고 볼 수 있습니다. 여기에서 ‘꽃이’가 공통 명사로 생략되었습니다. 내포절 ‘아름답게’가 문장 전체에서 부사 역할을 하므로 부사절이라고 볼 수 있습니다.

이 글에서는 한국어의 부사절 내포를 부사형 전성어미의 종류와 관련지어 설명하겠습니다.

개괄

부사형 전성어미와 그 문법적 기능을 정리한 표는 다음과 같습니다.

-게

부사형 전성어미 ‘-게’는 다음과 같이 쓰입니다.

-도록

부사형 전성어미 ‘-도록’은 다음과 같이 쓰입니다.

-게 vs -도록

‘-게’와 ‘-도록’은 결과적 한계, 목적 등 많은 면에서 그 의미가 유사합니다. 하지만 성질, 상태, 방식에 대해선 ‘-게’를, 시간적 한계에는 ‘-도록’을 씁니다.

그는 [{고독하게, *고독하도록}] 살았다.

나는 [밤이 {*새게, 새도록}] 시험공부를 했다.

-이, -을수록, -듯(이)

부사형 전성어미 ‘-이’는 결합하는 서술어가 ‘다르다, 같다, 없다’로 한정됩니다.

[미국과 달리] 한국 여성들은 결혼 후에도 본래의 성을 쓴다.

우리는 [돈 없이] 1주일을 더 견뎌야 한다.

아이가 [꽃과 같이] 예쁘다.

‘-을수록’은 점차 심해짐의 의미를 나타냅니다.

[날이 갈수록] 취업이 어려워지고 있습니다.

‘-듯(이)’는 유사한점을 비유적으로 표현할 때 씁니다. 앞 절의 내용이 뒤 절의 내용과 거의 같음을 나타냅니다.

나그네가 [달이 구름에 가듯(이)] 걸어간다.

-으면서, -으며

이들 어미는 동시에 발생하는 사건을 나타냅니다.

진이가 노래를 들으면서 밥을 먹는다.

-자/자마자 vs -고(서)/어(서)

이들 어미는 연이어서 나타나는 사건을 뜻하는 계기적 사건을 가리킵니다. 아래 (가)는 선행절이 나타내는 사건과 후행절의 사건이 거의 즉시 발생하는 경우를, (나)는 시간차가 있는 경우를 의미합니다.

진이가 학교에 가자/가자마자 친구들이 환호성을 질렀다. (즉시)

종이배를 접어서 시냇물에 띄웠다. (시간차)

-자마자 vs -자

‘-자마자’와 ‘-자’는 모두 앞 절의 동작이 이루어진 후 바로 뒤이어 다음 절의 사건이나 동작이 일어남을 나타냅니다. ‘-자마자’는 뒤 절에 명령문이나 청유문이 올 수 있고, 앞 절 주어와 뒤 절 주어가 같아도 되고 달라도 됩니다. 반면 ‘-자’는 뒤 절에 명령문이나 청유문이 올 수 없고, 앞 절 주어와 뒤 절 주어가 같을 때 제약이 있습니다.

-어서 vs -고서

‘-어서’와 ‘-고서’는 동사 뒤에 결합하여 행동의 시간적 순서를 나타냅니다. ‘-어서’의 경우 앞 절은 뒤 절의 조건이 되며 서로 밀접한 관계를 가집니다. 앞 절의 동작이 없이는 뒤 절이 이뤄질 수 없습니다. 반면 ‘-고서’는 끝점이 있는 타동사와 결합하여 앞 절 동작의 결과가 지속되면서 뒤 절의 내용이 진행될 때 사용할 수 있습니다. 예문을 보겠습니다.

(A) 숙제를 해서 오세요.

(B) 숙제를 하고서 오세요.

(A)는 숙제를 한 다음 그 숙제를 가지고 오라는 느낌이 약간 강합니다. (B)는 숙제를 마치고, 오라는 느낌이 있습니다. 다른 예문을 보겠습니다.

-다가

‘-다가’는 선행절이 중단되고 다른 상황이 이어짐, 즉 사건의 전환을 나타냅니다. 다음 예문과 같습니다.

진이가 운동을 하다가 쓰러졌다.

앞 절의 행동이 계속되면서 추가로 뒤 절의 행동이 일어나는 경우에도 사용할 수 있습니다.

잠을 자다가 무서운 꿈을 꿨어요.

-어(서)

필연적인 인과관계가 있을 때 ‘-어(서)’를 쓰면 자연스럽습니다. 따라서 일반적인 자연의 현상이나 사물의 변화로 발생한 결과를 설명할 때 ‘-어서’를 주로 사용합니다. 예문을 보겠습니다.

비행기가 추락해서 사람들이 많이 죽었다.

비가 많이 내려서 홍수가 났다.

진이가 아들만 셋을 ?낳아서 이번에는 딸을 낳을거야.

마지막 문장은 조금 부자연스럽습니다. 아들 셋을 낳은 사실과 딸을 낳을 거라는 추측에 필연적인 인과관계가 있지 않기 때문인듯합니다. 다음 예문처럼 ‘-어(서)’ 앞에 오는 말은 새로운 정보(주제)인 경향이 있습니다.

Q: 어머니가 왜 걱정을 하시지?

A: 진이가 아파서 걱정을 하셔.

‘-어(서)’ 뒤 절에는 청유문과 명령문을 사용할 수 없습니다.

*시간이 없어서 서두르세요.

*시간이 없어서 서두릅시다.

-으니까

화자 나름의 주관적인 이유를 제시할 때나, 주관적인 추론의 전제를 제시할 때 ‘-으니까’가 주로 쓰입니다. 다음 예문과 같습니다.

집에서 책만 읽으니까 친구가 없지.

진이가 아들만 셋을 낳았으니까 이번에는 딸을 낳을거야.

대문 앞에 신문이 쌓여 있으니까 집 안에 사람이 없는 게 틀림없어.

위 예문에서 두번째, 세번째 문장에 ‘-어(서)’를 넣어서 비교해보면 그 뉘앙스 차이를 느낄 수 있습니다. 다시 말해 아들 낳은 사실, 대문 앞에 신문이 쌓여있는 사실은 각각 딸을 낳는 것과 집안에 사람이 없다는 사실과 직접적인 관련이 없습니다.

‘-으니까’ 뒤에 오는 말이 새로운 정보인 경우가 많습니다.

Q: 장마 기간인데 물가가 어때?

A: 장마 기간이 되니까 채소 값이 올랐어.

-어(서) vs -으니까

아래 예문에서 ‘피곤해서’와 ‘피곤하니까’의 뉘앙스 차이에 주목해 봅시다.

A: 나 오늘 일찍 퇴근해야겠어.

B: 왜?

A1: 피곤해서.

A2: 피곤하니까.

‘피곤하니까’는 ‘피곤해서’에 비해 약간 짜증스러움이 묻어난다는 게 느껴집니다. 다시 말해 ‘당신도 내가 피곤하다는 사실을 이미 알고 있으면서 왜 굳이 다시 물어보느냐’라는 어감이 나타난다는 것입니다. 이는 ‘-어(서)’와 ‘-으니까’ 앞에 오는 말이 각각 신정보, 구정보에 해당하기 때문이라고 설명을 할 수 있겠습니다. 다음 예문에서 (2)가 비문이 되는 이유도 이의 연장선상에 있습니다.

(1) 배가 아파서 어제 결석했습니다.

(2) 배가 *아프니까 어제 결석했습니다.

앞에 어떤 이유를 제시하고 그로 인해 뒤따르는 새로운 상황을 명령문이나 청유문의 형태로 제시할 때는 ‘-으니까’만이 쓰입니다.

아기가 {자니까, *자서} 조용히 해라.

-으면

앞 말이 조건, 가정일 때 ‘-으면’을 씁니다. 뒤 절 문장 유형에 제약이 없습니다.

내일 날씨가 화창하면 소풍을 {갑니다., 갑니까? 갑시다., 가십시오.}

-거든

앞 말이 조건, 가정이면서 전체 문장이 명령문, 청유문일 때 대개 ‘-거든’이 쓰입니다.

가는 길에 진이 만나거든 전화 좀 하라고 해.

손님이 오시거든 먹겠니?

*호랑이도 제 말을 하거든 온다.

-어야

앞의 내용이 조건, 가정이면서 뒤에 오는 내용의 필수 조건임을 나타냅니다. 명령문, 청유문에서는 쓰일 수 없습니다.

윗물이 맑아야 아랫물이 맑다.

*비가 와야 우산을 가지고 가라. (명령문)

*호랑이를 만나야 혼내주겠다. (필수 조건 아님)

-어도, -을지라도, -더라도, -어야, -은들, -을망정

‘-어도’, ‘-을지라도’, ‘-더라도’, ‘-어야’, ‘-은들’, ‘-을망정’은 내포절을 양보의 기능을 하도록 만드는 부사형 전성어미입니다. 양보란 종속절의 사태로 인하여 논리적으로 도출되는 사태가 주절에 이어지는 것이 아니라, 일반적으로 예상되는 것과는 반대되는 결과가 주절에 이어지는 걸 말합니다. 다음 예문과 같습니다.

(가) 아무리 바쁘더라도 차 한잔 마실 시간은 있다.

(나) 비가 와도 여행을 갈 거야.

(가)의 경우 종속절의 사태로 논리적으로 도출되는 사태는 ‘아주 바쁘면 차 한잔 마실 시간도 없다’가 됩니다. 하지만 이와 반대되는 내용이 주절에 언급이 되면서 ‘-더라도’가 쓰였습니다. 마찬가지로 (나)에선 ‘비가 오면 여행을 가지 않는다’가 예상됐는데 여행을 간다고 언급이 되면서 ‘-어도’가 쓰였습니다.

-으려고

앞의 내용이 목적이면서 앞 절과 뒤 절에 오는 동사에 제약이 없습니다.

진이는 머리를 자르려고 미용실을 예약했다.

하지만 뒤 절에 청유문과 명령문이 올 수 없습니다.

*고기를 잡으려고 바다로 가자.

-고자

앞의 내용이 목적이면서 주로 격식을 갖춘 말이나 공식적인 장소에서의 대화, 글에서 많이 사용되는 부사형 전성어미입니다.

이 논문에서는 한국어의 중국어의 부정법을 대조하고자 한다.

-으러

앞의 내용이 목적이면서 선행절의 서술어가 동작동사이고 후행절의 서술어가 이동동사일 때만 쓸 수 있습니다.

진이는 머리를 자르러 미용실에 갔다.

*예뻐지러 미용실에 갔다.

*지이는 나를 안 만나러 서울로 갔다.

*파마를 하러 미용실을 예약했다.

명령문과 청유문에서 쓰일 수 있습니다.

고기를 {잡으러/*잡으려고/*잡고자} 바다로 가자.

-는데, -으니

‘-는데’와 ‘-으니’는 앞 절이 뒤 절의 배경이나 상황일 때 씁니다.

집에 가는데 소나기가 내렸다.

서울역에 가 보니 사람이 정말 많았다.

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

복문이란

단문(單文)이란 주술관계가 한 번 있는 문장을, 복문이란 주술 관계가 둘 이상 포함된 문장을 가리킵니다. 아래 예에서 (가)는 단문, (나)~(라)는 복문입니다.

(가) 우리 집 셋째가 집에서 숙제를 한다.

(나) [인생은 짧고] [예술은 길다].

(다) [진이가 와서] [우리는 모임을 시작했다].

(라) [나는 [봄이 왔음]을 오늘에서야 깨달았다].

학교문법에서 보는 복문의 종류

학교문법에서는 복문을 다음과 같이 분류합니다.

이어진문장

• 대등적으로 이어진 문장 : [먼동이 트고] [별들이 사라진다]
• 종속적으로 이어진 문장 : [먼동이 트자] [별들이 사라진다]

안은 문장

• 명사절을 안은 문장 : [그가 돈이 많음]이 분명하다
• 관형사절을 안은 문장 : [그가 우리를 도와 준] 일을 잊지 맙시다
• 부사절을 안은 문장 : 그 사람이 [말도 없이] 떠나 버렸구나
• 서술절을 안은 문장 : 철수가 [키가 아주 크다]

그러나 위와 같이 (1) ‘대등적으로 이어진 문장(대등절)’과 ‘종속적으로 이어진 문장(종속절)’을 구별하고 (2) ‘종속적으로 이어진 문장’과 ‘부사절을 안은 문장(부사절)’을 별개의 것으로 보는 견해는 국어학계에서 소수라고 합니다. 실제 사례들을 따져보면 예외가 상당히 많이 발생하기 때문입니다. 세 가지 기준으로 살펴보겠습니다.

이동가능성

첫번째 기준은 절이 문장 내에서 이동가능한지 여부로 종속절, 부사절, 대등절을 나눠보는 것입니다. 예문을 살펴보겠습니다.

종속절 : 이동가능

[아버지가 돌아가시자] 진이는 고향을 떠났다.

진이는 [아버지가 돌아가시자] 고향을 떠났다.

부사절 : 이동가능

[구름에 달이 흘러가듯이] 나그네가 간다.

나그네가 [구름에 달이 흘러가듯이] 간다.

대등절 : 이동불가능

[인생은 짧고] 예술은 길다.

*예술은 [인생은 짧고] 길다.

학교문법에서는 종속절이 대등절과 비슷하다고 봅니다. 그러나 이동가능성 기준을 놓고 볼 때 종속절은 오히려 부사절과 유사합니다.

주어의 ‘은/는’ 결합 가능성

두번째 기준은 분석 대상 절의 주어에 조사 ‘-은/는’이 붙을 수 있는지 여부입니다. 예문을 보겠습니다.

종속절 : 결합불가능

[{사촌이, *사촌은} 땅을 사서] 배가 아프다.

부사절 : 결합불가능

[{엄마가, *엄마는} 지나가게] 아빠가 길을 비켜 주셨다.

대등절 : 결합가능

[{산이, 산은} 높고] 물은 깊다.

주어의 ‘은/는’ 결합 가능성 기준을 놓고 봐도 종속절은 부사절과 유사합니다.

재귀 대명사의 결속 가능성

세번째 기준은 분석 대상 절에 재귀 대명사가 쓰일 수 있는지 여부입니다. 예문을 보겠습니다.

종속절 : 결속가능

온달은 [자기 아내가 공주이므로] 부마가 된다.

부사절 : 결속가능

진이는 [자기 동생이 지나가게] 길을 비켜 주었다.

대등절 : 결속불가능

진이는 키가 크고 *[자기 동생은 키가 작다].

재귀대명사의 결속 가능성 기준을 놓고 봐도 종속절은 부사절과 유사합니다.

다시 보는 복문의 종류

지금까지 논의한 내용을 바탕으로 복문의 종류를 다시 분류해보면 다음과 같습니다. ‘종속적으로 이어진 문장(종속절)’ 모두를 ‘부사절을 안은 문장(부사절)’으로 보는 것입니다.

이어진 문장

• 대등적으로 이어진 문장

안은 문장

• 명사절을 안은 문장
• 관형사절을 안은 문장
• 부사절을 안은 문장 (종속적으로 이어진 문장 포함)
• 서술절을 안은 문장

어미의 종류

어미를 위치와 기능에 따라 대략적으로 분류한 표는 다음과 같습니다.

어말어미란 단어의 끝에서 쓰이는 어미입니다. 선어말어미란 어말어미 앞자리에서 쓰이는 어미입니다. 어말어미엔 종결어미(문말어미)와 비종결어미 둘로 나뉩니다. 종결어미는 한 문장을 끝맺는 기능을 합니다.

비종결어미엔 연결어미(접속어미)와 전성어미가 있습니다. 연결어미는 한 문장을 다음 문장으로 이어주는 역할을 합니다. 전성어미는 한 문장을 명사나 관형사, 부사와 같은 단어의 자격으로 전성(change)시키는 기능을 합니다. 여기에서 연결어미는 ‘이어진 문장’, 전성어미는 ‘안은 문장’과 더 깊은 관련을 맺고 있습니다.

이번 글에서는 내가 만든 알고리즘이 얼마나 효율적인지를 따져보기 위한 도구인 점근 표기법(asymptotic notation)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

개요

내가 만든 알고리즘을 수퍼컴퓨터에서 돌릴 때와 노트북에서 수행할 때는 분명 속도 면에서 차이가 날 겁니다. 수행환경을 통제하지 않고서는 공정한 비교라고 할 수 없겠지요. 이 때문에 알고리즘의 계산복잡성은 컴퓨터 성능에 관계없이 machine independent한 방식으로 따져보게 됩니다. 알고리즘 자체의 효율성은 데이터 개수($n$)가 주어졌을 때 덧셈, 뺄셈, 곱셈 등 해당 알고리즘 수행시 필요한 ‘기본 연산(basic operation)의 횟수’로 표현하는 것이 일반적입니다.

이렇게 따져본 내 알고리즘의 계산복잡성이 $20/πn^2+n+100$이라고 칩시다. $n$이 증가함에 따라 이 알고리즘의 계산복잡성이 대략 어떻게 늘어나는지, 머릿 속에서 그 모양과 방향을 예측하기가 그렇게 쉽지만은 않습니다. 여기에 어떤 개발자가 내놓은 알고리즘은 $100000n+100000$이라고 가정해봅시다. 그러면 내가 만든 알고리즘과 비교해 어떤 것이 더 나은 알고리즘일까요? 이 문제도 역시 단박에 알아내기가 어렵습니다. 이럴 때는 가늠해보려는 알고리즘의 계산복잡성 증가 양상을 단순화시켜 우리가 익히 알고 있는 로그, 지수, 다항함수 등과의 비교로 표현하는 점근 표기법이 유용하게 쓰일 수 있습니다.

점근 표기법에서는 원 함수를 단순화하여 최고차항의 차수만을 고려합니다. 최고차항을 제외한 모든 항과 최고차항의 계수는 무시합니다. 이 표기법을 따르면 내 알고리즘의 계산복잡도는 $n^2$, 다른 개발자의 알고리즘은 $n$이 됩니다. 따라서 데이터 수가 증가함에 따라 내 알고리즘의 계산복잡도는 지수적으로, 상대방의 알고리즘은 선형적으로 증가하며, 상대방의 알고리즘이 제 것보다 더 나은 알고리즘이라고 비교할 수 있게 됩니다. 만약 위 그림처럼 점근 표기법으로 표현된 계산복잡성이 $\log{n}$인 알고리즘이 등장한다면 state-of-the-art의 기법이 되겠지요.

점근 표기법에는 대표적으로 대문자 O 표기법, 대문자 오메가(Ω) 표기법, 대문자 세타(Θ) 표기법, 소문자 o 표기법, 소문자 오메가(ω) 표기법 다섯 종류가 있습니다. 다섯 표기법 모두 내가 만든 알고리즘 $f(n)$를 지수, 다항함수 등 우리가 익히 알고 있는 함수 $g(n)$와 어떤 관계가 있는지 표현해 줍니다. 차례로 살펴보겠습니다.

Big-O notation

대문자 O 표기법에서는 아래 그림을 만족하는 $f(n)$를 $O(g(n))$이라고 표시합니다. 이 때 $g(n)$를 $f(n)$의 점근 상한(an asymptotic upper bound)이라고 합니다. 러프하게 보면, 내가 만든 알고리즘 $f(n)$이 $O(g(n))$에 속한다면, $f(n)$의 계산복잡도는 최악의 경우라도 $g(n)$과 같거나 혹은 작다는 뜻입니다.

이를 수식으로 나타내면 다음과 같습니다.

예를 들어보겠습니다. $2n^2=O(n^3)$입니다. 2($n_0$) 이상의 모든 $n$에 대해 $0≤2n^2≤cn^3$을 만족하는 $c$가 존재하기 때문입니다($c=1$).

이를 그림으로 나타내면 다음과 같습니다. (빨간색 선=점근 상한=$n^3$) 이 알고리즘의 계산복잡도는 최악의 경우에도 빨간색 선보다는 작거나 같습니다.

다음은 $O(n^2)$에 속한 함수 $f(n)$입니다. 최고차항의 차수가 2보다 작거나 같은 함수들입니다.

$n^2$

$n^2+n$

$n^2+1000n$

$1000n^2+1000n$

$n$

$n/1000$

$n^{1.99999}$

$n^2/\log\log\log{n}$

Big-Ω notation

대문자 Ω 표기법에서는 아래 그림을 만족하는 $f(n)$를 $Ω(g(n))$이라고 표시합니다. 이 때 $g(n)$는 $f(n)$의 점근 하한(an asymptotic lower bound)이라고 합니다. 러프하게 보면, 내가 만든 알고리즘 $f(n)$의 계산복잡도가 $Ω(g(n))$에 속한다면, $f(n)$의 계산복잡도는 최선의 경우를 상정하더라도 $g(n)$과 같거나 혹은 크다는 뜻입니다.

이를 수식으로 나타내면 다음과 같습니다.

예를 들어보겠습니다. $\sqrt{n}=Ω(\ln{n})$입니다. 2($n_0$) 이상의 모든 $n$에 대해 $0≤\ln{n}≤c\sqrt{n}$인 $c$가 존재하기 때문입니다($c=1$).

이를 그림으로 나타내면 다음과 같습니다. (녹색 선=점근 하한=$\ln{n}$) 다시 말해 이 알고리즘의 계산복잡도는 최선의 경우에도 녹색 선보다는 크거나 같습니다.

다음은 $Ω(n^2)$에 속하는 함수 $f(n)$입니다. 최고차항의 차수가 2보다 크거나 같은 함수들입니다.

$n^2$

$n^2+n$

$n^2-n$

$1000n^2+1000n$

$1000n^2-1000n$

$n^3$

$n^{2.00001}$

$n^2\log\log\log{n}$

$2^{2^n}$

Big Θ-notation

대문자 Θ 표기법에서는 아래 그림을 만족하는 $f(n)$를 $Θ(g(n))$이라고 표시합니다. 이 때 $g(n)$은 $f(n)$의 점근적 상한과 하한의 교집합(an asymptotic tight bound)이라고 합니다. 러프하게 보면, 내가 만든 알고리즘 $f(n)$이 아무리 나쁘거나 좋더라도 그 계산복잡도는 $g(n)$의 범위 내에 있다는 뜻입니다. 다음과 같습니다.

이를 수식으로 나타내면 다음과 같습니다.

예를 들어보겠습니다. $n^2/2-2n=Θ(n^2)$입니다. 8($n_0$) 이상인 모든 $n$에 대하여 $0≤c_1n^2≤n^2/2-2n≤c_2n^2$을 만족하는 $c_1, c_2$가 존재하기 때문입니다($c_1=1/4, c_2=1/2$).

이를 그림으로 나타내면 다음과 같습니다. (노란색 선=점근 하한=$1/4n^2$, 검정색 선=점근 상한=$1/2n^2$) 다시 말해 이 알고리즘의 계산복잡도는 최선의 경우에도 보라색 선보다는 크거나 같고, 최악의 경우에도 검정색 선보다는 작거나 같습니다.

o-notation, ω-notation

소문자 o 표기법, 소문자 오메가(ω) 표기법은 각각 대문자 O 표기법, 대문자 오메가(Ω) 표기법과 비교해 등호가 빠지는 등 조건이 약간 더 엄격합니다. $o(g(n))$의 정의는 다음과 같습니다.

그 예시는 다음과 같습니다. 최고차항의 차수가 2보다 작은 함수(정확히 2인 것은 제외)입니다.

$n^{1.99999}=o(n^2)$

$n^2/\log{n}=o(n^2)$

$n^2≠o(n^2)$ (마치 $2 ≮ 2$ 인 것과 같음)

$n^2≠o(n^2)$

$ω(g(n))$의 정의는 다음과 같습니다.

그 예시는 다음과 같습니다. 최고차항의 차수가 2보다 큰 함수(정확히 2인 것은 제외)입니다.

$n^{2.00001}=ω(n^2)$

$n^2\log{n}=ω(n^2)$

$n^2≠ω(n^2)$

표기법 간의 관계

다섯가지 점근 표기법을 한눈에 정리하면 다음 표와 같습니다.

엄밀히 말해 $ω(g), Ω(g), Θ(g), O(g), o(g)$는 각각 함수의 집합을 의미합니다. 각 집합의 요소 수는 무한히 많을 것입니다. 다섯 집합 사이의 관계를 따져보면 다음과 같습니다.

알고리즘 계산복잡도를 따질 때 보통 가장 많이 쓰이는 것은 대문자 O 표기법이라고 합니다. 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.

점근 표기법의 속성

점근 표기법은 다음과 같은 속성을 지닌다고 합니다. 저 또한 정리 용도로 올려둡니다.

이번 글에서는 함수호출(function call)과 이와 관련된 여러 개념에 대해 살펴보도록 하겠습니다. 이 글은 C언어를 바탕으로 설명해주신 고려대 김황남 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

점프와 프로그램 카운터

폰 노이만 아키텍처(Von-Neumann Architecture)는 헝가리 출신 미국인 수학자 존 폰 노이만(1903-1957)이 제안한 컴퓨터 구조입니다. 그는 저장된 프로그램(stored-program)이라는 개념으로 아키텍처를 설계했는데요. 데이터와 명령어를 따로 구분하지 않고 같은 공간에 저장한다는 것이 핵심입니다. 이 구조의 장점은 컴퓨터에 다른 작업을 시키려고 할 때 굳이 하드웨어를 재배치할 필요 없이 소프트웨어만 바꾸면 되기 때문에 범용성이 크게 향상된다는 것입니다. 이 때문에 현재 거의 모든 컴퓨터 중앙처리장치(CPU)는 이 구조를 따르고 있다고 합니다. 그 개념도는 다음과 같습니다.

레지스터(register)란 CPU에서 데이터와 명령어를 저장해두는 아주 빠른 기억 장소(위 그림에서 memory unit)입니다. 대부분의 CPU는 보조 메모리에서 레지스터로 데이터든 명령어든 옮겨와 이를 처리한 후 필요시 그 내용을 다시 보조 메모리로 저장하는 로드-스토어(Load-Store) 설계를 사용하고 있다고 합니다. 레지스터는 다양한 종류가 있는데, 이 중 함수호출과 직접 관련된 것은 프로그램 카운터(program counter)입니다. 프로그램 카운터란 다음에 실행될 기계어로 된 명령어의 메모리 주소를 저장해두는 레지스터의 일종으로 ‘명령어 포인터’라고도 불립니다.

한편 기계어(machine language)란 CPU가 직접 실행하는 명령어의 집합입니다. 기계어에는 로드, 스토어 같은 데이터 이동(data transfer) 명령, AND/OR 등 산술/로직(Arithmetic/Logic) 명령, 그리고 콘트롤(control) 명령 등이 있습니다. 콘트롤 명령은 프로그램 실행과 관련이 있는데요, 콘트롤 명령 가운데 함수호출과 직접 관련된 것은 점프(jump)라고 합니다. 보통 CPU는 프로그램을 순차적으로 처리합니다. 그런데 특정 조건이 만족돼 점프가 수행되면 프로그램 카운터에 저장돼 있는 주소값이 바뀌게 됩니다. 함수호출과 관련해 이를 다시 살펴보겠습니다.

예컨대 함수 A를 실행하다가 B를 호출하고, B를 실행하다가 C, C 이후 D를 차례로 호출하는 프로그램을 작성했다고 칩시다. 또 C는 함수 D의 실행 결과를 반환받아 나머지 코드를 실행한 뒤 그 결과를 B에, B는 다시 A에, 이로써 A는 최종 아웃풋을 산출하는 구조라고 가정해보겠습니다. 이 경우 CPU는 함수 A를 실행하다가 중간쯤에서 점프를 합니다. 프로그램 카운터가 함수 B가 저장된 주소값으로 바뀌게 됩니다. 아울러 B가 실행되는 중간쯤 다시 점프, 프로그램 카운터의 주소값이 함수 C의 시작 위치로 바뀝니다. 이러한 방식으로 함수호출이 점프, 프로그램 카운터와 긴밀한 관련을 맺게 되는 것입니다.

매개변수와 전달인자

그러면 함수 간 소통은 어떠한 방식으로 이뤄지는 걸까요? 다시 말해 위 그림에서 함수 D의 실행결과는 C, C가 리턴한 값은 B, B의 결과는 A의 연산에 영향을 미치는 갈색 화살표 방향이 우리의 주된 관심입니다. 이 때 중요한 개념이 바로 매개변수(parameters)와 전달인자(arguments)입니다. 매개변수란 서브함수에 입력값으로 전달되는 데이터를 가리키기 위한 변수(variable)이며, 전달인자는 서브함수를 호출할 때 전달되는 실제 값(value)을 뜻합니다. 보통 매개변수는 함수를 정의할 때 선언합니다. 예를 들어보겠습니다.

int incr( int i )
{
  int j;
  j = i + 1;
  return j;
}

int main( void )
{
  int k, m = 4;
  k = incr(m);
  printf( "k = %d, m = %d\n", k, m);
  return 0;
}

incr 함수는 어떤 값을 넣으면 여기에 1을 더한 값을 반환하는 함수입니다. 위 코드에서 매개변수는 $i$, 전달인자는 4가 됩니다. main 함수는 incr을 호출할 때 4를 전달하며, incr 함수는 4를 $i$에 대입시켜 연산을 수행합니다. incr 함수의 최종 출력은 $j$인데, 여기엔 실제로 5라는 값이 들어 있게 되겠죠. 이 값이 다시 $main$ 함수의 $k$라는 변수에 저장되는 형식입니다.

C언어의 인자 전달(argument passing)에는 크게 값에 의한 호출(call-by-value)과 포인터에 의한 호출(call-by-pointer) 등이 있습니다. 위 예시는 바로 값에 의한 호출 방식으로 인자를 전달한 것인데요. 서브함수를 호출할 때 전달인자의 복사본을 전달하며, 함수의 전달인자는 별도의 변수로 관리됩니다. 인자의 복사본이 서브함수에 전달되기 때문에 인자가 서브함수 내에서 바뀌어도, 원래 함수의 변수는 변하지 않습니다.

위 예시를 기준으로 말씀드리면 $m$이 가리키는 값(4)의 복사본이 incr 함수에 전달되기 때문에 main 함수의 $m$의 값은 main 함수가 종료되더라도 4로 남아있게 됩니다.

포인터

포인터(pointer)란 변수의 메모리 주소 정보를 가리킵니다. 예를 볼까요?

int v = 1;

위 코드는 $v$에 해당하는 포인터에 1이라는 값을 할당(assign)하라는 뜻입니다. 그러면 포인터에 의한 호출과 관련해 아래 예시를 보겠습니다.

void incr( int* i )
{
  *i = *i + 1;
}

int main( void )
{
  int m = 4;
  incr(&m);
  printf( "m = %d\n", m);
  return 0;
}

main 함수에서 ‘incr(&m)’이란 변수 $m$의 포인터를 incr 함수에 인자로 전달한다는 뜻입니다. incr 함수에서 ‘int* i’란 매개변수 $i$의 포인터가 가리키는 값을 불러온다는 뜻입니다. 따라서 incr 함수는 $m$의 포인터에 저장돼 있는 4라는 값을 불러와 여기에 1을 더한 뒤 다시 $m$에 저장합니다. 결과적으로 main 함수에서 출력되는 $m$의 값은 5가 되는 것입니다.

재귀함수

재귀함수(recursion)란 자기 자신을 반복적으로 호출하는 함수입니다. 다음 세 가지 조건을 만족해야 합니다.

(1) 종료조건(base case)이 존재한다 (=안 그러면 무한 루프)

(2) 반복문이 정의되어 있다

(3) 서브루틴을 수행할 수록 base case에 가까워진다 (=안 그러면 무한 루프)

이를 만족하는 대표적인 사례가 factorial(1부터 지정한 수까지의 모든 자연수의 곱)입니다. 코드는 다음과 같습니다.

int factorial(int n) {
  if (n < 2) {
    return 1;
  } else {
    return factorial(n-1) * n;
  }
}

물론 위 함수를 반복문으로 작성할 수도 있습니다. 다음과 같습니다.

int factorial_iter(int n) {
  int result = 1;
  int i;
  for (i = 1; i <= n; ++i) {
    result *= i;
  }
  return result;
}

위 둘 가운데 재귀함수 방식의 계산복잡성이 아주 약간 높다고 합니다. 왜냐하면 실행 과정에서 인자를 전달해야하고, 수행 중에 점프를 해야 하는 등 함수호출 관련 추가적인 연산이 필요하기 때문입니다. 하지만 재귀함수로 코드를 작성하면 디버깅이 수월해지는 등의 장점이 있어서 선호되는 방식이라고 합니다.

그런데 재귀함수를 쓰면 되레 안 좋은 경우가 있습니다. 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)이 바로 그 예입니다(그림 출처). 딱 봐도 계산 중복이 많은데요(fib(3)는 세 번이나 계산해야 하네요). 이 경우에는 재귀함수보다는 저장해 두었다가 풀기(다이나믹 프로그래밍)를 쓰면 효율적이라고 합니다.