2011년 2월 28일 월요일

현재부터 졸업까지 학점 정리(2011.04.18 수정)

3학년 복학할때 엄청 고민했던 내용을 또 하게 되었다.
경영 부전공을 안하려 결심했다가 4학년이된 지금 시점에서 되돌리려니 계절학기도 들을지 모르지만... 일단 강행 해보기로 했다.


졸업요구학점 총 136학점 중 4-1학기까지 144학점이수한 상태 (이미 충족)
제1전공과목은 심화전공 58학점 요구(요구학점(46)+심화요구(12))
- 4-1학기까지 60학점 이수했고(이미 충족), 4-2학기에도 전공 몇과목 들을예정
   그러면 60학점이상으로 제1전공 심화 이수 완료


경영학과 부전공
(학칙 13장 74조 3항)부전공을 이수하고자 하는 자는 부전공 학과 또는 전공의 전공선택과목 중에서 총 21학점이상이수 하여야 한다. 다만, 법과대학, 공과대학 및 건축대학의 총 이수학점은 따로 정한 바에 의한다.
- 현재 자본시장론, 금융기관론 6학점 이수상태


금융세부전공
대상 : 전공과 관계없이 경제학개론, 경제학원론1, 경제학원론2 중 1과목 이상 수강한 학생
개설학부(과) : 경제학부, 경영학부, 법과대학
경영학부 개설과목 중 금융세부전공 해당 과목
재무관리-> 투자론, 재무회계, 자본시장론(이수), 금융기관론(이수), 기업법, 보험론, 선물옵션, 재무설계실제(증권분석에서 이름변경)
*재무관리 선수과목은 경영통계수학(학부과기초)이다.
*재무회계 선수과목은 회계학원론(학부과기초)이다.
*참고로 학부과 기초과목은 경영부전공에도 포함이 되지 않는다.
*그 외 과목은 선수과목 없다.
위 과목중 6개이상 수강하고 평점평균이 2.5이상이면 세부전공 이수자로 인정한다.
- 현재 자본시장론(3학점), 금융기관론(3학점) 이수상태

가능성 재고
수강가능 과목
1학기 : 경영통계수학, 재무관리, 금융기관론, 경제학원론2
*재무관리는 선수과목 불충분으로 수강불가
여름학기 : 경영통계수학, 경제학원론2 (불규칙적이지만 열릴가능성있음)
2학기 : 기업법, 보험론, 선물옵션, 재무관리, 재무설계실제, 금융기관론

위험성
1. 2학기시간표가 저 과목끼리 겹칠 위험
2. 2학기 컴학부 전공과 위 전공과목 시간이 겹칠 위험


경영부전공을 위해 15학점 남았고, 금융세부전공을 위해 12학점이 남았다.
이 중 금융세부전공과 경영부전공 과목중 12학점이 겹친다.
단순 숫자계산으로는 두 학기에 걸쳐서
겹치는 12학점 + 경영부전공으로 3학점 = 15학점을 들어야한다.

얼핏보면 당연히 가능해 보이지만, 2학기에만 수강할 수 있는 과목이 있고, 서로 다른 학년의 과목이기 때문에 Risk가 상당하다.

불가항력 1방으로 모든계획이 무너질 수도 있지만, 나는 현재 내가 할 수 있는 최선을 다 하도록 하겠다. 그 다음에 불가항력이든, 운이 좋고 나쁨을 운운하자.

2011년 2월 27일 일요일

펀투상 강의 수강소감


토익시험 전날 영어공부하는 기회비용을 지불하고서 강의를 들으러 갔다.
그만큼 유익했고 큰 기회비용을 지불한 만큼 많이 얻어왔다. 물론, 아직 내가 암기해야 하는 부분이 많이 있지만, 전체적인 뼈대는 잡힌 느낌이다.

강사님 말씀대로 금융투자협회에 등록된 개인이 투자상담을 하고 펀드를 계약하여 fee를 받을 수 없다는 현행이 아쉬운 점이긴 하다.(강의듣기 전까지는 이런분야는 생각도 못했다.)
(현재 미국&영국에서는 개인 사업자 이름으로 펀드를 팔 수 있다.)

펀드투자상담사 자격증을 따면
투자권유대행인으로 증권사와 연계 후 활동이 가능하다고 한다.
집에 오는 내내 굉장히 궁금한 내용이었고 오늘 3시간넘는 검색 끝에 무슨 일을 하며, 증권사를 바꿀 수 있는지, 불이익은 어떤 점이 있는지 등등 꼬리에 꼬리를 무는 검색을 했다.

투자권유 대행인에 관해 알아낸 내용을 간략히 요약하면
1. 펀투상 합격 후 금투협 사이트에서 등록교육을 이수받아야한다.
2. 활동할 증권사(영업점까지) 선택
3. 필요서류 구비
4. 계약 체결 뒤 투자권유대행인으로서 대행인번호를 부여받고 활동가능
- 증권사와의 계약은 1년 단위로 자동연장됨.(특정사유가 있을경우 재계약시점에서 정지 당함)
- 2년에 한번씩 금투협에서 사이버 보수 교육을 받아야 한다.(유료이지만 대부분 증권사 지원)
- 각종 금융자격시험을 증권사에서 지원해준다.(교육비 + 응시료)
- 매 해 이행보증보험 가입(34000원) : 첫해는 증권사 지원
- 증권사와의 계약해지는 해지신청서 와 신분증 사본을 제출한다. (이후 타 증권사와 계약 가능)

교육을 받은 하나대투증권에서 할까, 취업을 은근히 갈망했던 한국투자증권을 할까,,
검색하다 알게된 교보증권 어느 지점에서 할까 고민중이다.

흥미와 관심으로 좀 더 깊이있게 공부하고 싶었고, 학교전공으로 수업도 들어 보고,
목표가 있으면 좋겠다 생각하여 자격증을 따보기로 했다. 아직 시험은 안봤지만(시험은 11년 3월 12일) 느낌은 좋은상태.
어쨋든 요는 이일은 생업으로 삼지 않을 것인데 고민을 하고 증권사 결정을 해야 하나 하는 회의도 좀 든다.(참고로  펀투상 자격증을 취득하고 5년간 활동을 하지않으면 자격증이 취소되기 때문에 증권사와 연계해서 활동중임을 나타내는 편이 좋다.) 하지만 기왕 하는거 신경 잘써주는 곳에서 하는게 좋을거라 생각한다.

2011년 2월 24일 목요일

신규 ETF '마이다스커버드콜'(137930) 상장

마이다스 커버드 콜 관련 정보
http://www.midasasset.com/product/pro03_view.aspx?fund_code=52437

마이다스에셋자산운용은 콜옵션(주식 매수 권리)을 활용해 완만한 상승장이나 횡보장에서 시장 대비 초과수익을 얻을 수 있는 '커버드콜(Covered Call)' 상장지수펀드(ETF)를 출시했다고 밝혔다.



커버드콜 전략은 현물 주식에 투자하면서 동시에 현재 주가보다 약간 높은 행사가격의 콜옵션을 파는 옵션활용 기법으로, 강세장에서는 이익이 제한되지만, 하락장의 방어력과 낮은 변동성이 특징이다.

회사 관계자는 "급등장에서는 수익이 일부 제한되나 완만한 상승장이나 횡보장, 하락장에서는 지수 대비 우월한 성과를 낼 수 있다"면서 "주식 수익률에 더해 매월 받는 옵션 프리미엄이 누적되면서 장기로 갈수록 투자 성과가 우수할 것"이라고 설명했다.

아울러 주요 타켓 투자자는 향후 주식시장이 단기 급등보다는 완만한 상승세를 유지할 것으로 전망하며 주가 하락 위험에 민감한 고객군으로, 단기보다는 장기투자를 선호하는 고객층이 주류가 될 것으로 전망했다.

15일 상장한 거래소(KRX) 커버드콜지수를 보면 코스피200이 1개월간 5% 이상 오르지 않으면 기준대비 초과 수익을 얻을 수 있다.


증권업계 관계자는 "최근 시장이 변동성을 높이고 있지만 추세적인 하락 국면으로 단정하기는 어려운 상황"이라며 "커버드콜 ETF도 현물 포지션을 정리하지 않았을 것으로 보인다"고 말했다. 이 관계자는 "현물 포지션 하락폭이 높아 콜옵션 매도 프리미엄으로 상쇄하기에 어려울 수도 있을 것"이라고 덧붙였다.

미리 상품 구조를 충분히 이해하고 투자해야 한다는 이야기다. "특정 시점에 도달해야 커버드콜 전략이 효과를 본다는 점을 먼저 알아야 한다"며 "기본적으로 현물을 매매한다는 점 또한 분명히 인지해야 한다"고 말했다.

2011년 2월 21일 월요일

배당주 투자 참고자료

2010년 하반기 참고자료.
고배당 관련주들

http://ydok007.blog.me/130094901058



ps. 배당시기에 발맞춰 KOSEF고배당 ETF 매수&매도 전략도 유효할듯 ,

2011년 2월 12일 토요일

706 : LCD Display

문제 : http://goo.gl/fynA1

+++++++++++++++++ WA문제 해결 ++++++++++++++++++++++++++++++++++++++++++++++++++++
큰 문제는 아니었다. 근본적인 문제에 해당한다고 봐야 하나...
LCD양식으로 표시하는 number 배열의 SIZE가 너무 작아서 WA판정을 받았던 것이었다.
이 문제점을 찾게 해준 알고스팟의 helloneo님께 감사를 표한다.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

왜 계속 WA가 뜨는지 도저히 모르겠다.
(출력문제 인것같아 다음 사항은 이미 모두 체크해보았다.)
- Minesweeper와 같은 한 줄 더 추가해서 문제가 생기는지 여부
- 00000001234 input시 1234로 출력
- 마지막 숫자 출력 후 1줄 띄워져 있는지 여부

로직은 다음과 같다.
1. 숫자를 string으로 받는다.
2. 첫번째값이 0이고, 길이가 1이 아닌경우 첫번째 값을 pop()하는 작업을 while() loop로 돌린다. ( 숫자앞에 0 제거)
3. 숫자가 필요한 size만큼 space를 채운다.( s+3열, 2s+3행 ) - s+3열인  이유는 문자사이마다 1줄의 공백이 들어가기 때문이다. 그리고 마지막 문자의 경우는 s+2열만 space로 채워서 마지막 숫자 출력하고 공백1줄이 들어가지 않는다.
4. 숫자가 출력될 공간의 가장 왼쪽 위지점을 함수로 넘겨서 숫자에 따라 달라지는 Seven Segment에 따라 '-'또는 '|'를 출력한다. (이미 공백이 위치한 값을 '-' 또는 '|'로 바꿔주는 것이다.) : 자료형은 char[][] 이다.
5. char[][] 배열을 출력한다.

소스의 자잘한 실수가 있는건지 WA가 계속나온다.. 소스를 짜는 시간의 몇배인 4시간 가까이 찾아보고,, 다른사람의 소스를 보고, 실행시켜 비교해봐도 WA인 이유를 모르겠다..
누군가 시원하게 답변해주길 기다린다..



while(cin >> s >> input)
 {
  int i, j, k;
  char number[23][SIZE]={};
  if( s==0 && input.length()==1 && input[0]=='0') break;
  
  // 숫자 앞의 0제거
  while(input[0]=='0' && input.length()!=1) input.erase(0,1);
  
  for(i=0; i<input.length(); i++)
  {
   // space로 필요한 공간만큼 채우고
   int tmp = i*(s+3)+s+3;
   if( i==input.length()-1) tmp--;
   for(j=0; j<2*s+3; j++)
   {
    for(k=i*(s+3); k<tmp; k++)
     number[j][k] = ' ';
   }
   // 숫자별로 Seven Segment 적용
   if( input[i]=='0')
   {
    top(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='1')
   {
    right_up(number, 0, i*(s+3), s); 
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='2')
   {
    top(number, 0, i*(s+3), s); 
    right_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='3')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='4')
   {
    left_up(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='5')
   {
    top(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='6')
   {
    top(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='7')
   {
    top(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='8')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='9')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
  }

  //Output
  if(cnt) cout << endl;
  for(int i=0; i<2*s+3; i++)
  {
   cout << number[i]<<  endl;
  }
  //cout << endl;
  cnt++;
 }

아래는 Seven Segment 부분을 채워주는 함수 이다.

void top(char num[][SIZE], int x, int y, int size) // up
{
 for(int i=1; i<1+size; i++) num[x][y+i] = CHARV;
}
void left_up(char num[][SIZE], int x, int y, int size) // left-up
{
 for(int i=1; i<1+size; i++) num[x+i][y] = CHARH;
}
void left_down(char num[][SIZE], int x, int y, int size) // left-down
{
 for(int i=size+2; i<2*size+2; i++) num[x+i][y] = CHARH;
}
void right_up(char num[][SIZE], int x, int y, int size) // right-up
{
 for(int i=1; i<1+size; i++) num[x+i][y+size+1] = CHARH;
}
void right_down(char num[][SIZE], int x, int y, int size) // right-down
{
 for(int i=size+2; i<2*size+2; i++) num[x+i][y+size+1] = CHARH;
}
void middle(char num[][SIZE], int x, int y, int size) // middle
{
 for(int i=1; i<1+size; i++) num[x+size+1][y+i] = CHARV;
}
void bottom(char num[][SIZE], int x, int y, int size) // down
{
 for(int i=1; i<1+size; i++) num[x+2*size+2][y+i] = CHARV;
}

2011년 2월 9일 수요일

10137 : The Trip

문제 : http://goo.gl/p7Pso

부동소수점의 연산은 최대한 피해야 한다는 것을 알려준 문제.
10분만에 풀줄 알았는데, 연산결과의 정확성이 떨어지는 것을 발견하고 이를 교정하는데 상당히 오랜 시간이 걸렸지만 결국 실패했다.

연산은 int형으로 하기로 결심했다. 이를 위해서는 먼저 (double변수*100+0.5)의 반올림 과정이 필요하다. (float으로 할 경우 1000명*10000달러의 데이터 합을 감당해 내지 못한다. -의외였다.)
그리고  사람수로 나눈 몫은  avg가 되고, 나머지는 돈을 많이낸사람에게 1원씩 배분해주어야 한다.(int로 변환한 뒤 1원. 본 문제에서는 1cent가 되겠다.)
많이낸 순서를 알기 위해서는 Sorting이 필요하고, 이는 qsort로 해결하였다.
(qsort 사용시 비교함수 만드는 법정도는 암기해두어야 겠다.)
평균의 차이를 계속 더해주고, 돈을 많이 낸 사람은 기존 평균에서 +1원한 뒤 계산한다.
그리고 다 더한 sum을 2로 나눠준다.( 그 이유는 분배한 돈중 주는 돈과 받는 돈을 중복적으로 계산 하였기 때문이다.) 이제 출력을 위해 100으로 나눠주어야 한다.



while(true)
 {
  int people;
  int ave=0, remnant;
  double sum=0.0;
  int pay[1000];
  
  scanf("%d", &people);
  if( people==0) break;

  REP(i, people)
  {
   double tmp;
   scanf("%lf",&tmp);
   pay[i] = (int)(tmp*100+0.5);
   ave += pay[i];
  }
  remnant = ave%people; // 나머지
  ave /= people; // 평균
  qsort(pay, people, sizeof(int), comp);
  
  REP(i, people-remnant)    sum += abs(pay[i]-ave);
  for(i=people-remnant; i<people; i++)sum += abs(pay[i]-(ave+1));
  printf("$%.2f\n",(sum/2.0)/100.0);
 }
int comp(const void *a, const void *b)
{
 if(*(int*)a<*(int*)b) return -1;
 else if(*(int*)a>*(int*)b) return 1;
 else return 0;
}

10189 : Minesweeper

문제 : http://goo.gl/wkdW

빌어먹을... 코딩은 10분~15분만에 후다닥 했는데, 그놈의 출력규격때문에 한참을 헤메다가 겨우 AC받았다.
PC는 AC나오는데 Uva는 WA나올경우가 많다. 되게 사소한 실수 일때 그런 경우가 발생한다.(또는 PC가 테스트를 대충하는 경향이 없지않아 있는것 같다.)

어쨋든,
반복문(출력후 1줄 비우는 것)이 아닌
반복문(1줄 비우고 출력) - 물론 첫번째는 1줄비우면 안되는 if문을 넣어야 한다.(더러운 코딩 -_-+)
그래도 안되는 분은 한문자씩 처리한 경우 끝문자열을 처리 했는지 살펴보자.
*을 만나면 주변 8방향+1씩 올렸다.
Index Overflow&Underflow 참조 관리 귀찮고 귀찮아서 넉넉하게 배열선언했다.

for(field=1; ; field++)
 {
  int m, n;
  string map[100];
  int anal[102][102]={};
  //Input
  scanf("%d %d", &n, &m);
  if( m==0 && n==0) break;

  if(field>1) printf("\n");
  
  for(int i=0; i<n; i++)
   cin >> map[i];

  //Process
  for(int i=0; i<n; i++)
  {
   for(int j=0; j<m; j++)
   {
    if( map[i][j]=='*' )
    {
     warning(anal, i+1, j+1);
    }
   }
  }

  // Output
  cout << "Field #" << field << ":" << endl;
  for(int i=0; i<n; i++)
  {
   for(int j=0;j<m;j++)
   {
    if( map[i][j]=='*')
     printf("%c", map[i][j]);
    else
     printf("%d", anal[i+1][j+1]);
   }
   printf("\n");
  }
 }

void warning(int anal[][102],int x, int y)
{
 anal[x+1][y-1]++;
 anal[x+1][y]++;
 anal[x+1][y+1]++;
 anal[x][y-1]++;
 anal[x][y+1]++;
 anal[x-1][y-1]++;
 anal[x-1][y]++;
 anal[x-1][y+1]++;
}

2011년 2월 8일 화요일

100 : The 3n+1 Problem

문제 : http://goo.gl/scOU

프로그래밍 챌린지 책을 보면서 새롭게 시작한 문제제공 및 Judge 서비스 해주는 곳이다. ACM ICPC와 매우 연관깊은 곳이기도 하다.

이 문제는 TLE에 유의해야한다.

힌트를 주자면 Memory cashing으로 Time, Space Trade-off하면 굉장히 빠른 시간에 답을 도출할 수 있다.
책을 자세히 읽어보지않아서 인풋을 while(scanf(...)==2) 이런식으로 받아야 하는 것을 몰라 한참 고민했다 ㅠㅠ..
- 주의 -
Recursion으로 구현했는데 FunctionCall StackOverFlow발생 :( ...
64bit integer 필요.


메모는 100만개짜리 int 배열.
while(scanf("%d %d",&a, &b)==2)
{
 int maxlen=0;
 int newA=a, newB=b;
 if(newA>newB) {newA=newA^newB; newB=newA^newB; newA=newA^newB;} // a,b swap

 for(int i=newA; i<=newB; i++)
 {
  cnt=1;
  int tmp;
  if( memo[i]==0)
   memo[i] = cycle_lenth(i);
  tmp = memo[i];
  if( tmp>maxlen) maxlen = tmp; // maxlen 갱신

 }
 printf("%d %d %d\n", a, b, maxlen);

}

int cycle_lenth(long long int n)
{
 long long int original = n;
 while(n!=1)
 {
  if(n<1000000)
   if(memo[n]!=0 )
   {
    cnt += (memo[n]-1);
  //  memo[original] = cnt;
    break;
   }

  if( n%2 ==0) //짝수
  {
   n /= 2;
   cnt++;
  }
  else //홀수
  {
   n = 3*n+1;
   cnt++;
  }
 }
 return cnt;
}

2011년 2월 5일 토요일

Diamond

 문제 : http://algospot.com/problems/read/DIAMOND

접근방법
특별한 스킬없이 막(?) 구현하였다.
문제를 풀면서 한 생각은... 이제 막 생각대로 프로그램 좀 짤 수 있겠다 싶은 1학년학생들 기죽이기 좋은 문제(? -_-;;)인듯하다. 'k!=0'이때문에 나온 WA가 날 포기하게 만들어서 거진 2~3주만에 부활시켜서 AC받아낸 문제..

내 소스의 단점은  다이아몬드를 점점 키우면서 검사하는데 같은 위치에서 size 1 -> 3 -> 5 ... 이렇게  늘어날 경우 테두리만 check하면 되지만, 귀차니즘으로...ㅠ Diamond 내부까지 다 검사하게 코딩했다. (TLE걱정할 문제도 아니고, Response Time도 괜찮게 나와서 궃이 수정하지 않았다.)

소스를 보면 중첨코딩으로 인해서 for문이 무려 4중첩이 되있지만 적절한 cutting으로 효율은 그리 나쁘지 않다.

위에서 언급한 k!=0 이거 찾아서 고치느라 소스 곳곳에 상세히 주석을 달았는데.. 보는사람에게 많은 도움을 줄듯하다.; (솔직히 for문장이 겹쳐서 소스보기 힘들지모르지만 주석을 보면 어느정도 이해가 가실듯...)


// 열 size를 구함
  int row=0;
  for(int i=0; pan[0][i]!=0; i++) row++;
  //pan 순회
  for(int i=0; i<size; i++)
  {
   for(int j=0; j<row; j++)
   {
    if( pan[i][j] == '#' )
    {
     int k;
     if( max == 0 ) max=1;
    
     //더 큰 다이아가 나올수 없는 행이면 종료
     if( i+max > size ) break; // 엄밀히 말하면 i+2*max-1 >size 이다. (궃이안바꿨다.)
    
     bool flag=false;
     while( true )
     {
      // Diamond 확장루틴
      // 세로방향(행) #판단 반복문
      for(k=1; k<max+1; k++)
      {
       // 가로방향(열)으로 # 판단 반복문
       // max를 아직 ++하기 전이기때문에 2k+1을 살핀다.
       for(int l=0; l<2*k+1; l++) 
       {
        // Array Index Underflow Handle
        if( j-k+l < 0)
        {
         flag=true;
         break;
        }
        // #이 아닌경우 max확장 실패
        if( pan[i+k][j-k+l]!= '#' )
        {
         flag=true;
         break;
        }
       }
       if( flag ) break;
      }
      if( flag ) break;
      // Diamond 축소루틴
      int bk=k;
      k--; // k가 1부터 시작했기 때문에 축소루틴에서는 1만큼 빼주고 시작
      while( k!=0 )
      {
       k--;
       for(int l=0; l<2*k+1; l++)
       {
        // Array Index Underflow Handle
        if( j-k+l < 0)
        {
         flag=true;
         break;
        }
        // #이 아닌경우 max확장 실패
        if( pan[i+bk][j-k+l] != '#' )
        {
         flag=true;
         break;
        }
       }
       if( flag ) break;
       bk++;
      }
      if( flag ) break;
      max++;
     }
    }
   }
  }

STL Container (vector)

벡터와 기존 타 STL 컨테이너 차이를 알고자 검색하다가

굉장히 정리가 잘된 블로그를 찾아서 링크 해놓는다.

vector 이외에도 List 등의 STL Container 내용이 상세히 설명되어있다.

Link : http://blog.daum.net/coolprogramming/77

Best Path On a Diamond

문제 : http://algospot.com/problems/read/DIAMONDPATH


접근 방법
Solution을 도출하기까지의 과정은 굉장히 빨랐다.
다만, 쌍for 한번으로 다이아몬드를 받아내려고, 테크닉을 부리다가 시간이 꽤 지났다..
(그냥 쌍for로 상단 삼각형모양받고 , 다시한번 쌍for로 받아도 되는걸 객기 부려봤다.;)

Input은 다소 낭비가 있더라고 다이아몬드를 받을 수 있는 크기의 2차원 배열(Notj jagged)로 받아서 처리했다. Memoization을 위한 배열 역시 같은 크기의 Array를 사용하였다.
다이아몬드 임의의 위치 n자신의 Cost를 Cost(n)이라고 하고, n까지의 도달하는데 최대Cost를 An이라고 하자.
An = Cost(n) + MAX( n에 도달할 수 있는 2개까지의 Path (A(n-1))
Array로 표현하자면,
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k-1])  // 다이아몬드 확장 루틴
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k+1])  // 다이아몬드 축소 루틴
// n-1, k-1, k+1을 하기 때문에 Index Overflow, Underflow관리는 알아서 해줘야 하는 사안.

// Maximum Cost로 Table Construction
  bool flag=false;
  tmpsize = size;
  path[0][0] = dia[0][0];
  for(int i=1; i<2*size-1; i++)
  {
   if( i>=size ) {tmpsize--; flag=true;}
   for(int j=0; j<tmpsize; j++)
   {
    if(flag) path[i][j] = dia[i][j] + max(path[i-1][j+1], path[i-1][j]);
    if( j==0 && !flag ) path[i][j] = dia[i][j]+path[i-1][j];
    else if(!flag)path[i][j] = dia[i][j] + max(path[i-1][j-1], path[i-1][j]);
    if( i==j ) break;
   }
  }

몇문제 풀고 보니 DP가 분석 후 문제 구축만 잘해내면 프로그래밍은 굉장히 깔끔하고
코드도 짧다.

2011년 2월 4일 금요일

Coin Change

문제 : http://algospot.com/problems/read/COINS


접근 방법
알고리즘 수업시간에 배웠던 내용이고, 공부했던 기억이 분명히 있었는데 한참을 떠올리려 고민하다가, 결국 강의자료 앞부분을 보고 점화식을 만들어 풀었다 ...;; 그때는 이해를하지 않고 암기를 해서 풀었나보다 (반성)ㅠ

잔돈의 종류가 n개로  k원의 거스름돈을 주는 가지수를 Coin(n, k)라고 하면,
임의의 잔돈 Cn이 포함된 경우 + 동전 Cn이 포함되지 않는 경우로 나눌 수 있다.

전자의 경우 Coin(n, k-Cn)
후자의 경우 Coin(n-1, k)
따라서 Coin(n, k) = Coin(n, k-Cn) + Coin(n-1, k)


발전적 제언.
k개 만큼의 배열을 선언하는데, 몇만원을 거슬러주는 경우 상당히 큰 배열을 필요로 하기때문에 메모리 초과현상이 나타날 수 있다. 이를 해결하기 위한 테크닉이 필요할 것 같다.
(물론 위 문제에서는 Cover 가능한 범위에서 Constraint되어 있다.)

#define REP(i,n) for((i)=0; (i)<(int)(n); (i)++)
// 초항 대입
  REP(i, numOfCoin+1) dp[i][0]=1;
  REP(i, change+1) dp[0][i]=0;
  //DP table 계산
  for(i=1; i<numOfCoin+1; i++)
  {
   for(int j=1; j<change+1; j++)
   {
    if(j-coins[i-1] < 0)
     dp[i][j] = dp[i-1][j];
    else
     dp[i][j] = (dp[i][j-coins[i-1]]+dp[i-1][j])%1000000007;
   }
  }

Tiling a Grid With Dominoes

출처 : http://algospot.com/problems/read/GRID

Google Code jam 문제풀다가 Dynamic Programming 벽에 부딫혀서 알고스팟의 DP문제를 물면서 연습도 하고, 감각을 익히려 한다.


  • Time Limit: 1000 ms
  •  
  • Memory Limit: 65536 kb
We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.
Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.

Input Specification

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.

Output Specification

For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.

Sample Input

3
2
3
7

Sample Output

1 5
2 11
3 781





해법
점화식 세우는 것이 관건.
An, Bn, Cn으로 나누어서 점화식을 다음과 같이 세웠다.
An = A(n-1)+A(n-2)+2*B(n-1)+Cn  : n번째 너비만큼 채우는 방법의 수
Bn = A(n-1)+B(n-1) : n번째 너비만큼 모서리2칸을 비운 나머지를 모두 채우는 방법의 수
Cn = A(n-2)+C(n-2) : n번째 너비만큼 'ㄷ'형태로 채우는 방법의 수
각 점화식의 초항(n=0~2까지)은 간단하기 때문에 손으로 구했다.

int a[1001], b[1001], c[1001];
int size;
a[0]=0;  a[1]=1;  a[2]=5;
b[0]=0;  b[1]=1;  b[2]=2;
c[0]=0;  c[1]=0;  c[2]=1;

in >> size;
for(int i=3; i<=size; i++)
{
 c[i] = a[i-2]+c[i-2];
 b[i] = a[i-1]+b[i-1];
 a[i] = a[i-2]+a[i-1]+2*b[i-1]+c[i];
}
ps. 문제 붙이니까 내 블로그 Grid랑 잘 안맞네;; 다음부턴 링크만 걸어둬야 겠다;

2011년 2월 3일 목요일

Google code jam 2010 Round A : Problem A

Problem : http://code.google.com/codejam/contest/dashboard?c=544101#s=p0&a=0

문제 접근

Rotation 후 중력작용이라고 했는데 결국 둘을 종합해서 Gravity방향을 파악해서 땡겨주면 된다는 점을 아는게 핵심이면 핵심이겠다. ( 이걸 몰라도 답은 구하겠지만, 소스 TLE나올 우려가 있다.) 나름 TLE 염려하면서 코딩했는데도 Large Set 컴파일하니까 0.5초정도 걸리더라..

천천히 모듈별로 짜서 하루 걸렸다. 문제에서 clockwise의 단어를 몰라서 그냥 그러려니 하고 넘어갔다가 나중에 90도 방향으로 1번 돌릴 수 있다고 해서... 나는 왼쪽 오른쪽 전부 코딩했다..;; 그리고 처음 상태에서 판별 + 회전한 상태에서 모두 판별 해서 이상하게 종합된 결과를 내서 Incorrect를 계속 받았다.. -_-;;  (역시 영어가 엄청 중요하다 ㅠㅠ - 해석이 어렵다가 이제는 아예 잘못읽어서 산으로 가다니...;;)

Rotation도 다 짜고 가만생각하니까 필요가 없었고... Gravity방향만 조절해주면 되었다..
여러모로 삽질을 많이 했던 문제.
디버깅할때 winCondition Size를 1줄이지 않은것때문에 2시간정도 찾다가 완전 의욕 잃고 게임좀하다가 다시 예제 하나하나 살펴보다가 이상한 곳을 발견해서 추적해 찾았다 -_ㅠ...

역시 WA가 뜰때는 완전 포기한 상태에서 처음부터 차근따라가는게 좋은 수다..;;

//right gravity
  for(int i=0; i<mapsize; i++)
  {
   int cnt=0;
   for(string::iterator iter=right[i].begin(); iter!=right[i].end(); )
   {
    if(*iter == '.') 
    {
     iter = right[i].erase(iter);
     cnt++;
    }
    else iter++;
   }
   if(cnt==mapsize) continue;
   else
   {
    for(int j=0; j<cnt; j++)
     right[i].insert(0,".");
   }
  }
  //checking Winner
  result = checking(right, winCondition, mapsize, &Bwin, &Rwin);

모듈별로 나눠서 코딩해서 그런지 코드가 나름 짧게 짰다. 하지만 그래도 130라인 ;;
8방향 삽질을 줄이고자 노력했으나,  쩝...;; 비슷한 라인이 뭉탱이로 있는곳이 군데군데 보인다 ㅠ
int를 리턴하는데, 0 : Neither, 1 : Blue, 2 : Red, 3 : Both 를 의미한다.

int checking(string* map, int win, int size, bool* Bwin, bool* Rwin)
{
 const char** tmp = new const char*[size];
 for(int i=0; i<size; i++)
 {
  tmp[i] = map[i].c_str();
 }
 for(int i=0; i<size; i++)
 {
  for(int j=0; j<size; j++)
  {
   if(tmp[i][j]=='B'&&!(*Bwin) || tmp[i][j]=='R'&&!(*Rwin))
   {
    bool flag=false;
    // 8방향에 대한 test 호출
    if(direction8(tmp, i, j, -1, -1, win-1, size)){flag=true;} //좌상
    else if(direction8(tmp, i, j, -1,  0, win-1, size)){flag=true;} //상
    else if(direction8(tmp, i, j, -1,  1, win-1, size)){flag=true;} //우상
    else if(direction8(tmp, i, j,  0,  1, win-1, size)){flag=true;} //우
    else if(direction8(tmp, i, j,  1,  1, win-1, size)){flag=true;} //우하
    else if(direction8(tmp, i, j,  1,  0, win-1, size)){flag=true;} //하
    else if(direction8(tmp, i, j,  1, -1, win-1, size)){flag=true;} //좌하
    else if(direction8(tmp, i, j,  0, -1, win-1, size)){flag=true;} //좌
    if(flag && tmp[i][j]=='B') *Bwin=true;
    else if(flag && tmp[i][j]=='R') *Rwin=true;
   }
  }
 }
 if(*Bwin && *Rwin) return 3;
 else if(*Rwin) return 2;
 else if(*Bwin) return 1;
 else return 0;
}

자질구레한 if문장이 엄청많은 이유는 8방향에 대한 제한 조건이 각각 달라서이다 ㅠ...
(처음에 엉뚱한 생각으로 통합했다가 디버깅으로 고친 문장..;;)
if문장은 Time Complexity에 큰 영향을 안주기에 더덕더덕 붙여서 썼다.

bool direction8(const char** map, int x, int y, int dir1, int dir2, int win, int size)
{
 bool winflag = true;
 //해당 direction 방향으로 진행할때 map을 벗어나는 경우 false 처리
 if( dir1==-1 && dir2==-1 ) //좌상
 { if(x+dir1*win<0 || y+dir2*win<0) return false;}
 else if(dir1==-1 && dir2==0) //상
 { if(x+dir1*win<0) return false;}
 else if(dir1==-1 && dir2==1) //우상
 { if(x+dir1*win<0 || y+dir2*win>=size) return false;}
 else if(dir1==0  && dir2==1) //우
 { if(y+dir2*win>=size) return false;}
 else if(dir1==1  && dir2==1) //우하
 { if(x+dir1*win>=size || y+dir2*win>=size) return false;}
 else if(dir1==1  && dir2==0) //하
 { if(x+dir1*win>=size) return false;}
 else if(dir1==1  && dir2==-1) //좌하
 { if(y+dir2*win<0 || x+dir1*win>=size) return false;}
 else if(dir1==0  && dir2==-1) //좌
 { if(y+dir2*win<0) return false;}

 for(int i=1; i<=win; i++)
 {
  if(map[x][y] != map[x+dir1*i][y+dir2*i])
   winflag =false;
 }
 return winflag;
}

2011년 2월 2일 수요일

파장을 일으키는 7개의 기업

- MBC스페셜에서 안철수교수님 말씀중 -
"세계적인 기업 Google에서 다음 7개 기업으로 빠져나가는 인재를 잡기 위해  연봉 10% 인상을 해줘도 막을 수 없다고 한다. 하지만 우리는 이 Google에 들어가고 싶어 안달이다."라고 했다.

그럼 그 7개 기업은 무엇일까? 뭐하는 회사인지 정도는 알아 놓자.


1. Facebook (http://www.facebook.com/)

 - 모르면 간첩... 부모님 세대라면 모를지도... (필자는 20대) , 제발 세상 돌아가는 것에 관심좀 갖자...  트위터와 함께 대표적인 미국의 SNS회사,  얼마전 시가총액이 미국의 대표적인 인터넷 마켓인 아마존을 추월했다.

 - 1번과 공감이다.

본인이 뉴스를 자주 안보더라도 주변에 유행을 좋아하는 친구정도만 있어도 위의 2가지는 알 것이다. 그럼 나머지 5개를 조사해보자.



3. Foursquare(http:/foursquare.com)

 위치기반 SNS 서비스 제공. User가 핸드폰 혹은 GPS가 있는 단말기를 통해 포스퀘어 App을 설치후 해당 건물, 거리에 자신의 발자취를 간단한 메시지와 함께 올릴 수 있고 친구들과 공유할 수 있다. 각 위치마다 Mayer라고 칭하는 대장(?) 터줏대감이 있는데, 그 지역에 정기적으로 자주 방문해서 발자취를 남기면 얻을 수 있다. 그외에 특정 조건을 만족하면 배지를 받을 수 있는데 이것도 하나의 재미로 여겨진다. 무엇보다도 타 SNS와 연동으로 편하게, 개방적으로 이용할 수 있는 게 장점. 이 회사도 필자는 이미 알고 있고 사용중인 SNS이기때문에 아는만큼만 적었다.


 구글의 60억달러 인수제안을 거부했다는 뉴스를 보고, 소셜커머스 업체라는 사업종류만 알고 있던 회사. 티켓몬스터를 필두로 파죽지세처럼 번져가는 소셜커머스가 무엇인지모른다면 그정도는 검색으로 꼭 알고 넘어가자. (본인의 경제력을 위해서도 그게 좋다.)
필자는 이 회사까지 딱 4개를 알고있었다.





이제 모르는 회사들은 검색으로라도 간단히 알고 가자.(Trend정도는 따라가야 않겠는가?)


  SNG게임개발업체, 미국에서도 굉장히 부상하고 있는 기업이며 검색해보니 최근에 9개의 게임제작 기업을 인수했다고 한다. 그리고 현재 facebook에 상위 랭킹되어있는 SNG는 대부분 이 업체에서 개발했다고 한다. 징가의 자산가치가 55억1000만달러로 EA를 앞지르고 세계 2위 게임업체가 되었다. (1위 업체는 블리자드)


6. Blippy (http://bilppy.com/)

  사용자가 신용카드로 구매한 내역을 친구들과 공유하는 SNS. 설립자 카플란은 많은 미국인들이 두 개 이상의 신용카드를 가지고 있다는 사실을 언급하며, "블리피에 등록된 신용카드로 스타벅스에서 커피를 산다면 바로 당신의 친구들이 당신이 스타벅스에 있다는 것을 알게될 것이고, 필요하면 스타벅스로 올 수도 있다. 사적인 용도로 사용하려면 등록되지 않은 나머지 카드를 사용하면 된다"라고 설명했다. 트위터와 마찬가지로 친구를 찾아 팔로우 할 수 있고, 자신이 팔로우한 사람의 물건구입을 알 수 있다. 물론 정보의 공개는 승인된 사람에게만 한다. 또한 아이튠즈나 아마존 구매내역과 같이 특정항목만 선택적으로 공유도 가능하다. 금융정보 노출에 대한 우려는 비공개 설정가능으로 일축하고있다. 공식오픈한지는 만1년정도 지났다.

7. YCombinator (http://ycombinator.com/)

 
회사라기 보다는 미국의 벤처기업 지원 프로그램? 프로젝트라고 표현하는게 더 맞는것 같다. 초기 단계의 벤처 투자에 특화된 새로운 형태의 업체. 주로 소프트웨어와 웹 서비스관련 업체에 투자한다. 기본적인 목표는 큰 규모의 투자를 달성하기 위해 필요한 위치에 도달할 수 있도록 지원하는 것. 초기에 $20,000 이하의 소규모 투자를 하고 기업지분의 2~10% 취득, 그 외에도 벤처 아이디어에 대한 공동작업 및 투자/인수자와의 계약, 법적 검토 지원. 유명 벤처 창업자, 금융가, 변호사, 회계사와의 만남주선으로 비즈니스  네트워크 형성을 돕는다.
벤처회사의 아이디어와 비전을 보고 사업 초기에 만나는 어려움을 돕는 대가로 쌀때 투자하는 형식의 투자회사라 생각한다.


세계적으로 이런 사업 비즈니스를 가진 회사들이 파장을 일으키고있다.
다행인지 불행인지, 세계적인 이런 파장이 일면 예전에는 5년 요즘은 1년 후면 우리나라에도 boom이 일어난다. 국내 유행에 민감한 사람이라면, 이제 해외를 둘러보고 우리나라 실정에 맞게 변화해서 시도해보자. 그렇게 까지 못하면 그런 곳에 투자라도 하자.

미래를 보는 안목을 길러야 살아남는다.







Google code jam 2010 Qualification Round : Problem C

Problem :  http://code.google.com/codejam/contest/dashboard?c=433101#s=p2


B번 문제에서 그렇게 해석에 애먹고 고생해서 그런지, 이번문제는 5분만에 읽고 해석 및 solution이 떠올랐다. 하지만, 세상에 쉬운일이 없듯이 이번 문제는 [효율]의 문제다.
그리고 또다시 부상한 Big Integer Class -_-+...


접근방법
문제를 읽은 후 사고의 흐름은 이렇다.
1. 배열로 그룹잡고 줄 빠지면 빼서 뒤로 넣고, 빼서 뒤로 넣고 하면되겠네.. 그런데 너무 삽질 같다?

2. 아, 그럼 STL의 위엄을 발휘해서 List로 하면 pop(), pushback()하면 편하겠다. 이렇게 해볼까?

3. 가만... 이거 1번 Riding할때마다 이렇게 수정해버리면 Overhead가 심해서 Complexity가 너무 올라가는데?.;;;

4. 아! 각 위치마다 시작지점과 버는 돈을 Hash Table로 만들어서 참조만 하면 효율이 확 올라가겠다!

5. 구축해놓고 참조만 할거니까, 컴퓨터적으로 조금 더 빠른 Array 2개를 이용하자!!

// next, earn 동적 배열을 채우는 루틴
  for(int i=0; i<numOfGroup; i++)
  {
   int sum=0;
   // cnt는 모두 태우고 남는 경우를 처리해주기 위함.
   for(int j=i, cnt=0; ; j++, cnt++)
   {
    if( j== numOfGroup) j=0;
    if( sum+group[j] <= canBoard && cnt!=numOfGroup)
    {
     sum += group[j];
    }
    else
    {
     next[i] = j;
     earn[i] = sum;
     break;
    }
   }
  }
 
  // solution 도출
  int forward=0;
  for(int i=0; i<numOfRide ; i++)
  {
   income += earn[forward];
   forward = next[forward];
  }

C++ Big Integer Class 구현

code jam 문제를 풀다가 두고두고 쓰면 좋을 것같아서 class file을 만들었다.
하지만 허접하게 구현해서 몇가지 제약사항이 있다.

<주의사항>
1. 뺄셈 operator 사용시 호출인자가 더 큰값이어야 한다.(아닐경우 unhandling)
2. 나눗셈 미구현

#include<string>
#define SIZE 100

using namespace std;

class BigInteger
{
private:
 string num;
 int range; //배열사용범위 표시
 int number[SIZE]; // 배열 1칸에 4자리의 숫자(0001~9999)가 들어간다
 int go_up[SIZE+1]; // 사칙연산 후 올림을 위한 수가 저장된다.

public:
 BigInteger(string n);
 string getNum();
 int* getNumber();
 int getRange();
 void operator+(BigInteger bi);
 void operator-(BigInteger bi); //앞의 인자(호출인자)가 무조건 크다는 전제
 void operator*(BigInteger bi);
 void operator/(BigInteger bi); //미구현
};

BigInteger::BigInteger(string n)
{
 memset(number,0,sizeof(int)*SIZE);
 memset(go_up,0,sizeof(int)*SIZE);
 num = n;
 int insert0 = n.size()%4;
 string tmp;

 for(int i=0; i<(4-insert0); i++)
 {
  n.insert(0,"0");
 }
 int index = (n.size()-1)/4;
 range = index;
 for(int i=0; index>=0;i++, index--)
 {
  tmp = n.substr(4*i,4);
  number[index] = atoi(tmp.c_str());
 }
}
int BigInteger::getRange()
{
 return range;
}
int* BigInteger::getNumber()
{
 return number;
}
string BigInteger::getNum()
{
 string largeNum;
 char tmp[5];
 for(int i=0; i<=range; i++)
 {
  itoa(number[i],tmp,10);
  largeNum.insert(0,tmp);
 }
 return largeNum;
}
void BigInteger::operator+(BigInteger bi)
{
 int index = range;
 int* big = bi.getNumber();
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<index; i++)
 {
  number[i]= number[i] + big[i] + go_up[i];
  go_up[i+1] = number[i]/10000;
  number[i] = number[i]%10000;
 }
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
 memset(go_up,0, sizeof(int)*100);
}
// 뺄셈시 앞의 big Integer가 무조건 크다는 가정임
void BigInteger::operator-(BigInteger bi)
{
 int index = range;
 int* big = bi.getNumber();
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<index; i++)
 {
  number[i]= number[i] - big[i];
  if( number[i] < 0) // 앞의 자리수에서 하나 꾸어 옴.
  {
   number[i+1]--;
   number[i] = number[i] + 10000;
  }
 }
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
}
void BigInteger::operator*(BigInteger bi)
{
 memset(go_up,0, sizeof(int)*100);
 int index = range;
 int* big = bi.getNumber();
 int tmp[100];
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<range+1; i++)
 {
  for(int j=0; j<bi.getRange()+1; j++)
  {
   tmp[j] = number[j] * big[i];

   go_up[i+j+1] += (tmp[j]+go_up[i+j])/10000;
   go_up[i+j] = (tmp[j]+go_up[i+j])%10000;
  }
 }
 memcpy(number,go_up,sizeof(int)*100);
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
 memset(go_up,0, sizeof(int)*100);
}

2011년 2월 1일 화요일

2006년 박경철 부자경제학 강의 요약.

감명깊게 보고 뜻하지 않게(?) 요약 동영상 편집을 했다.
안목을 기르기 위한 자기반성부분은 두고두고 다시 봐야겠다.
..;;


 : 투자전략 수립시 고려할 중요변수
 : 지속가능한(안정적) 수익률, 복리효과, 투자자산의 평균으로 회귀
 : 투자 수단의 평균 회귀

 


 : 부가가치가 있는 투자를 할 것
 : 초심자의 행운
 : ELS상품의 구조와 재테크 (철저한 리스크 관리의 중요성)


 : 직관과 영감에 과감한 투자, 미래의 비전을 보는 안목을 기르고 있는가 자기반성
 : 총정리

Euclid greatest common measure

1)유클리드의 호제법이란?
유클리드 호제법이란 최대공약수를 쉽게 구하는거예요.
예를들어 A = BQ + r
q 는 quoto 인가? 몫을 저렇게 사용하구요 r 은 나머지구요. ^^
이럴때 A 는 피젯수 , B 는 젯수라고 해요. 자, 이제 본론으로들어갑시다.
유클리드 호제법이란 A 와 B 의 최대공약수는
B 와 r 의 최대공약수와 같다는거예요.
예를들어 94 = 6 x 15 + 4
여기서 94와 6의 최대공약수는 2라는 것이죠.
마찬가지로 6과 4의 최대공약수는 2에요
응용으로 4389 와 2299 의 최대공약수는?
여기서 4389 = 2299 x 1 + 2090
2299 와 2090 의 최대공약수
2299 = 2090 x 1 + 209
2090 과 209의 최대공약수는 209 가 되겠네요 ㅋ

2)유클리드 호제법의 기본적인 원리
자연수 A , B 에 대하여 A 를 B 로 나누었을 때의 몫을 q ,
나머지를 r 이라 하자.
A , B 의 최대공약수를 x 라 하면 A = a'x 15 = 3 x 5 이고
최대공약수가 5일때 a'란 3이되겟죠.
B = b'x ( a' , b' 는 *서로소 { 이유는 최대공약수로 곱해졋으니 남은 곱해
지는수들은 더이상 나누어 지지 않아야겟죠} )
*relatively prime : 1 이외에 공약수를 갖지 않는 두 자연수를 말한다.
r = (a' - b'q)x 이유는 A = BQ + R 에서 a'x = (b'x)q + r 이고
r 은 a'x - b'xq = (a' - b'q ) x
따라서 A , B 의 최대공약수 x 는 B와 r 의 공약수다.
B 와 r 의 공약수인 이유는 아시겟죠?
r = ( a' -b'q)x 이고 B = b'x 잖아요 여기서 공통으로 x 가 들어가있네요.
그런데 a' , b ' 이 서로소이면 b' 와 (a'-b'q) 의 최대공약수는 1이므로
x 는 B 와 r 의 최대공약수이다.
따라서 . a,b 의 최대공약수는 b 와 r 의 최대공약수이다

출처 : 네이버지식인