글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

경기과학고등학교의 친구들과 함게 학교를 째고 ACM-ICPC(대학생 프로그래밍 경시대회)에 번외 참가하러 왔습니다. 원래 고등학생은 예선에만 번외참가했었는데(Challenge XX) 이번에는 본선에 번외 참가하게 되었습니다.

오늘은 예비소집이고, 내일이 본 대회이며 오늘은 4위의 성적을 거두었습니다. 처음에 저희 팀 자리에 잘못된 비밀번호를 알려주셔서 초기에 한 5분 정도 지연되는 바람에 5분 정도 늦게 시작한게 조금 아쉽네요.

1번은 1번답게 값 받아서 간단하게 사칙연산해서 출력하면 되고, 2번으로는 Slicing Tree라는 기출문제가 나왔습니다. 이전에 한 번 풀어본 문제였기 때문에 코딩 도중 약간 헷갈리기는 했지만 금방 짜서 제출할 수 있었습니다.

키보드가 엄청 부드러워서 좀 익숙하지 않았습니다. 다 짜고 시간이 남길래 키보드에 익숙해질 겸 팀원이 돌아가면서 풀었던 문제를 한 번 더 풀어봤습니다.

제가 원래 한 번 틀리면 그 뒤로 계속 틀리는 징크스가 있어서 걱정했는데, 다행히 예비소집 때는 컨디션이 좋았던 것 같습니다.

예비소집 끝나고 나서는 숙소에 짐을 풀었는데, 저희 숙소에 도쿄대 팀이 묵는다는 정보를 선생님께서 얻어오셨습니다. 도쿄대 팀에는 마코토 소에지마(rng), 쇼고 무라이 등 아는 사람은 아는 고수들이 있기 때문에 기대하고 있었는데, 카운터에 문의해서 숙소를 알아냈습니다(알려주면 안 될 것 같은데)

나중에 숙소로 쳐들어갈까 어쩔까 하다가 그냥 저희 방으로 들어왔는데 갑자기 선생님께 연락이 오더니 지금 도쿄대 팀이랑 얘기하고 있다고 숙소 앞으로 나오라고 하더군요. 내려가보니 정종광 선생님께서 유창한 일본어로 도쿄대 팀이랑 대화하고 있었고 같이 밥을 먹게 되었습니다.

한식집이었는데 보쌈 + 돌솥밥 + 불고기를 먹었습니다. 불고기를 좀 일찍 시켰어야 되는데 타이밍이 안 맞아서 돌솥밥을 다 먹고 불고기가 나왔다는게 좀 아쉽긴 했지만 맛있었습니다. 그리고 비쌌죠

처음에는 도쿄대 팀이랑 어색어색해서 말을 못 붙였는데 한 번 말 걸고 나니까 어느 정도 대화가 되더군요. 일본인이랑 제대로 대화해본 건 처음인 것 같네요.

저희 팀 한 명은 일본어 아예 못 하는데 나머지 한 명은 일본어 어느 정도 되는데 말을 못 걸더군요. 이런 때 아니면 언제 말 걸어보겠냐고 꼬드겼는데 결국 제대로 말 못걸고 끝났네요.

김치 같은거 매울것 같애서 맵지 않냐고 물어보니까 쇼고 무라이가 매운거 좋아한다고 ㅋㅋ 또 기억나는건 새우젓보고 뭐냐 그래서 새우(에비)라고 대답했더니 무슨 새우냐고 해서 그냥 작은 새우라고 했더니 자기들끼리 새끼 새우인가보다 이러면서 보쌈 찍어먹는게 재밌었음.

다른 사람은 배불러서 다 먹었는데 쇼고 무라이는 자기 테이블 음식 다 먹고 옆 친구 테이블 불고기도 다 먹더군요. 대식가 ㄷㄷ해

그쪽 팀은 청국장이 일본 낫토랑 비슷해서 그런지 청국장을 좋아하더라구요. 원래 국 같은거 다 같이 먹는건 우리나라 문화라 익숙하지 않을 것 같은데 잘 먹더군요.

처음에는 어색했는데 밥 다 먹고 나니까 그래도 나름 친해진 것 같은 기분을 느꼈습니다. 되게 소소하게 재밌는 하루였습니다.

내일 좋은 성적 거두면 좋겠네요 ㅎㅎ

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

위키피디아 : 아호-코라식 알고리즘

여러 개의 패턴 검색할 때 선형시간에 패턴을 검색하게 해 주는 알고리즘입니다. IDE에서 색깔 입혀줄 때 사용할 것으로 강력하게 추정되네요.

패턴 하나는 KMP로 선형에 되는데 패턴 여러 개 있을 때 어떻게 하나 항상 궁금했었는데 이런 알고리즘이 존재하는군요.

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

화폐개혁

전국대회 예비소집 전 자기 전에 연습삼아 한 문제를 풀고 자려고 ‘화폐 개혁’이라는 문제를 선택했음.

열심히 풀다가 너무 안 풀려서 풀이를 보기로 했음.

T[i]를 ‘i를 최대 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 아래서부터 에라토스테네스의 체 방식을 이용하여 배수를 채워 나가는 Bottom-Up 방식과, T[i]를 ‘i를 최소 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 max값부터 내려오면서 그 값의 약수들을 채워나가는 Top-Down 방식의 풀이가 있었는데 Bottom-Up 방식은 글과 코드가, Top-Down 방식은 코드만 첨부되어 있었음.

Bottom-Up 방식도 잘 보면 이해할 수 있었을 것 같은데 첨부된 글이 너무 못 알아듣게 써 있어서 Top-Down 방식 코드를 보고 있었고, 마침 그 방식대로 짠 친구가 있어서 설명을 듣고 그대로 짰음. 처음에 풀이를 봤을 때는 저게 Bottom-Up 방식인지도 못 알아들었었음.

처음에는 Top-Down 방식으로 짰는데 전처리를 안 하고 그냥 \sqrt{M}까지 루프를 돌렸기 때문에 최초에는 O(MN \sqrt{M}) 정도의 시간복잡도로 마지막 테스트 케이스에서 TLE.

그래서 전처리를 이용해 소인수분해를 미리 해 두고, 계산할 때는 소수들을 이용해 약수를 직접 구하는 방식으로 코드를 고쳤지만 이번에도 마지막 테스트 케이스에서 TLE.

Top-Down 방식은 에라토스테네스를 이용하는 Bottom-Up 방식과는 다르게 약수를 구하는 과정에서 어쩔 수 없는 낭비가 생긴다는 것을 깨닫고, Bottom-Up 방식으로 다시 짜기로 함.

Bottom-Up 방식에서는 에라토스테네스 방식을 사용해서 시간복잡도가 O(MN lglg M)이 보장되기 때문에 훨씬 빠를 것이라 예측하고, 다시 짰으나 결과는 별반 다르지 않았음. 심지어 더 앞쪽에서 TLE.

뭐가 문제일까 생각하다가, 설마 아니겠지 생각하면서도 나눗셈 연산과 퍼센트 연산이 느려서 그런게 아닐까 생각하게 됨.
a/i-(a/j+a%j/i) 이 부분을 a/i/(j/i)*(j/i-1)로 고치고 j가 i의 배수라는 사실을 이용해 a/j*(j/i-1)로 고쳐서 겨우겨우 AC.

나눗셈 연산과 나머지 연산 좀 줄인걸로 속도가 세 배이상 빨라졌음. 생각한 것 보다 나눗셈과 나머지 연산이 많이 느리다는것을 느끼는 계기가 되었음.

문제 자체는 평소에 잘 접하지 못하는 새로운 형태의 dp라서 좋았던 것 같음. T[i] 정의와 dp라는것만 떠올렸으면 스스로 풀 수 있었을 것 같은데 워낙 생소한 형태의 문제라 좀 고생했던 것 같음.

전국대회에서 좋은 결과 있으면 좋겠네요.

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

일반적으로 짜는 방법은 O(N lg lg N)인데, 리스트를 사용해 O(N)으로 시간복잡도를 줄인 버전이다.

친구가 짜서 준 소스를 조금 다듬었다.

#include <cstdio>

const int MAX=1000020;

int n, next[MAX], prev[MAX];

int main(){
    int i, j;

    scanf("%d", &n);

    for(i=1; i<n+3; i++){
        next[i] = i+1;
        prev[i] = i-1;
    }

    for(i=2; i*i<=n; i=next[i]){
        for(j=i; i*j<=n; j=next[j]);
        for(j=prev[j]; j!=i; j=prev[j]){
            prev[next[i*j]] = prev[i*j];
            next[prev[i*j]] = next[i*j];
        }
        prev[next[i*i]] = prev[i*i];
        next[prev[i*i]] = next[i*i];
    }

    for(i=2; i<=n; i=next[i])
        printf("%d ", i);
}