Tag Archives: 알고리즘

프로그래밍/ P, NP, NP-Hard, NP-Complete


http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

튜링 기계


http://www.ibs.re.kr/newsletter/2014/12/sub_01.html

테이프 위를 움직이며, 테이프에 쓰여진 기호를 읽고 명령을 수행하는 기계.

튜링 기계에는 한 번에 하나의 상태만 가질 수 있는 –현대의 컴퓨터– 결정론적 튜링 기계와 한 번에 여러 상태를 동시에 가질 수 있는 –양자 컴퓨터– 비결정론적 튜링 기계가 있다.

비결정론적 튜링 기계는 분기 상황을 한 번에 진행할 수 있기 때문에, 결정론적 튜링 기계로 지수 시간이 걸리는 문제를 다항식 시간내에 해결할 수 있다.

튜링 기계 –명령을 수행하는 방식– 를 폰 노이만 구조 –CPU, 메모리, 프로그램으로 구분된– 로 만들어낸 것이 현대의 컴퓨터라고 할 수 있다.

결정 문제 (Decision Problem)

Yes or No로 대답할 수 있는 문제.

‘n개의 도시를 모두 방문하고 돌아오는 최단거리를 구하라’는 문제는 Yes, No로 대답할 수 없지만, ‘n개의 도시를 모두 방문하고 돌아오는 거리 K이하인 경로가 존재하는가?’ 는 Yes, No로 대답할 수 있으므로 결정문제다.

P와 NP는 모두 결정 문제에 속한다.

다항 시간

다항 시간이라는 것은 현실적인 시간 내에 해결 가능한 시간을 의미한다. 문제 해결 자체는 가능하지만 해결하는데 시간이 1010초 정도의 시간이 걸린다면 현실적으로 해결하기 어려운 시간이라는 의미다. –참고로 우주의 나이는 4.35×1017이다. 다항 시간을 넘어서는 시간을 지수 시간이라고 한다.

일반적으로 다항식하면 xn이 포함되지만, 알고리즘에서 다항 시간은 알고리즘 함수의 최고차 항의 계수가 3이하이거나 N x logN 으로 표시되는 정도까지 인정한다. 지수 범위가 5만 넘어가도 현실적인 시간 내에 풀기는 어려우므로 다항식 시간이라고 보기는 어렵다.

P (Polynomial time)

결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합.

NP (Non-deterministic Polynomial time)

비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합. 또는 Yes라는 근거가 제시되었을 때 결정론적 튜링 기계로 그것이 옳다는 것을 다항식 시간에 확인할 수 있는 문제의 집합.

위 2가지 설명은 완전히 동일한 의미이다. 비결정론적 튜링 기계로 다항 시간 내에 답을 구할 수 있다는 것은 결정론적 튜링 기계로는 답을 구하는데 지수 시간이 걸린다는 것이고, 결정론적 튜링 기계로 지수 시간이 걸린다는 것은 Yes라는 근거가 제시되었을 때 다항식 시간에 그것이 옳다는 것만 확인할 수 있다는 뜻이 된다. 모두 같은 말인데, NP 문제를 설명할 때 표현이 다르니 주의.

NP는 풀 수 없는 문제가 아니라 풀 수 있는데 –Yes라는 근거가 제시되므로– 튜링 기계로 다항식 시간 내에 풀 수 있는 알고리즘이 아직 알려지지 않은 문제이다. 운이 좋으면 다항식 시간 내에 답을 구할 수 있기도 하다.

NP Hard

어떤 NP문제를 다항식 시간 내에 어떤 문제로 변환(Reduction) 할 수 있는 경우 –당연히 풀기 더 쉬운 형태로– 그 문제를 NP-Hard 문제라고 부른다. TSP 문제는 해밀토니안 문제로 변환가능하기 때문에 NP-Hard 문제가 된다.

만일 그 변환한 문제를 다항식 시간 내에 해결할 수 있다면, 원래 문제는 ‘변환하는데 걸리는 다항식 시간 + 변환한 문제를 해결하는데 걸리는 다항식 시간’이 되어 결국 다항식 시간 내에 풀리는 문제가 된다.

NP-Hard는 P와 교집합이 없다고 여겨지는데, 만일 단 한 문제라도 P 문제이면서 NP-Hard인 문제가 발견되면, 모든 NP 문제는 P로 변환할 수 있게 되고 P = NP가 성립된다. –TSP 문제를 다항식 시간 내에 풀 수 있는 알고리즘이 발견되면 이것이 성립한다.

NP문제를 변환할 수 있는 경우 NP-Hard가 된다고 해서 NP-Hard가 NP의 부분집합처럼 생각되는데, NP-Hard는 결정문제 뿐만 아니라 비결정문제도 포함되기 때문에 NP의 부분집합이 아니다. 그래서 ‘모든 경우를 일일히 확인하지 않고서는 답을 구할 수 없는 문제’라는 보다 정의가 좀 더 직관적으로 느껴진다. 참고로 NP문제와 NP-Hard의 교집합은 NP-Complete이 된다.

NP Complete

NP이면서 동시에 NP Hard인 –교집합– 문제. 일반적으로 NP 문제 중 가장 어려운 문제들의 집합이라고 한다.

NP-Complete에 속하는 문제들은 NP 문제와 밀접한 논리적 연결 관계를 갖고 있는데, 만일 NP-Complete에 속하는 문제 중 어느 한 문제만이라도 다항식 시간 내에 해결이 된다면, 그 해법을 이용하여 NP에 속하는 다른 모든 문제를 다항식 시간에 풀 수 있다.

P-NP 문제

결정론적 튜링 기계로 답을 구할 수 있는 모든 문제는 비결정론적 튜링 기계로 다항식 시간 내에 구할 수 있는 반면 그 반대는 아니므로 P는 NP의 부분집합이다.

그런데 P가 NP의 부분집합이라는 것은 확실하지만 P가 NP보다 작다는 증명이 되지 않았기 때문에, P와 NP가 같은지 P가 NP보다 작은지는 알 수 없다. 이게 바로 P-NP 문제이다.

만일 P와 NP가 같다는 것이 증명되면 모든 NP 문제는 P 문제로 변환할 수 있는 알고리즘이 존재한다는 뜻이고 모든 NP 문제는 결정론적 튜링 기계로 다항식 시간 내에 답을 구할 수 있다는 뜻이 된다.

이것은 직관적으로 믿기 어렵기 때문에 많은 사람들이 P와 NP가 같지 않다고 믿는다.

프로그래밍/ 알고리즘의 복잡도

알고리즘의 복잡도

시간 복잡도

알고리즘의 수행 시간을 분석하는 것. 알고리즘을 구성하는 함수에 따른 수행 시간은 아래와 같다.


http://stackoverflow.com/questions/7830727/n-log-n-is-on

시간 복잡도의 표기는 여러개가 있지만, 기본적인 것 3개만 정리한다.

O (빅오)

알고리즘 시간의 하한선을 나타내는 표기법. 알고리즘 수행 시간이 아무리 빨라도 비교 함수에 비해 같거나 빠르다.

표기는 대문자 O 다음의 괄호안에 비교하는 함수를 넣는다. ex) O(g(n)), O(n), O(n2), O(logn), O(nlogn)…

Ω (오메가)

알고리즘 시간의 상한선을 나타내는 표기법. 알고리즘 수행 시간이 아무리 빨라도 비교 함수에 비해 같거나 느리다.

표기는 Ω(오메가) 다음의 괄호안에 비교하는 함수를 넣는다. ex) Ω(g(n)), Ω(n), Ω(n2), Ω(logn), Ω(nlogn)…

Θ (세타)

알고리즘 시간의 상한-하한 범위선을 나타내는 표기법. 빅오와 오메가의 교집합을 의미한다. Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

표기는 Θ(세타) 다음의 괄호안에 비교하는 함수를 넣는다. ex) Θ(g(n)), Θ(n), Θ(n2), Θ(logn), Ω(nlogn)…

공간 복잡도

알고리즘이 사용하는 메모리의 양을 분석하는 것.

알고리즘의 복잡도 분석

시간 복잡도 함수

시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한 것이다. 연산에는 산술 연산, 대입 연산, 비교 연산, 이동 연산 등이 포함되는데 복잡도 분석에서 이들 연산의 실행 횟수를 사용한다.

만일 동일한 조건에서 동일한 일을 하는데 알고리즘 A는 20번의 연산이 필요하고 알고리즘 B는 100번의 연산이 필요하다면 알고리즘 A가 더 효율적이라고 할 수 있다.

만일 n2을 구하는 문제에 대해 다음과 같은 알고리즘들이 있다면 각각의 실행 시간은 다음과 같다.

알고리즘 연산 횟수
알고리즘 A sum <- n*n 2
알고리즘 B for i <- 1 to n do
sum <- sum + n
2n
알고리즘 C for i <- 1 to n do
for j <- 1 to n do
sum <- sum + 1
2n2

엄밀하게 따지면 곱셈 연산이 덧셈 연산보다 수행 시간이 더 걸리지만 알고리즘 분석에서는 연산 횟수를 더 중요하게 보기 때문에 무시한다.

프로그래밍/ 재귀함수

함수가 함수 내부에서 자기 자신을 호출 하는 것. 자기호출이라고도 한다.

int Fibonacci (int N)
{
    if (N == 1 || N == 2)
        return 1;
    else
        return Fibonacci(N-1) + Fibonacci(N-2);
}

재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.

위 함수가 구현하는 피보나치 수열의 점화식은 아래와 같다.

  • a1 = 1, a2 = 1
  • an+2 = an+1 + an (n은 양의 정수)
    • 위 코드와 정확히 같게 표현하면 an = an-1 + an-2 (n은 3이상의 양의 정수)가 된다.

재귀는 긴 수열을 아주 간결하게 표현할 수 있다는데서 무척 아름답고, 재귀로 함수를 구성하면 마치 퍼즐을 푼 것 같은 즐거움도 느껴지만, 코드를 한 눈에 이해하기 어렵고, 현실 세계에 존재하는 컴퓨터의 메모리의 물리적 한계상 자칫하면 stackoverflow가 발생할 수 있으며, 중복 계산 때문에 성능이 떨어지는 –물론 이를 위한 별도의 해법이 존재한다– 등의 문제가 있으므로 실제 코드작업에서 많이 사용되지는 않는다. –일반적인 loop문을 이용한 해법이 이해도 쉽고 성능에도 유리하다.

하지만 재귀를 이해하는 것은 자신을 더 작은 문제로 쪼개고 그것의 옳음을 증명해 자신의 옳음을 증명하는 수학적 귀납법을 이해하는 것이기 때문에 논리적인 사고력 훈련에 도움이 되리라 생각한다. –재귀가 이루는 수학적 귀납법은 복잡함의 세계에서 자기유사성의 원리와도 맞닿아 있다.

쉽게 배우는 알고리즘

프로그래밍을 배우면서 놀랐던 적이 2번 있는데, 한 번은 C#에서 LINQ와 Lambda 식을 섞어 사용하는 것을 봤을 때였고, 다른 한 번은 재귀 알고리즘을 봤을 때였다. 재귀 알고리즘에 대한 놀라움 덕분에 나는 프로그래머는 아니지만 –가끔 오해하는 사람들이 있는데, 나는 'Designer'다– 알고리즘을 좀 배워봐야겠다는 생각을 하게 되었고, <Introduction to Algorithms>의 번역자인 문병로 교수가 직접 쓴 책인데다 '쉽게 배우는'이라는 타이틀이 달려 있어서 다른 책 보다 먼저 읽게 되었음. 

동일 저자의 <쉽게 배우는 유전 알고리즘>이 유전 알고리즘에 대한 기반 지식이 없으면 이해하기 어려워서 읽다가 말았는데, 이 책은 그것보다는 좀 쉬운 편. 알고리즘에 대한 기본적인 개념에서부터, 검색이나 정렬 등 실재하는 여러 문제에 대한 알고리즘과 NP 문제등 알고리즘에 대한 다양한 내용을 잘 다루고 있다. 

물론 교재로 쓰여진 책이니 만큼 한 번 읽었다고 내용을 온전히 이해했다고 보기는 어렵고, 별도로 공부를 해둬야 이해가 잘 될 것 같다. 다만 알고리즘에 대한 책은 많은 관계로 다른 책들도 살펴 본 후에 괜찮은 책을 따로 정리하는게 좋을 듯.

책 내용과는 별개의 것이지만, 결국 알고리즘이라는 것도 결국 생각하는 것과 관련한 것이라 알고리즘에 대한 지식을 배운다고 알고리즘 실력이 는다기 보기는 어렵고, 다양한 문제 상황에서 직접 문제를 해결하고 그것의 더 나은 방법을 찾아보고 해야 알고리즘 실력이 오르는 것 같다. –뭐 사람 하는 일에 아닌 일이 어디있겠느냐만– 

물론 도구를 쓰는 법을 배워야 도구를 사용할 수 있듯 이런 책을 통해 기본 지식은 배워야겠으나, 실력을 높이는 것은 어디까지나 직접해봐야 한다는 것. 다이어트 지식을 아무리 많이 가져도, 다이어트를 하지 않는 이상 살은 빠지지 않는다.

메트릭 스튜디오

컴퓨터 알고리즘 전문가인 문병로 교수가 이야기하는 수치와 확률에 기반한 주식 투자 방법. 이 책을 읽게 된 계기는 주식 투자에 관심이 있어서가 아니라 –후술 하겠지만 나는 주식에는 손대지 말라는 쪽에 가깝다– 동저자의 알고리즘 책을 보다가 통계와 관련된 내용이 좀 있는 것 같아 읽게 되었음.

저자는 주식 투자에 대해 통계적 사고와 세상의 파동에 대한 이해를 강조하는데 –오르고 내리는 것은 늘상 있는 일이고, 장기적 관점에서 그걸 인내해 내야 한다는 것을 강조– 개인적으로도 동일한 세계관을 갖고 있기 때문에 –세상은 확률-통계적이고 세상의 변화는 파동적이다– 책이 다루는 분야가 전혀 관심 없는 분야임에도 불구하고 배운게 많았다. –인간이 비합리적이라든가, 효율적 시장을 강조하는 경제학을 까는 이야기는 하도 많이 들어서 이제는 새롭지도 않음.

저자의 세계관에도 동의하고, 저자가 스스로 이야기하듯 저자의 알고리즘이 성공 확률을 높이는 것이라는 것에도 동의하지만 –단순히 추세선을 분석하는게 아니라 실제 기업의 재무제표 분석을 바탕으로한 투자 알고리즘– 주식에는 손을 대지 않는게 좋다고 생각하는데, 

일단 주식을 제대로 하려면 자신이 투자하는 대상에 대해 꾸준히 공부하고 감시해야 하는데, 이게 결코 만만치 않은 일이라는 것이 하나의 이유이고 –이래서 투자를 대신해 주는 사람이 먹고 사는 것이다. 기업 분석도 안하고 주식 투자 하는 것은 그냥 전재산 걸고 주사위 굴리는 것과 같음– 

결국 주식은 장기적으로 기업의 성장을 따라가는데, –이래서 나는 주식 시장을 랜덤워크라고 보는 시각에는 반대한다. 주식 시장이 완전 랜덤이면 기업의 성과와 별개로 주식 가격이 매겨져야하는데 현실은 그렇지 않다– 기업의 성장이 기업의 역량만 갖고는 안되고 운의 영향이 크다라는게 가장 근본적인 이유. 사업이라는게 단순히 잘하기만 한다고 성공하는게 아니다. 

물론 분야마다 그 크기는 다르겠으나 사업의 성공에는 운이 결정의 영향이 상당히 큼. 대단히 정량화된 분야가 아닌 이상, 대부분의 경우 운이 성공의 결정 요인으로 작용한다. 이에 대해 나심 탈레브는 성공한 사람과 그렇지 않은 사람은 유일한 차이는 '운'이라고 했는데, 나도 완전히 동의한다. 역량이 높으면 성공 확률이 높아지지만 그것이 성공을 결정하지는 않는다. –손자는 전쟁에 패배하는 것은 나에게 달린 것이지만, 전쟁에 승리하는 것은 적에게 달린 것이라고 했다. 성공은 내가 잘해서 이룰 수 있는 영역 바깥에 있다. 내가 잘해서 할 수 있는 것은 실패하지 않는 것 뿐.

다시 말해 근본적으로 운에 기대고 있는 사업가에게 기대는 것이 주식투자라서 주식에는 손을 대지 않는게 좋다는 것이 나의 지론. 주식을 하는 가장 좋은 방법은 본인이 사업을 해서 본인 회사 주식에 투자하는 것이다. 차선은 저자와 같은 높은 확률로 시장에서 승부하는 사람에게 맡기는 것이 되겠다.

미래를 바꾼 아홉 가지 알고리즘

현시대에 컴퓨터와 인터넷은 전화기나 전기, 수도, 가스에 비할 수 있을만큼 우리 생활에 밀접해져서 없으면 매우 불편한 –전기, 수도, 가스 없이도 살 수는 있다. 이미 적응된 우리의 삶이 대단히 불편해 질 뿐– 것들이 되었는데, 그러한 컴퓨터-인터넷 세계를 우리가 신뢰하고 사용할 수 있게 해주는 주요한 컴퓨터 알고리즘에 대한 설명을 담고 있는 컴퓨터 과학 교양서. 

내용 자체도 물론 좋지만, 이해하기 쉽지 않은 알고리즘의 기반 아이디어를 개념은 비슷하지만 쉽게 이해 가능한 아이디어를 이용하여 설명하는 부분이 대단히 훌륭함. 덕분에 나도 막연히 알고 있었던 내용을 꽤 잘 이해할 수 있게 되었다. 그렇게 이해하자니 왜 이 책에서 다루는 알고리즘들의 아이디어를 '천재적'이라고 부르는지에 대한 것도 이해할 수 있었다. –공개키 암호화와 오류 정정 코드의 개념을 이해할 때는 정말 뒤통수를 얻어 맞은 기분이었다.

컴퓨터에 대해 관심이 있다면 한 번쯤 읽어볼 만한 책이라 생각 됨.