Algospot - QUANTIZE 알고리즘

//

//  main.cpp

//  quatnization

//

//  Created by sungjuho on 2014. 4. 20..

//  Copyright (c) 2014 sungjuho. All rights reserved.

//

#include <cstdio>

#include <cstring>

#include <algorithm>


#define N 101

#define MAX 1000000000


using namespace std;


int nCase,patternLen,useNum;

int input[N];

int dp[N][10];


inline int roundToInt(float val){return (int)(val+0.5);}


inline int getQuant(int s, int len)

{

    int result=0;

    int avgSum=0;

    int avg ;

    int d;

    

    for(int i=0; i < len; ++i)

    {

        avgSum += input[s+i];

    }

    

    avg = roundToInt( (float)((float)avgSum / len));

    

    for(int i=0; i < len; ++i)

    {

        d = input[s+i]-avg;

        result += d*d;

    }

    

    return result;

    

}

int solve(int s, int n, int k)

{

    if(patternLen<=useNum)

        return 0;

    

    if(dp[n][k])

    {

        return dp[n][k];

    }

    

    if(k==1)

    {

        return getQuant(s, patternLen-s);

    }

   

    int sum = 0;

    int min = MAX;

    

    for(int i=1; i <= n-k+1; ++i)

    {

        sum = getQuant(s, i);


        sum += solve(s+i, n-i, k-1);

        

        if(sum < min )

        {

            min = sum;

        }

    }

    

    dp[n][k] = min;

    

    return dp[n][k];

    

}


int main(int argc, const char * argv[])

{

    scanf("%d",&nCase);

    

    while(nCase-->0)

    {

        scanf("%d%d",&patternLen,&useNum);

        

        memset(dp, 0, sizeof(int)*N*10);

        

        for(int i=0; i < patternLen; ++i)

        {

            scanf("%d",&input[i]);

        }


        sort(input, input+patternLen);

        

        printf("%d\n",solve(0,patternLen, useNum));

    }

    return 0;

}



Lexical Analysis 컴파일러


* 기본 숙지 사항
 

1. 컴파일러의 수행절차

(1) Lexical Analysis
(2) Parsing
(3) Semantic Analysis
(4) Optimization
(5) Code Generation

* Lexical Analysis란...

 실생활에서 Lexical Analysis의 예를 든다면, 문장을 보고 의미단위로 쪼개는 것을 의미한다.

 예시)  He go home. 이라는 문장을 Lexical Analysis(구문분석)을 한다면, He, go, home 이렇게 나눌 수 있다.

 그리고 He는 주어(Subject), go는 동사(Verb), home 목적어(Object)라고 부른다. 이것들은 각 문장 성분의 한 요소이다.

 이와 마찬가지로, 컴파일러에서 Lexical Analysis는 구분자(Punctuation)로 나뉘어진 코드 라인을 작은 의미 단위로 쪼개는 것이다.

 작은 의미 단위로 쪼개는 이유는, 이후 처리에 대해 간결하게 하기 위함이다. (내 추측임..) 

 Lexical Analysis에 의해서 쪼개어진 부분 문자열을 유식하게 Token이라고 부른다.

 Token은 <Class, Stiring> 쌍으로 구성된다. 여기서 Class는 우리가 쓰는 언어에서의 문장 성분에 해당한다.

 Class의 구체적인 종류로는..

  -> Identifier -  |a-zA-Z|*|0-9|* 
  -> Number - |0~9|
  -> Operator  - *,+,-,/,% (산술연산), ||, ==, ^,~,|(논리연산), = (대입연산)  
  -> Keyword - 예약어라 불리며, if-then-else , while ... 일련의 컴파일러에 미리지정된 명령어이다.
  -> Whitespace - 위의 요소들을 문장에서 서로 구분해주는 역할을 한다. 
  등이 있다. 

 String은 나뉜 부분 문자열이다.

 예를 들어보자.  아래 코드는 3개의 토큰으로 분리가 될 수 있다. 

  foo = 42;
 
 <Identifier, foo> , <operator, = >, <number, 42>

<TokenClass, Lexeme>도 <Class, String>과 똑같은 의미를 지닌다. 

나중에 나오겠지만, Lexical Analysis로 추출해낸 Token은 Parser의 입력데이터로 들어가 문장 구조 분석을 수행하게 된다. 



 

근황 일상생활

현재 직장인이 되어, 게임 회사(C****) 에 근무중입니다..

올해 5~6월 정도에 게임 출시 예정에 있습니다.

근 2년간 뜸했는데.. 이제 다시 시작해볼까합니다.

제 분야(IT)외에도 여러가지 경험과 생각에 대해 여기에 글로 적어서 조금이나마 발자취를 남겨야 될 것 같아서..

모쪼록 잘 지켜봐주세요~ 



LL(1) Parser에 대한 개인적인 정리 컴파일러


파서는 렉서(스캐너)로 토큰단위로 자른 문자열을 심볼로 인식해서 파싱트리로 만들어주는 역할을 한다.

컴파일러는 파싱 트리를 가지고 입력으로 들어온 문자열들이 문법적으로 타당한지의 여부를 검사하게 된다.

즉, 파서는 각 문자열이 스캐너에 의해 토큰으로 나뉜 것에 의미를 부여하고 문법(CFG)의 타당성을 검사하는 역할을 한다.

파서에는 두 가지 종류로 나뉘게 되는 데 상향식 파서와 하향식 파서로 나뉘게 된다.

하향식 파서는 시작 심볼로 시작해서 주어진 입력문자열(터미널 심볼)로 만드는 과정이고, 상향식 파서는 주어진 입력문자열에서

시작 심볼까지를 만드는 과정이다. 즉, 하향식 파서는 파스 트리를 루트노드에서 부터 시작해서 트리를 만드는 과정이고, 상향식 파

서는 단말 노드에서 부터 시작해서 트리를 만드는 과정이다.

지금 내가 정리 할 부분은 하향식 파서이다.

하향식 파서는 predicctive 파서라고 부른다. 이 파서는 어떤 상태에서나 파스 트리의 다음 낮은 단계를 예측하려고 한다. 이러한

예측은 입력의 다음 토큰과 현재의 트리를 검사한 후, 다음에 시도할 생성규칙을 선택하는 것으로 행해진다.

따라서, 파서는 좌측유도(입력 토큰을 좌측부터 읽어서 변환 시키기 때문..)를 실시하면서, 위에서 아래로 파스 트리를 구축한다.

하향식 파서는 두 가지 방법으로 접근하게 된다.

1.재귀하강파싱

 - 재귀 하강 파싱은 파스 트리를 구성하기 위해서 재귀적인 방법을 사용해서 생성한다. 문법에 있는 각각의 난터미널에 대해서 그

난 터미널을 구문분석하는 프로시져를 가진다. 이 프로시져들은 입력을 읽으면서 생성규칙의 오른쪽에 있는 터미널 심볼들을 맞추

어보거나, 입력을 읽는 프로시져나 터미널 심볼들을 맞추어보는 프로시져를 호출한다. 이 방법은 좌측 재귀 방법을 제거해야한다.

왜냐하면 S -> SR 일 경우 각 심볼마다 프로시져가 있는 데, S심볼에 대한 프로시져는 무한루프에 빠지기 떄문이다.

그래서 왼쪽 반복이 제거되도록 해서 프로시져를 작성해야된다.

2.LL(1) 파싱

 - LL(1)파서는 구문 분석을 위해 테이블을 사용한다. 첫번째 L은 입력 스트링이 왼쪽에서 오른쪽으로 스켄됨을 의미한다. 

두 번째 L은 좌측우선유도로 구성됨을 의미한다. 1은 하나만 미리본다는 뜻이다. 단지 단 하나의 다음 심볼을 보겠다는 의미이다.

위에 재귀하강파싱 방법에서는 재귀하강파싱만의 문법(좌측 재귀 방법을 제거하기..)이 있듯이, LL파싱에서도 자기만의 문법이있다.

먼저 문법이 left-factoring이 되어야 한다. 가령, 문법이 E -> T+E | T , T -> int | int * T | ( E ) 일 경우, 

E에서 T로의 두 개의 경우로 분기하게 된다. 그리고 T가 두 개의 int로 분기하게 된다. left-factoring은 같은 기호들을 prefix로 가지는

2개 이상의 생성 규칙이 존재할 때에, 새로운 중간 생성 규칙을 두어서 하나의 prefix에 대해 1개의 생성 규칙으로 변환 시켜주는 것이다. 

만약에 그렇게 하지 않을 경우에는 결정적이지 못하고, 백트래킹을 하게 되므로 효율성이 많이 떨어지게 된다.

A -> aB1 | aB2 | aB3  일 때,

A -> aA'
A' -> b1 | b2 | b3 .. 

이렇게 바꾸면 된다.

LL(1)파싱은 테이블과 스택을 이용해서 하향식으로 파싱을 하게 된다. 테이블은 로우 인덱스는 논터미널 심볼로 구성되어있고,

테이블의 칼럼인덱스는 논터미널 심볼과 $로 구성이 된다. 파싱하는 방법은 아주 간단하다. 처음에 스택에 시작 심볼과 $를 넣는다.

>> 테이블을 이용한 파싱방법

1. 스택의 TOP과 입력문자열을 비교해본다.

1-1. 스택의 TOP과 입력 문자열이 같을 경우, 스택 TOP을 팝시키고, 다음 문자를 읽는다.

1-2. 스택의 TOP과 입력 문자열이 다를 경우,

   1-2-1 :  스택의 TOP과 입력 문자열에 T[S_TOP, Input] = a가 있을 경우 스택의 탑을 팝시키고, a를 스택에 넣는다.
   1-2-2 :  스택의 TOP과 입력 문자열에 T[S_TOP, Input] = NULL 일 경우 에러 처리시키면 된다.

2. 스택이 전부 빌때까지 계속 1번 과정을 반복한다.


>> 테이블을 만드는 방법

테이블은 각 논터미널 심볼에 대해서 FIrst,Follow set을 구한 다음에,  테이블 생성 알고리즘을 거쳐 각 칸마다 내용을 채워넣는다.

1. First Set 구하기

First(X) = { t | X ->* tA} U { eipsilon | X->* eipsilion} <- 이 경우는 S -> AB , A-> x | epsilon  일 경우 S의 FIRST는 B의 FIRST가 된다.

예  :  E -> TX, X -> +E | Epsilon , T -> ( E ) | int Y , Y -> *T | epsilon  일 때,

FIRST(E) = { ( , int }
FIRST(T) = { ( , int }
FIRST(Y) = { *, epsilon}
FIRST(X) = { +, epsilon}

2. Follow set 구하기

Follow(X) = { t | s -> *BXtY} , 여기서 B는 터미널 혹은 논터미널 심볼이다. 논터미널 심볼 X 다음에 터미널 심볼 t가 Follow(X)의 원소가 된다.

(1) IF X -> AB then FIrst(B) is Subset of Follow(A) : X -> AB ->* Atq 가 될 경우 Follow(A)는 t가 된다. 그리고 First(B)도 t가 되므로

First(B)는 Follow(A)의 Subset이 된다. <- 여기서는 왜 그런 관계가 되는지 아직 이해가 안된다.

(2) IF X->AB then FOLLOW(X) is Subset of Follow(B) :  S -> Xt ->ABt   but b go to epsilon FOLLOW(X) is subset of Follow(A)
(3) IF X is Start Symbol $ is element of Follow(X)


예  :  E -> TX, X -> +E | Epsilon , T -> ( E ) | int Y , Y -> *T | epsilon  일 때,

Start Symbol은 E 이므로, 먼저 Follow(e) = { $,  } 를 쓴다.

그리고 T -> ( E ) 에서 E 다음에 터미널 심볼 ) 이 나오므로, Follow(e) = { $ , ) , } 를 쓴다. 

X->+E에서  FOLLOW(X) < FOLLOW(E)가 된다. 그리고 E->TX에서 FOLLOW(E) < FOLLOW(X)가 된다. FOLLOW(X) == FOLLOW(E)가 되고

더 이상 E에 관해서 찾을 수 있는 것이 없으므로 FOLLOW(E) = { $, ) }, FOLLOW(X) = {$,)} 가 된다.

FOLLOW(T)를 찾아보자. 먼저 E->TX에서 X가 EPSILON에 갈수있으므로 FOLLOW(T)는 FOLLOW(E)를 서브셋으로 갖는다.

FOLLOW(T) = { $, ) , } 이고, E->TX->T+E가 되므로 FOLLOW(T) = { $, ), + , }이 된다. 

FOLLOW(Y)를 찾아보자.  T-> int Y 에서 FOLLOW(T)는 FOLLOW(Y)의 부분집합이 된다. 그리고 Y->*T에서 FOLLOW(Y)는 FOLLOW(T)의

부분집합이 된다. 그래서 FOLLOW(Y)와 FOLLOW(T)는 동치가 되서 FOLLOW(Y) = { $, ), +}이 된다.

정리해보면 

FOLLOW(E) = { $, ) } , FOLLOW(X) = {$,)} , FOLLOW(T) = {+,$,)}, FOLLOW(Y) = {+,$,)}이 된다.

3. Table 생성하기

For each Production A -> a(terminal or non terminal) in G do :

(1) terminal t is element of First(a) : if a lengh is more than 1, select to first character of a.
 
 T[A,t] = a 

(2) if epsilon is element of  FIRST(a), and for each t element of Follow(A)

 T[A,t] = a

 (3) if epsilon is element of FIRST(a) AND $ is element of FOLLOW(A)

  T[A,$] = a

이 세가지 방식으로 채워놓으면 된다. 



 

10258 – Contest Scoreboard 알고리즘

#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef struct Problem
{
bool isAccept;
int nPanelty;
Problem()
{
nPanelty=0;
isAccept=false;
}
};
typedef struct Team
{
int n;
int solved;
int time;
Problem p[100];
Team()
{
n=0; solved=0; time=0;
}
};

bool cmp(const Team& t1, const Team& t2)
{
if(t1.solved > t2.solved)
return true;
else if(t1.solved==t2.solved)
{
if(t1.time < t2.time)
return true;
else if(t1.time==t2.time)
if(t1.n < t2.n)
return true;
}
return false;
}

int main()
{
int n,team,prob,time;
char c;

scanf("%d",&n);
getchar();
getchar();
for(int i=0; i < n; i++)
{
//char ch = getchar();
map<int, int>m;
vector<Team> t;
int cnt=0; 
char line[255];
while(gets(line)&&line[0])
{
sscanf(line,"%d %d %d %c",&team,&prob,&time,&c);
if(m.find(team) == m.end())
{
m.insert(pair<int,int>(team,cnt++));
Team s;
s.n = team;
t.push_back(s);
}
switch(c)
{
case 'I': 
if(!t[m[team]].p[prob].isAccept)
t[m[team]].p[prob].nPanelty++;
break;
case 'C': 
if(!t[m[team]].p[prob].isAccept)
{
t[m[team]].p[prob].isAccept = true;
t[m[team]].solved++;
t[m[team]].time += t[m[team]].p[prob].nPanelty*20+time;
}
}
}
sort(t.begin(),t.end(),cmp);
if(i)
putchar('\n');
for(vector<Team>::iterator it = t.begin(); it != t.end(); it++)
{
printf("%d %d %d\n",it->n,it->solved,it->time);
}
}
return 0;
}

1 2 3 4 5 6 7 8 9 10 다음