zzun.net

100만달러 ‘수학난제’ 한국인이 풀었다

[한겨레 2004-12-05 20:51]  


[한겨레] 현상금 100만달러가 걸린 세계 7대 수학난제 중 첫번째 문제를 김양곤(55·수학통계정보과학부) 전북대 교수가 이끄는 국내 연구팀이 3년 만에 풀어냈다.
김 교수는 5일 “미국 클레이 수학재단(CMI)이 지난 2000년 상금 700만달러를 걸고 발표했던 세계 7대 난제 중 1번 문제를 풀어 독일의 논문평가기관인 첸트랄블라트에서 발간하는 논문집에 수록했다”고 밝혔다.

김 교수는 미국 위스콘신 대학 남기봉 교수와 함께 1번 문제인 ‘P 대 NP’를 공동으로 해결했다. 이번 논문은 지난 3월에 인도의 한 저널에도 발표됐다. 김 교수가 푼 ‘P 대 NP’는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가라는 문제로 물리학자들도 향후 10~20년 이후 해답이 나올 것으로 예측했다. 김 교수의 논문은 게재 후 2년 동안 수학계의 반응을 본 뒤 클레이 수학재단의 심사를 거쳐 100만달러를 수상하게 된다.

전주/박임근 기자 pik007@hani.co.kr ⓒ 한겨레(http://www.hani.co.kr), 무단전재 및 재배포 금지

Comment +4

  • zzun 2004.12.06 08:35 신고

    알고리즘 시간에 많이 들은 얘기지만..
    P=NP 가 연역적으로 풀이 가능하다면 정말
    알고리즘 학계에 역사상 최대의 사건이 되는건데 -_-
    그동안 수많은 시도가 있었고 다들 '풀었다!'라고 했지만
    다른 수학자 혹은 공학자들이 항상 오류를 발견해내었다 ㅡㅡ;;

    왠지 이번에도 그럴것 같은 느낌...

  • 2004.12.06 16:30 신고

    문병로 교수님이 수엽시간에 한이야기 생각난다
    그 수업들을 당시 약 몇초간...생각한건데..
    '함 풀어보까?'
    ㅋㅋㅋ

  • 2004.12.06 23:05 신고

    허허..전에 assignment problem 풀 때, 잠시 본 문제였는데..
    문제 자체를 이해하기도 힘들던데.. 허허..

  • zzun 2004.12.06 23:32 신고

    뵨//나도 그때 몇초간 생각했었어 ㅋㅋ
    엽//알고리즘 수업 들으면 문교수님이 친절히 설명해주신다 -_-;

http://acm.uva.es/p/v1/143.html

/**
Orchard Trees
zzun
hello82@unitel.co.kr
http://zzun.net
**/

#include <iostream.h>
#include <fstream.h>

ifstream fin;

void swap(float& a, float& b)
{
       float temp = a; a = b; b = temp;
}

bool read_input(float* x, float* y)
{
       bool rtn = false;
       for (int i=0; i<3; i++)
       {
               fin >> x[i] >> y[i];
               if ( x[i] > 0 || y[i] > 0 )
                       rtn = true;
       }

       return rtn;
}

int main()
{
       fin.open("test.in");
       float* x = new float[3];
       float* y = new float[3];
       int cur_y, count, tx1, tx2;
       float a1, a2, cur_x1, cur_x2;
       bool turn;

       while ( read_input(x, y) )
       {
               if ( y[1] < y[0] && y[1] <= y[2] )
               {
                       swap( x[0], x[1] );
                       swap( y[0], y[1] );
               }
               else if ( y[2] < y[0] && y[2] < y[1] )
               {
                       swap( x[0], x[2] );
                       swap( y[0], y[2] );
               }        // for largest y

               count = 0;
               turn = false;
               cur_y = (int) y[0];

               a1 = (x[1]-x[0])/(y[1]-y[0]);
               a2 = (x[2]-x[0])/(y[2]-y[0]);

               if ( a1 > a2 ) // which is on left side
               {
                       swap( x[1], x[2] );
                       swap( y[1], y[2] );
                       swap( a1, a2 );
               }

               cur_x1 = x[0] + a1*((float)cur_y - y[0]);
               cur_x2 = x[0] + a2*((float)cur_y - y[0]);

               while ( 1 )
               {                        
                       cur_y++;

                       if ( !turn && cur_y > y[1] && cur_y <= y[2] ) // find turning point
                       {
                               a1 = (x[2]-x[1])/(y[2]-y[1]);
                               cur_x1 = x[1] + a1*((float)cur_y - y[1]);
                               cur_x2 += a2;
                               turn = true;
                       }
                       else if ( !turn && cur_y > y[2] && cur_y <= y[1] )
                       {
                               a2 = (x[1]-x[2])/(y[1]-y[2]);
                               cur_x2 = x[2] + a2*((float)cur_y - y[2]);
                               cur_x1 += a1;
                               turn = true;
                       }
                       else
                       {
                               cur_x1 += a1;
                               cur_x2 += a2;
                       }

                       if ( (cur_y<=y[1] || cur_y<=y[2]) && cur_y<100 )
                       {
                               tx1 = ( cur_x1-(int)cur_x1 == 0 ) ? (int)cur_x1 : (int)cur_x1+1;
                               tx1 = ( tx1 == 0 ) ? 1 : tx1;
                               tx2 = ( (int)cur_x2 == 100 ) ? 99 : (int)cur_x2; // no point at 0&100
                               count += tx2 - tx1 + 1;
                       }
                       else
                               break;
               }
               
               cout << count << endl;
       }

       fin.close();
}

'IT > 소스코드' 카테고리의 다른 글

[C/linux] TCP/IP 가위바위보 게임 (Concurrent Server Version)  (0) 2004.07.07
Intersecting Circles  (2) 2004.06.15
[C++] Orchard Trees  (0) 2004.06.04
[C++] Maximum Sum (upgrade)  (2) 2004.05.18
[C++] Maximum Sum  (0) 2004.05.10
[C] AVL Tree  (0) 2003.10.16

Comment +0

[info]
http://acm.uva.es/p/v1/108.html
내림피아드 프로젝트의 첫번째 문제
O(N^3) 알고리즘

[test.in]
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

[n01_zzun.cpp]
/**

Max-Sum Subrectangle Search

zzun
http://zzun.net
hello82@unitel.co.kr

**/

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>

int array_size;
char** num_array;

bool read_input(char* filename)
{
       ifstream fin;
       int buf;

       fin.open( filename );

       fin >> array_size;        // take the array size N
       if ( array_size <= 0 )
       {
               cout << "Error : array size!" << endl;
               return false;
       }

       num_array = new char*[array_size];
       for (int i=0; i<array_size; i++)
               num_array[i] = new char[array_size];        // 2-dim array M-allocate

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
               {
                       fin >> buf;
                       num_array[i][j] = (char) buf;        // take the values
               }
       
       fin.close();

       return true;
}

int main()
{
       char* input_filename;
       int** sum;
       int max = 1 << 31;
       int local_max, local_max_candi, temp;

       input_filename = "test.in";        

       if ( !read_input(input_filename) )
               return -1;

       sum = new int*[array_size+1];        // 2-dim array for SUM from [0,0] to [x,y]
       for (int i=0; i<array_size+1; i++)
       {
               sum[i] = new int[array_size+1];
               sum[i]++;        // move the pointer to use the -1 index
       }
       sum++;        // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]

       for (int i=-1; i<array_size; i++)
       {
               sum[i][-1] = 0;
               sum[-1][i] = 0;        // init
       }

       for (int i=0; i<array_size*2-1; i++)
               for (int j=0; j<=i; j++)
                       if ( i-j < array_size && j < array_size )
                               sum[j][i-j] = num_array[j][i-j] + sum[j-1][i-j] + sum[j][i-j-1] - sum[j-1][i-j-1];        // calculate sum[][], O(N^2)

       for (int i=0; i<array_size; i++)
               for (int k=0; k<=i; k++)
               {
                       local_max = 1 << 31;
                       local_max_candi = 0;
                       for (int j=0; j<array_size; j++)
                       {
                               temp = sum[i][j] - sum[i][j-1] - sum[k-1][j] + sum[k-1][j-1];
                               local_max_candi += temp;
                               if ( temp > local_max && temp > local_max_candi )
                                       local_max = local_max_candi = temp;
                               else if ( local_max_candi > local_max )
                                       local_max = local_max_candi;
                               else if ( temp > local_max_candi )
                                       local_max_candi = temp;
                       }
                       max = (local_max > max) ? local_max : max;
               }

       cout << max << endl;

       sum--;
       for (int i=0; i<array_size+1; i++)
       {
               sum[i]--;
               delete [] sum[i];
       }
       delete [] sum;        // M de-alloc

       return 0;
}

'IT > 소스코드' 카테고리의 다른 글

Intersecting Circles  (2) 2004.06.15
[C++] Orchard Trees  (0) 2004.06.04
[C++] Maximum Sum (upgrade)  (2) 2004.05.18
[C++] Maximum Sum  (0) 2004.05.10
[C] AVL Tree  (0) 2003.10.16
[C] fork(), exec(), and wait()  (0) 2003.10.16

Comment +2

  • zzun 2004.05.19 03:19 신고

    우선 1차원 행렬에서 maxsum substring을 O(N)에 구하는 알고리즘

    a1, a2, ..., ax, ..., ay, ay+1, ..., ak-1, ak, ...
    이런 행렬이 있다고 치고,
    a1~ak-1 중에 maxsum substring을 ax...ay 라고 하자.

    그렇다면 위의 조건을 이용하여 a1~ak의 maxsum substring을 O(1) 안에 구할 수 있으면
    귀납법으로 전체의 maxsum substring을 O(N) 안에 구할 수 있게된다.

    a1~ak의 maxsum substring이 될 수 있는 후보는,
    1. a1~ak-1의 최대값인 ax...ay : max
    2. 새로운 원소 하나 ak
    3. 또 다른 스트링 az...ak (단, x<=z<k) : candi
    위에서 1번과 3번을 편의상 max랑 candi라고 부르자.

    여기서 candi 값을 잘 유지하는게 중요한데
    임의의 점부터 현재원소까지의 합 중 maximum 값을 유지해야 한다.
    (즉, ak를 끝점으로 하는 substring 중에 max를 말한다.)

    위의 과정을 하는 코드를 짜보면..


    max = -inf; candi=0;
    for k=1 to k=N
    {
    candi += ak
    if ( ak > max && ak > candi )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max = candi = ak; // 위에서 2번 후보에 해당
    else if ( candi > max )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max = candi;&nbsp;&nbsp;// 위에서 3번 후보에 해당
    else if ( ak > candi )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;candi = ak; // candi를 최신으로 유지하기 위한 코드
    } // 위에서 1번 후보의 경우는 max값을 갱신할 필요 없음
    print max;



    이래서 1차원 행렬의 max를 O(N) 만에 구할 수 있다.

    이것을 2차원에 적용하는 방법은
    사각형의 네 좌표를 [,]-[,] 식으로 나타낸다면
    [0,a]-[0,b] (a,b는 임의의 수) 같은 사각형은 총 O(N^2)개 존재한다.
    이 각 사각형들 내부의 합은 우리가 N^4할때 썼던 방법으로 쉽게 구하고
    이 사각형 중 maximum은 위에서 언급한 1차원 알고리즘으로 구할 수 있다.
    즉, O(N) 시간안에 최대값을 구할 수 있다는 얘기다.
    이런 방법으로 [0,a]-[1,b] 의 최대값, [2,a]-[5,b] 의 최대값
    식으로 구하면
    총 O(N^2)개의 최대값을 O(N^3) 시간 안에 구할 수 있고
    그 모든 최대값 중에 최대값이 바로 우리가 원하는 값이다.

  • 2004.05.22 19:22 신고

    좀 퍼갈께..ㅋㅋ


티스토리 툴바