JMK no matter what

IPSC 2010 연습

• 첫 4시간. 개시~ 라고 썼지만 결국 5시간 다했다. 작년에 3등했지만 그때 나는 이랬기 때문에 아는 문제가 없어요~ ㅋㅋㅋ -_-;;
• A1 A2 B1 B2 C1 C2 D1* D2** F1* F2 I1*** J1 J2 K1 K2 L1 으로 23점.

간단한 정리

• A (Antisort): sort and swap.
• B (Broadway): 그림을 몇개 그려보고 나니까 브로드웨이에 들어가기 전/후에는 항상 직선이어도 될 거 같단 생각이 들어서 밑져야 본전 하고 내봄.
• C (Cell): 걍 수식 파싱.. ~_~ 근데 생각하다 보니 위상정렬 한다음에 파이썬에 걍 돌리면 되네 ㅋㅋㅋ
• D (Dragon Slayer): easy 는 brute force 해서 풀고, hard 는 두 개의 sword 에 대해 케이스를 나눠서 풀었다. 하나는 증가/하나는 감소 케이스가 문제.
• E (Eyjafjallajökull): 뭐.. 이런건 시뮬레이터 짜서 돌리면 되는뎅;; 건드리지도 못했다;;
• F (Flawed Code): 원래는 랜덤으로 풀려그랬는데 그냥 손으로 고쳐서 풀었다. -_-
• G (Grid Is Good): 아이디어는 대충 알만한데 시간이 모자라서 풀지 못하였다
• I (Inside job): 몰랐는데 이지 입력은 무지 쉽더라.. -_-;; 그래서 그냥 대충 짬 ㅋ 하드는 작년에 캐노가다로 풀었네;; 라이브러리 있으니까 C++ 로 다시 짜면 좀 쉽게 짜려나
• J (Jimmy the Acting Teacher): 예제 출력 보고 구조 찍어서 맞음 ㅋ
• K (Klingon High Council Training): 적절히 변환하면 game of nim 으로 만들 수 있다.. 까진 쉽게 알았는데.. sum of three square 주어질 때 인덱스 구하기가 어려웠다. OEIS 를 열심히 뒤진 결과 공식을 알아내서.. 그 이후는 전에 풀어봤으므로 간단히 ㅋㅋ
• L (Little Stamps): 이지만 풀고.. 하드 풀겠다고 잡고 있었으나 못풀었다 orz Lucas Theorem 쓰는거 같긴 했는데 오피셜 솔루션도 비슷한거 같긴 한데.. 아 몰라몰라 ㅋㅋㅋ

카라츠바 빠른 정수 곱셈 알고리즘의 구현

A (rather naive) implementation of Karatsuba algorithm.

And yes, this could be accelerated a lot further if I represent more than one digit in each array element.

lang:cpp

// num[] 의 자릿수 올림을 처리한다.
void normalize(vector<int>& num) {
    num.push_back(0);
    // 자릿수 올림을 처리한다
    for(int i = 0; i < num.size(); i++) {       
        if(num[i] < 0) {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        }
        else {
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    if(num.back() == 0) num.pop_back();
}

// 두 긴 정수의 곱을 반환한다. 각 배열에는 각 수의 자리수가 1의 자리에서부터 시작해 저장되어 있다.
// 예: multiply({3,2,1},{6,5,4}) = 123*456 = 56088 = {8,8,0,6,5}
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1, 0);
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
            c[i+j] += a[i] * b[j];
    normalize(c);
    return c;
}

// a += b * (10^k); 를 구현한다.
void addTo(vector<int>& a, const vector<int>& b, int k) {
    a.resize(max(a.size(), b.size() + k));
    for(int i = 0; i < b.size(); i++) a[i+k] += b[i];
    normalize(a);
}

// a -= b; 를 구현한다. a >= b 를 가정한다.
void subFrom(vector<int>& a, const vector<int>& b) {
    a.resize(max(a.size(), b.size()) + 1);
    for(int i = 0; i < b.size(); i++) a[i] -= b[i];
    normalize(a);
}

// 두 긴 정수의 곱을 반환한다. 
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
    int an = a.size(), bn = b.size();
    // a 가 b 보다 짧을 경우 둘을 바꾼다
    if(an < bn) return karatsuba(b, a);
    // 기저 사례: a 나 b 가 비어 있는 경우
    if(an == 0 || bn == 0) return vector<int>();
    // 기저 사례: a 가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다.
    if(an <= 50) return multiply(a, b);

    int half = an / 2;
    // a 와 b 를 밑에서 half 자리와 나머지로 분리한다
    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
    // z2 = a1 * b1
    vector<int> z2 = karatsuba(a1, b1);
    // z0 = a0 * b0
    vector<int> z0 = karatsuba(a0, b0);
    // a0 = a0 + a1; b0 = b0 + b1
    addTo(a0, a1, 0); addTo(b0, b1, 0);
    // z1 = (a0 * b0) - z0 - z2;
    vector<int> z1 = karatsuba(a0, b0);
    subFrom(z1, z0);
    subFrom(z1, z2);
    // ret = z0 + z1 * 10^half + z2 * 10^(half*2)
    vector<int> ret;
    addTo(ret, z0, 0); 
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);
    return ret;
}

string toString(vector<int> a) {
    string ret;
    while(a.size() > 1 && a.back() == 0) a.pop_back();
    for(int i = 0; i < a.size(); i++) 
        ret += char('0' + a[a.size() - 1 - i]);
    return ret;
}

vector<int> fromString(const string& s) {
    vector<int> ret;
    for(int i = 0; i < s.size(); i++)
        ret.push_back(s[i] - '0');
    reverse(ret.begin(), ret.end());
    return ret;
}

2011-06-01

• 하염없이 흘려보낸 5월을 반성하며 6월은 다시 알차게 보내야겠다! 라고 다짐하고 시작한 하루였으나.. 일은 조금밖에 안 하고, 집정리하고, ADOM 하고 노느라 시간을 보냈다. -_-
• 방금 그레이엘븐 위저드로 그렘린 파밍하다가 \oW 두개 줍고 미친듯이 좋아하면서 와 이걸로 뭐하지 두근두근 하면서 허브 캐다가... Strength of Atlas 풀려서 overburdened 때문에 죽었다. 바닥을 뒹굴뒹굴 구르면서 소리를 질렀다 (수정이도 있는데 뭐하는 짓이었나.-_-;). 와 난 정말 병신이오 병신.
• 참고로 어제에는 그레이엘븐 위저드를 하고 있었는데.. 레드드래곤 그레이터 볼트를 slow monster 나한테 걸고 ice ball 로 쓸다가 (레벨 30이었는데 웜 세마리 잡으니까 42 됐다 -_-;), 순간 방심해서 한턴에 HP 300 깎이고 뒈졌다. 새벽에 모니터에 대고 비명을 지르고 싶었다.
• 난 왜 이러는 걸까. -_-;
• 최소한 앞으로는 노는 시간이라도 재기로 맘먹었다...
• 오늘 저녁은 보은이네+벤옹네랑 일곱이서 지오다노에서 밥먹고, 근처 새로 연 아이스크림집에서 아이스크림 먹고 수다수다. =_=

2011-05-27

• 오늘의 식사: 점심은 간단히 물만두로 때우고, 저녁엔 내가 김치찌개 끓이고 수열이가 호박 볶고 계란후라이 해서 먹었다. 으 김치찌개는 역시 돼지고기를 팍팍 넣어야..
• 오늘의 원고: 6장 RC1 냄.
• 왜일케 시간이 잘가는지 원.
• 어제는 사실 원고 하나도 안했는데.. 그건 다 입큰이 갑자기 ADOM 하고 있다고 날 말아서... 오랜만에 바바리안 해봤는데, 맨날 그레이엘븐 위저드 하다가 오키쉬 바바리안 하니 왜이리 신나던지;; 한방에 픽픽 다죽고 아싸 신난다~ 하고 피라밋 그레이브야드 워터템플까지 쓸고.. 이제 스미씽을 해봐야지 하고 조낸 노가다 하다가.. 레벨에 벽 다 파버려서 몬스터들이 계속 깝죽대는거 y 누르다가... 고르곤한테 석화당해서 죽었다. .... 나 석화로 죽어보는거 처음임 ㅠㅠㅠ ㅅㅂ 좆망 늘 새롭게 죽는 법을 배우지요

2011-05-25

• 12시쯤 일어나서 점심먹고, 쭈욱-원고. 별거 없이 쭈욱-원고. 원고. -_-
• 오늘의 식사: 점심은 수열이가 샌드위치 해줬고, 저녁엔 또 부타나베. 오늘은 참깨소스에 마늘이랑 고추기름을 많이 넣었더니 매콤하니 아주 맛있었다. 숙주는 더 듬뿍 넣어도 될 듯.
• 원고는 챕터4 RC1 릴리즈하려고 원고 빌드하는 중.. "수행 시간 어림짐작하기" 라는 절을 넣어야겠다 했는데 생각보다 엄청 오래 걸렸다. 고쳐도 고쳐도 맘에 안드는 부분이 남아있는지 원. 으으. 벌써 이번주 다갔네.
• 그 외엔 뭐 별게 없네. 오늘 시카고 날씨 완전 캐구리다. -_-; 5월 말인데.. 밖이 8도야.. 졸라추워서 난 지금 후드집업에 두꺼운츄리닝에 양말에 슬리퍼를 신고 있지........;;;;; 미쳤어 이건.. 왜 이런데 도시를 만든거야.. ㅠ.ㅠ
• 아, 그리고 책용 도메인 샀다. algobook.info. 후후
• 원고19

wikipedia convergence

Today's xkcd says, in the title tag, "Wikipedia trivia: if you take any article, click on the first link in the article text not in parentheses or italics, and then repeat, you will eventually end up at 'Philosophy'".

I tried it from the article I was reading then.. and it worked! I was so amazed so I wrote something to automate it. With BeautifulSoup's power in my hand, it's a no-brainer.

lang:py
# -*- coding: utf-8 -*-
import sys, urllib2, BeautifulSoup

def fetch(url): 
    request = urllib2.Request(url)
    request.add_header("User-Agent", "Wget/1.12")
    return urllib2.urlopen(request).read()

def get_next(soup):
    for p in soup.find("div", attrs={"id": "bodyContent"}):
        if not hasattr(p, "name") or p.name != "p": continue
        opened = 0
        for elem in p:
            if hasattr(elem, "name") and elem.name == "a" and opened == 0:
                next = elem["href"]
                if next.startswith("/"):
                    next = "http://en.wikipedia.org" + next
                return next
            elif not hasattr(elem, "name"):
                for ch in elem:
                    if ch == "(":
                        opened += 1
                    elif ch == ")":
                        opened -= 1
    return None

def explore(url):
    ret = []
    seen = set()
    while True:
        soup = BeautifulSoup.BeautifulSoup(fetch(url))
        title = soup.find("h1").string
        print "Got to", title
        ret.append(title)
        if title == "Philosophy":
            print "Reached Philosophy!"
            break
        if title in seen:
            print "Cycle detected!"
            break
        seen.add(title)
        url = get_next(soup)
        if not url:
            print "Couldn't find link!"
    return ret


seed = sys.argv[1]
print " -> ".join(explore(seed))

Yes, the code is shitty, and it doesn't hold for every page (for instance, Soviet Union falls into a cycle real quick), it's still amazing.

[3:47:38] jongman:~/Dropbox/code/python $ python wikipedia.py 

http://en.wikipedia.org/wiki/Time_complexity
Got to Time complexity
Got to Computer science
Got to Theory
Got to Ancient Greek
Got to Greek language
Got to Indo-European languages
Got to Language family
Got to Language
Got to Communication
Got to Meaning (philosophy of language)
Got to Aristotle
Got to Greeks
Got to Nation
Got to Sovereign state
Got to State (polity)
Got to Social sciences
Got to Umbrella term
Got to Subset
Got to Mathematics
Got to Quantity
Got to Property (philosophy)
Got to Modern philosophy
Got to Philosophy
Reached Philosophy!
Time complexity -> Computer science -> Theory -> Ancient Greek -> Greek language ->
 Indo-European languages -> Language family -> Language -> Communication -> 
Meaning (philosophy of language) -> Aristotle -> Greeks -> Nation -> Sovereign state -> 
State (polity) -> Social sciences -> Umbrella term -> Subset -> Mathematics -> Quantity -> 
Property (philosophy) -> Modern philosophy -> Philosophy

2011-05-24

• 바쁜 하루였다. =_=
• 아침에 일어나서 허겁지겁 씻고 나일즈로 수열이 병원 진료.. 꿀꿀이는 잘 크고 있고, 걱정했던 임신 당뇨도 별 문제 없다는 좋은 소식을 듣고 왔다. 점심으로 와퍼먹고ㅋ 집에와서 원고좀 하다가 김선생님이랑 운동. 운동 끝나고 Redfin home buying class 들으러 North & Clybourn 갔다 집에 돌아와서, 원고 좀 함. 이제 지쳐서 자야겠다 -.-;;
• 오늘의 운동은 등+이두.. 랫풀다운8 시티드로우7 원암로우35 컬 로프로 하는거;; 4 허리 굽혔다 펴는거-_- 바벨컬 17.5 해머컬 15 이렇게 했던가. 정확하진 않음
• 오늘의 원고는.. 챕터4 는 카메라레디 캔디데잇 내고 잘 수 있을줄 알았는데.. 땡! 실패! orz
• 핸드폰 개통됐다. 통화 품질은 의외로 좋던데... 하여간 가격대 성능비만으로도 후회는 없음.. ㅠ.ㅠ/
• 원고11 운동2

비교 기반 정렬 알고리즘 수행 시간의 하한

본격 책에서 잘려나간 부분 시리즈 #2 입니다. 이번에는 정렬 알고리즘 수행 시간의 하한은 인가에 대해 다룹니다. 이거는 일반적인 알고리즘이나 자료구조 수업에서 다 다루긴 하지만.. 이것도 열심히 썼는데 결국 잘라야하다니 흑흑

---

우리는 모두 줄 세우기를 좋아합니다. 인터넷 검색 결과를 최신 순서로 정렬해 보여 주는 것, 가요 프로그램에서 매주마다 음원 판매와 인터넷 투표 점수를 합쳐 1등을 뽑는 것, 고스톱 칠 때 손 안에 든 패를 순서대로 정리하는 것 등, 순서대로 줄을 세우는 것은 우리의 일상 생활과 밀접하게 관련된 문제입니다. 이렇게 중요한 문제인 만큼 정렬하는 알고리즘에 대한 연구는 꽤나 자세하게 이루어져 있는 편입니다. 영문 위키백과의 정렬 알고리즘 항목에는 관련 알고리즘이 스무 개 넘게 등재되어 있고, 이것 또한 완전한 목록이라고 할 수는 없지요.

정렬 알고리즘 수행 시간의 하한

이와 같이 많은 연구가 이루어졌지만, 정렬 알고리즘에 대한 연구는 아직 활발하게 이루어지고 있습니다. 난수를 이용해 확률적으로 더 빠른 알고리즘을 만든다거나, 입력에 정렬된 부분 수열이 존재할 경우 이를 이용하는 알고리즘¹을 만드는 것이죠. 그러나 정렬 문제는 '풀린' 문제라고 볼 수 있습니다. 정렬 알고리즘 수행 시간이 얼마나 빨라질 수 있는지에 대한 한계를 찾았고, 이 한계 속도로 동작하는 알고리즘 또한 이미 고안되었기 때문이죠.

1: 현실 세계에서는 완전한 난수 입력은 별로 없고, 부분적으로 정렬된 입력이 더 흔하기 때문에 완전한 난수 입력에 좀 더 느린 대신 부분적으로 정렬된 입력에 더 빠르게 동작하는 알고리즘들을 구현하기도 합니다. 이런 알고리즘을 적응형 알고리즘(adaptive algorithm) 이라고 부르죠. 파이썬과 자바의 표준 라이브러리에서 사용하는 팀 정렬(TimSort) 이 이의 좋은 예입니다.

이 증명은 정확하게 설명하자면 까다로우니 간략한 아이디어만 소개하겠습니다. 크기가 인 정수 배열 를 비교를 통해 정렬한다고 합시다(이 가정이 있으므로, 원소들을 서로 비교하지 않고 정렬하는 알고리즘 (카운트 정렬 등) 은 이 하한에 적용되지 않습니다). 정렬이란 다시 말해 입력된 값들을 크기에 따라 줄 세우는 방법을 찾는 문제죠. 개의 원소를 줄 세우는 방법은 모두 가지가 있기 때문에, 정렬 알고리즘의 반환 결과가 가질 수 있는 값은 가지가 됩니다. 예를 들어 이라고 하면 정렬 알고리즘의 가능한 결과값은 , , 이런 식으로 개가 있을 겁니다.

추상적으로 말해, 비교를 이용한 정렬 알고리즘들은 모두 같은 방식으로 동작합니다. 비교를 이용한 정렬 알고리즘들은 한 번에 두 개의 숫자를 선택해 그 둘의 대소 관계를 확인합니다. 그리고 그 결과와 모순되는 후보들을 목록에서 탈락시키는 것이죠. 예를 들어 인 예에서 첫 번째로 과 을 골라서 비교했다고 합시다. 만약 그 결과가 이라면 6개의 후보 중 을 포함하는 3개는 이제 답이 될 가능성이 없습니다. 정렬 알고리즘은 가능한 결과가 하나밖에 남지 않을 때까지 이 과정을 반복합니다. 따라서 정렬 알고리즘의 성능은 얼마나 똑똑하게 비교할 숫자들을 선택하는지, 그리고 얼마나 효율적으로 모순되는 후보들을 찾아내는지에 좌우된다고 할 수 있습니다.

이 알고리즘에서 비교할 숫자들을 선택할 때 중요한 것은 이 비교 결과가 남은 후보들을 어떻게 반으로 나누는가입니다. 예를 들어 남은 후보들이 전부 를 포함한다면 과 를 비교하는 것은 의미가 없지요. 그럼 10억개의 후보들이 남아 있는데 그 중 10개는 를 포함하고, 나머지는 를 포함한다고 합시다. 이 때 과 를 비교하는 것이 좋은 선택일까요? 아마도 아닐 겁니다. 실제 비교 결과에서 이 더 작다면야 좋겠지만, 가 더 작다면 우리는 후보의 개수도 얼마 줄이지 못한 채 비교만 한 번 낭비한 셈이 되기 때문이지요. 이쯤해서 눈치채셨겠지만, 최악의 경우에도 비교의 회수를 최소화하기 위해서는 항상 남은 후보의 수를 가능한 절반에 가깝게 줄이는 비교를 하는 것이 좋습니다.

이와 같은 선택을 통해, 비교를 한 번 할 때마다 후보의 수를 절반으로 줄일 수 있다고 합시다. 이 때 필요한 비교의 횟수는 후보의 수 에 로그를 취한 결과인 가 된다는 것을 쉽게 알 수 있습니다. 수학을 약간 이용하면 이라는 모호한 숫자를 좀 더 알기 쉽게 바꿀 수 있습니다. 다음과 같이 풀어 써 봅시다.

이 때 , , , 들은 모두 과 같거나 그보다 큰 숫자들이지요. 따라서 이 식을 다음과 같이 정리할 수 있습니다.

라는 결론을 얻을 수 있지요. 따라서 비교 기반 정렬이 필요로 하는 최소 비교의 수는 이상이라는 것을 알 수 있습니다. 이만큼 비교를 하려면 최소한 이만큼 반복문을 수행해야 할 테니 정렬 알고리즘의 수행 시간은 항상 이거나 더 커야 하지요. 따라서 정렬 알고리즘의 수행 시간의 하한은 이 됩니다(붙어 있던 는 어디 갔냐고요? 1.7절에서는 우리들은 앞으로 상수들은 멋있게 신경쓰지 않기로 한 합의에 대해서 설명합니다.).

수행 시간 하한의 의미

사실 수행 시간의 하한은 누구나 발견할 수 있습니다. 당장 제가 벌떡 일어나 "정렬하려면 최소한 수를 다 읽어들이긴 해야 한다. 따라서 정렬 문제의 수행 시간의 하한은 이다!" 라고 외칠 수 있고, 실제로 맞는 말이니까 별로 태클 걸 사람도 없을 겁니다. 이 최소 수행 시간이란 것이 대체 무슨 의미가 있을까요?

알고리즘의 수행 시간을 계산하는 한 가지 방법은 이 시간의 상한과 하한을 찾아내는 것입니다. 예를 들어 인간이 100m 를 달릴 수 있는 최소 시간 의 값을 찾아내고 싶다고 합시다. 현재의 세계 기록 9.58초는 이 값의 상한입니다. 이미 9.58초에 100m 를 달린 사람이 있기 때문에, "최소 시간"인 가 이 값보다 크다면 모순이 되기 때문입니다. 반면 인간이 1초안에 100m 를 달릴 수는 없다! 라는 주장은 가 1 보다 작아질 수는 없다는 뜻이기 때문에 의 하한을 나타냅니다. 그런데 인간이 1초 안에 100미터를 달릴 수 없다는 것은 다들 알고 있고, 때문에 너무 작은 하한은 아무런 의미가 없습니다. 따라서 우리는 항상 하한을 끌어올리기 위해 힘씁니다. 반대로 100m 를 달리는 선수들은 가능한 한 빨리 달려서 그 상한을 끌어내리기 위해 힘쓰지요. 이 두 숫자가 만났을 때 100m 문제가 풀렸다! 고 우리는 주장할 수 있게 되는 겁니다. 정렬에 대해서도 마찬가지입니다. 정렬 문제는 해결되었다! 라고 주장할 수 있는 이유는 우리가 찾아낸 수행 시간의 하한에 해당하는 알고리즘이 고안되었기 때문이지요. 가장 유명한 정렬 알고리즘인 퀵 정렬이나 힙 정렬 등이 이 하한에 해당하는 알고리즘의 예입니다.

2011-05-23

• 아침에 일어나니 수정이가 야채볶음이랑 계란말이 해둬서 먹었다. 와 처제가 밥도해줘 >.< 점심은 냉동실에 있던 루말나티 피자 먹고, 저녁엔 오랜만에 해먹는 삼겹살두부두루치기. 이것이 고단백 저탄수화물 메뉴?
• 딴건 한거 없고 원고.. 3챕터 카메라레디 버전 만드느라 삽질. ~_~ 아.. 더 열심히 해야 되는데 시간이 왤케 빨리 가나 ㅠㅠㅠㅠㅠㅠ 젠장
• 김선생님이랑 하체운동. 스쿼트115, 런지25 하고 나니 토할거 같길래 그 이후로는 살살 했다. -_-; 저번에도 하체운동하다가 맛이 가서 집에 가서 한시간 누워 있었던 기억이 나니 더럭 겁이 나더라능 -_-;
• 원고14 운동2

2011년 5월 3주 주간리뷰

• 주간리뷰 오랜만에 쓴다. 아오 졸래 반성해야지.
• 그래도 지난주엔 로그는 안빼먹고 썼네.. 가 아니라 18일에 빼먹었네. 이날 뭐했담.
• 원고12+10+22+15+7+1=67
• 운동은 2번감. needs improvement!
• 원고는 교정 페이즈에 돌입

2011-05-22

• 빼먹고 안썼었네 반성 orz 요즘 일을 안하면 로그를 안쓰게 되는 버릇이 생겨갖고.
• 반성합니다. 열심히 써야지. 하지만 원고는 하나밖에 안함 ㅋㅋㅋ
• 뭐했나.. 하면 아울렛에 다녀왔다. 꿀꿀이 옷도 사고, 나 겨울 잠바도 하나 더 사고, 코렐에서 밥그릇 국그릇도 사고 (요즘 좀 깨먹어서 부족했다 ㅋ) 위스컨신에 있는 아울렛이었는데, 소비세가 싸!! 완전좋음 ㅋ
• 날씨 구리대서 아 놔 어떡해.. 하면서 갔는데 날씨 매우 좋았다. -_-;
• 골프로드에 있는 장충동왕족발ㅋㅋㅋㅋㅋ에서 감자탕ㅋㅋㅋㅋ을 먹고 아씨에서 장까지 보고 집에 오니 10시였다. -_- 나가수 보고 잤다..
• 원고1

2011-05-21

• 오늘은 다시 늦잠자고, 점심엔 호밀빵 토스트에 버터랑 잼 발라 먹고, 저녁엔 반년만에 시카고 놀러온 민재형이랑, 유진이형이랑 조선옥. 유진이형+민재형 개그가 미친듯이 터져서 한참 웃다가 집에 옴. 집에 와서는 수정이랑 셋이 모노폴리. 이거 은근히 잔인한 게임이다.
• 원고는 챕터3 리팩토링하다가 시간이 갔네.. 사실 별로 많이못했다.
• GCJ R1B 문제 보고 한 사십분 풀다가 C 번 풀기 귀찮아서 GG.. -_-;
• 원고7 연습2

정수 연산에서 오버플로우가 발생하는지 확인하기

How to detect overflows in integral operations

원고 카메라 레디 버전을 만들면서, 정말 중요하다고 느끼지 않는 부분을 팍팍 잘라낼 예정이다. 그 첫 번째 타자로, "변수 범위의 이해" 절의 일부를 잘라내게 되었다. 그래도 열심히 썼는데 가슴이 아파서 블로그에 옮겨 본다.

---

수학적으로는 아무 문제 없는 코드에서도 오버플로우는 난데없이 발목을 잡기 때문에, 어디서 오버플로우가 발생할 수 있는지 알고 경계하는 것이 좋습니다. 각 사칙 연산 별로 언제 오버플로우가 일어나는지를 간단히 정리해 보겠습니다. 우선 현재 사용하는 정수형의 최소 값을 , 최대 값을 이라고 부르기로 합시다. 만약 현재 사용하는 정수형이 부호 있는 32비트 정수라면 , 이 되겠습니다.

눈치채셨겠지만 가장 작은 수와 가장 큰 수는 0 을 사이에 놓고 대칭이 아닙니다. 정수형이 표현할 수 있는 음수와 양수의 개수가 같으려면 0 까지 포함해 전부 홀수개의 가짓수가 되는데, 비트로 표현할 수 있는 정수의 가짓수 은 언제나 짝수이기 때문이죠. 이와 같은 특성은 대부분의 컴퓨터들이 2의 보수(Two's Complement) 라는 방법을 사용해 부호 있는 정수를 표현하기 때문입니다. 자세한 것은 위키백과 페이지 (http://en.wikipedia.org/wiki/Two's_complement) 를 참조하세요..

덧셈 뺄셈

덧셈 뺄셈으로 정수형 오버플로우가 나려면 실제로 꽤 큰 숫자를 다뤄야만 합니다. 큰 입력 제한 숫자들은 어느 정도 산술 오버플로우에 대한 경계심을 불러일으키기 때문에, 덧셈 뺄셈을 통한 오버플로우는 자주 등장하진 않습니다. 를 계산할 때

• 가 양수라면, 를 더했을 때 오버플로우가 나지 않을 수 있는 가장 큰 값은 입니다. 가 이 값보다 크다면 오버플로우가 발생하겠죠.
• 가 음수라면, 를 더했을 때 오버플로우가 나지 않을 수 있는 가장 작은 값은 입니다. 가 이 값보다 작다면 오버플로우가 발생합니다.

여기에서 유의할 만한 것은 양수와 음수를 더할 때는 오버플로우가 절대로 나지 않는다는 것입니다. (만약 양수가 부호 없는 정수형에 저장되어 있다면 이야기가 달라집니다. 다음 변수형의 프로모션 항목을 참조하세요.)

곱셈

부호 있는 32비트 정수를 사용한다고 합시다. 이 때 표현할 수 있는 최대의 수는 인데, 이 때 안심하고 곱셈할 수 있는 숫자는 기껏해야 네 자리 수 정도입니다. 다섯 자리 수를 두 개 곱하면 32비트 정수의 표현 범위를 쉽게 넘어갈 수 있지요. 이니, 이거든요. 그러니 작은 숫자를 다루고 있다고 방심할 때도 곱셈에 의한 오버플로우는 발생할 수 있습니다. 엄밀히 말해 를 계산할 때

• 두 수의 부호가 같다면 를 곱했을 때 오버플로우가 나지 않을 수 있는 가장 큰 값은 입니다 가 이 값보다 크다면 오버플로우가 발생합니다.
• 두 수의 부호가 다르다면 를 곱했을 때 오버플로우가 나지 않을 수 있는 가장 큰 값은 입니다. 가 이 값보다 크다면 오버플로우가 발생합니다.

나눗셈

다행히도 정수의 나눗셈에서는 오버플로우가 발생할 일이 없습니다. 하지만 오버플로우만큼이나 무서운 0 으로의 나눗셈이 있기 때문에, 나눗셈을 쓸 때는 오른쪽에 0 이 올 일이 절대 없는지를 한 번쯤 마음 속으로 확인하면 좋습니다.

단항 연산자

앞의 주석에서도 간단히 언급했지만 부호 있는 정수형이 표현할 수 있는 범위는 0 을 중심으로 대칭이 아닙니다. 은 표현할 수 없지만, 은 표현할 수 있지요. 따라서 정수 변수 에 표현할 수 있는 최소 값이 들어 있으면, 는 오버플로우가 아니지만 에서는 오버플로우가 발생하는 경천동지할 일이 발생할 수도 있습니다. 예를 들어,

lang:cpp
int c = INT_MIN; // -2^31
if(c == -c) cout << “True” << endl;

은 True 를 출력합니다.

덧셈과 곱셈에 대해 오버플로우가 발생하는 경우를 수식으로 나열한 까닭은, 이와 같은 판단을 프로그램 상에서 해야 할 일이 종종 있기 때문입니다. 예를 들어 가 어떤 숫자 보다 큰지 판단하고 싶을 때가 있습니다. 물론 그냥 곱하고 비교해 보면 되겠지만, 에서 오버플로우가 난다면 이와 같은 비교를 쉽게 할 수 없습니다. 이 때 와 를 비교한다면 안전하게 오버플로우 없이 판단할 수 있습니다.

수정: yongwoon 님의 커멘트에 여기에서 캐치하지 못한 점이 몇 가지 있으니 꼭 읽어보세요.

2011-05-20

• 한 열시쯤 일어났나.. 수열이 배고프대서 비몽사몽에 두부조림해서 늦은 아침 먹고.. 원고 하다가 뒤늦게 점심으로 짜파게티 먹었다. ㅎㅎ 원고하다가 저녁에 코드잼 R1A 있어서 그거 하고, 챕터2 리팩토링 좀더 하다가 이시간. 이틀 연속 잠을 6시간 잤는데 별로 안피곤하다. 대신 집중은 안되네. ㅋㅋ
• 원고는 챕터1 카메라레디 버전 냈고, 챕터2 리팩토링중. 역시 이 부분이 고칠 거리가 많았다! -_- 우선 다음 주에 최대한 많이 교정으로 집어넣는게 목표인데, 챕터 2 3 은 아직 남겨둔 부분이 많아서 여기에 시간을 쓰긴 어려울 것 같다. 주말 중에는 이미 어느 정도 형태를 다 갖춘 3부-4부 챕터들을 최대한 많이 카메라 레디 버전으로 낼 생각이다. 그 다음 주에 나머지 챕터들 마무리해서 교정 올리고.. 뭐 이런 식.
• 코드잼 R1A 는.. 뭔가 좀 어영부영 풀었는데 어케 어케 되어서 13등했다.;
• 아 재밌는건 B에서 각 단어를 각 문자의 위치를 표현하는 비트마스크 목록으로 표현한 뒤 이걸 트라이에 넣어서 풀었는데.. 이지 풀고 하드 테스트 케이스 한개 만들어서 돌려보니까 약 170초.. 테스트 케이스 10개니까 1700초고, 코어 4개 나눠야 돌려야 간신히 돌아갈 거 같아서 영 불안했다. 그래서 pypy 를 받아서 돌렸지요! 시간이 38초로 줄어들었다. 실제로는 케이스 10개 다 푸는 데 싱글코어로 3분밖에 안걸리더라. 와와 pypy 만세입니다.
• 코드잼5 원고15

헐 JM 은 모다??

헐퀴