The Way

세그먼트 트리는 그냥 일반 알고리즘 수업만 들은 사람이랑 PS를 한다는 사람을 구분짓는 가장 대표적인 알고리즘이 아닐까 싶다. (CLRS 책에 안나와서 그러려나) 인터넷에 쳐보면 그야말로 넘쳐날 정도의 세그먼트 트리 글이 있지만, 아주 쉬운 구현을 발견해서 이를 포함해서 정리 겸 써본다.세그먼트 트리는 기본적으로 i) 구간에 대한 정보 쿼리, ii) 구간을 한번에 업데이트 시키기 두 가지에 아주 적합한 자료구조이다. 세부적으로 약간 차이가 있지만, 크게 3가지 타입이 있을 것 같다. i) 단일 업데이트, 구간 쿼리업데이트가 일어날 때는 하나의 원소만 변경되고, 쿼리는 구간에 대해서 묻는 질의이다.대표적으로 https://www.acmicpc.net/problem/2042과 같은 문제가 있다. 대표적인 세..

둘이서 베스킨라빈스 31 게임을 해본 사람이 있는가?다들 알다시피, 베스킨라빈스 31은 1부터 시작해 숫자를 최대 3개씩 부를 수 있고, 31을 먼저 외치는 사람이 지며, 먼저 시작한 사람에게 필승 전략이 존재한다. 왜 그런지 게임이 끝나는 상황부터 거꾸로 되돌아가보자.베스킨라빈스 31 게임은 30을 말하는 사람이 무조건 이기게 된다.30을 말하려면, 26을 외쳐야 한다. 26을 외치면, 다음사람이 어떤 수를 외치든 (4 - 외친수)만큼의 수를 말하면, 30을 만들 수 있기 때문이다. 즉, 26을 외치는 사람이 필승한다.반복적으로 26을 외치려면 22를 외쳐야 하고, 18, 14, 10, 6, 2...까지 간다. 따라서, 먼저 시작한 사람이 1, 2를 외치기만 하면 이미 게임은 끝난 상태인 것이다. 이러..

요약: 몫은 양수 나눗셈 기준으로 부호만 맞추어주면 되고, (나누는 두 수의 부호가 같으면 몫이 양수, 다르면 몫이 음수) 나머지는 위에서 구한 몫으로, $a = bq + r$를 만족하는 값이 된다. -------------------------------------------------- 나눗셈의 몫과 나머지는 무엇일까? 일반적으로 통용되는 정의를 따져보면, 정수 a를 0이 아닌 정수 b로 나누었을때, $a = bq + r\;(0 \le r < |b|)$를 만족하는 수 q가 몫이고, r이 나머지이다. 이는 명백해보이지만, 음수가 들어가면 약간 애매해진다. 예를 들어서 -7을 3으로 나누면 몫과 나머지는 무엇일까? 정의에 따르면, $-7 = 3\times(-3) + 2\;(0 \le 2 < |3|)$이므..

추상대수학 시간에 배운 소수판정법인데, 아주 유용하여 기록해놓는다. Miller-Rabin 소수 판별법은 확률에 의존하는 소수판정법인데, 라그랑주 정리를 이용한다. 라그랑주 정리는 p가 소수이면, $f(x) \equiv 0 ( \text{mod}\:p)$는 최대 $deg(f(x))$개의 incongruent solution을 가진다는 정리이다. 라그랑주 정리에 따르면, $x^2 \equiv 1 ( \text{mod}\: p)$는 최대 두 개의 해를 가진다. 그런데 우리는 두 가지의 자명해를 알고있다. 바로 $\pm1$이다. (단, p > 2라 하자) 따라서, 만약 자명해가 아닌 $x^2 \equiv 1 ( \text{mod}\: p)$를 만족하는 해를 발견한다면, p는 소수가 아니라는 것을 알 수 있다...

운영체제 프로젝트 1은 스도쿠 푸는 프로그램을 작성하는 과제였다. 운영체제 수업에서 왜 스도쿠를 푸는지는 잘 모르겠으나.. 프로젝트를 하면서 많은 것을 배우게 되었으니 정리해본다. 스도쿠는 단 한 가지의 정답만 가져야 한다는 있다는 말도 있는데, 꼭 필요한 조건은 아니라고 생각한다. 물론 손으로 풀 때 답이 여러가지이면 굉장히 열받겠지만, 진정한 프로그램이면 어떠한 경우에서도 해답을 찾아낼 수 있어야 한다고 생각한다. https://www.acmicpc.net/problem/2580 참고로 백준 스도쿠 문제의 테스트 케이스 중에도 스도쿠 판을 채우는 방법이 여럿인 경우가 있다고 명시되어 있다. 답이 유일한 스도쿠를 찾는다면, http://staffhome.ecm.uwa.edu.au/~00013890/su..

C에는 온갖 입출력 함수들이 많다. 당장 출력만 해도 putchar, putc, fputc, puts, fputs, fwrite, printf, fprintf의 8개 정도 함수를 손에 꼽을 수 있을 것 같다. 함수들의 출력속도에는 상당한 차이가 있다. 그것도 꽤 많은 차이가 난다. https://www.acmicpc.net/blog/view/57 백준 블로그인데, 여기에 함수들의 출력 속도 차이가 적혀있다. fwrite가 가장 빠르다고 나온다. 저 함수들 중 몇 개가 비어있기 때문에, 마저 채우는 느낌에서 속도를 측정해보았다. 백준에서는 숫자를 1부터 1000만까지 출력하였지만, 약간 특수한 상황이므로 이번 테스트에서는 더 본질적인 메모리에 있는 문자열을 그대로 출력하기를 해 보았다. 구체적인 테스트 방..

컴파일을 하기 위해서는 보통 gcc를 사용한다. gcc의 컴파일 과정은 다음과 같은 순서로 이루어지는데, a.c (작성한 코드)→ a.i (#define이나 #include 같은 것을 처리함)→ a.s (어셈블리어로 번역)→ a.o (어셈블리 파일을 오브젝트 파일로 번역)→ a.out (오브젝트 파일을 linking까지 완료) 중간 단계까지만 진행하는 것도 가능한데,-E 옵션을 주면 전처리만, -S 옵션을 주면 어셈블리어로, -c 옵션을 주면 오브젝트 파일까지만 완료할 수 있다. 1) 어셈블리어먼저 어셈블리어로 번역되는 과정에 주목해보자. 어셈블리어는 파고들자만 한도끝도 없을 정도로 복잡하지만, 대표적으로 다음과 같은 명령들은 알아둘 만 하다. mov src des: src를 des로 복사 add, su..

요즘 운영체제 수업을 듣는다. 작년 이맘때에도 들었지만 중간에 휴학을 하는 바람에 다시 듣는다.컴퓨터공학과에서 운영체제는 보통 3학년 1학기에 듣는 듯 하다. 막학기가 되어서야 듣는 나는 그만큼 기본기가 부족하다는 뜻이다. 다행히 존경스런 교수님이 정말 세세히 알려주셔서 감사한 마음으로 기본기를 쌓을 수 있다. 실습은 항상 1등으로 풀고 나가지만 여기서 만족하지 않고 더 열심히 해나가야겠다. 아무쪼록, 실습 내용을 앞으로는 그날그날 간단히 정리를 해보려고 한다. 친숙하지만, 그 속에 많은 유용한 정보를 담고 있을 수 있다. 가장 첫 번째는 비트 연산이다. 컴퓨터는 태생적으로 0과 1로밖에 데이터를 저장하지 못하기 때문에, 이진법을 필연적으로 사용할 수밖에 없다.컴파일러마다 약간 차이가 있긴 하지만 cha..

이 장에서는 다양한 적분기법들을 배운다.적분이라는게 사실.. 미분처럼 그리 자유롭게 되는 것이 아니라 약간만 형태가 복잡해져도 각종 트릭을 써서 구해야하고, 또 그마저도 못 구하는 경우도 많다.이 과정에서 굉장히 천재적인 아이디어가 많이 나온다. 그저 감탄만 하면서 7장을 마쳤다. 7장에 나온 내용은 사실 다 알 필요가 없다고 생각한다. 우리에겐 천재들이 만들어놓은 wolfram alpha가 있기 때문에..그래도 아이디어에 감탄하면서 한번 쭉 풀 가치는 충분하다. 부분적분가장 기본적인 형태. 곱의 미분을 거꾸로하면 유도된다.$\int{f(x)g'(x)}dx = f(x)g(x) - \int{f'(x)g(x)}dx$ f(x) 하나는 미분을 반복했을 때 점차 소거, g(x)는 적분을 반복할 때 그리 복잡해지지..

자연상수 e는 경이로운 숫자이다. e는 다양한 곳에서 등장하는데, 예컨데 $\lim_{n\to \infty} (1 + \frac{1}{n})^n = e$$\lim_{n\to \infty} \sum_{k = 0}^{n}\frac{1}{k!} = e$ 등이 있다. 이 장에서는 적분에서 출발하여 e를 정의하고 또 다양한 쌍곡선함수들을 정의한다. 자연로그함수의 정의 자연로그함수 $\ln x$는 다음과 같이 정의한다. $\ln x = \int_{1}^{x} {\frac{1}{t}} dt$ e의 정의e는 다음을 만족하는 수이다.$\int_{1}^{e} {\frac{1}{t}} dt = 1$ exp(x)의 정의$\exp(x) = \ln^{-1} x$ 사실 다 돌고도는 성질들이라 큰 차이는 없지만, 이렇게 정의하였을 ..