남남서의 블로그

1.리눅스의 경우, 기본 쉘이 xterm으로 되어있는 경우가 있는데, gnome-terminal로 교체하면 훨씬 편하다. Settings → Environment → (General Settings) → Terminal to launch console programs:gnome-terminal --disable-factory -t $TITLE -x 2.기본 폰트 설정을 만져준다. KOI에서 사용하는 환경의 경우, 기본 폰트가 Monospace로 되어있는데, 놀랍게도 이는 고정폭이 아니다. Ubuntu Mono 등으로 바꾸자. 또한 Strip trailing blanks 옵션은, 저장 시 각 행마다 뒤에 남는 공백을 지워버린다. 나는 습관적으로 저장하다 보니, 이 옵션을 끄게 된다. 3.행 번호를 표시하는..

(cms github; cms/server/static/cws_style.css#L525) before hover : RGB(153, 255, 153), RGBA(0, 255, 0, 0.4), HSLA(120˚ 혹은 85, 100%, 50%, 0.4)on hover : RGB(127, 255, 127), RGBA(0, 255, 0, 0.5), HSLA(120˚ 혹은 85, 100%, 50%, 0.5)

다항식 찾기 (n+1)개의 점, 즉 $(x_i, y_i)$의 순서쌍이 (n+1)개 주어지면, 이 n개의 점을 모두 지나는 다항식을 하나 찾을 수 있다. 즉 $P(x_i) = y_i$를 모두 만족하는 $P(x)$를 찾을 수 있다. (일단 각각의 $x_i$는 모두 다르다고 하자.) 예를 들어 (1, 1)과 (2, 3)을 지나는 다항식은 $f(x)=2x-1$도 있고, $g(x)=x^2-x+1$도 있다. 이런 다항식은 여러 가지가 있고, 무한히 많다. 그런데 사실은, 그중 차수가 가장 낮은 건 n차이고, 게다가 이때의 n차 다항식은 무려 유일하다. 다항식을 왜 찾을까? ― 다항식 곱셈 문제 잠깐 다른 얘기를 해본다. 두 다항식의 곱을 계산하는 문제를 생각하자. 예를 들면 $(x^2 + x + 3)$과 $(x -..

한 쌍의 정점을 잇는 간선은 최대 하나이고(no parallel edges),모든 정점을 포함하는 매칭이 존재하는 이분그래프 G=(L, R, E)가 있다고 하자."이 그래프의 최대 매칭이 유일하다면 degree가 1인 정점이 항상 존재한다."에 대해 참/거짓을 밝히고자 한다. 모든 정점을 포함하는 매칭이 존재하므로 모든 정점의 degree는 1 이상이다.G=(L,R,E)의 모든 정점이 degree가 2 이상이라고 하자.여기서 서로 다른 매칭이 두 개 이상 존재한다는 것을 보이자. alternating path와 비슷한, 'alternating cycle'을 생각하자.alternating cycle이란, 그 간선들이 '매칭된 간선'과 '매칭되지 않은 간선'을 번갈아가는 사이클이다.예)1-2 x 3-4이런 ..

Invariance Principle.어떤 문제에서, 어떤 연산을 아무리 적용해도 1) 변하지 않는 값이 있거나(→불변량, I) 2) 일정한 규칙에 의해 순환하는 값이 있거나,3) 일정한 규칙(단조증가, ...)에 의해 발산하는 값이 있다이런 경우에 적용할 수 있다.특히 이런 불변량은 mod N이 통하는 경우가 많다. 그중에서도 대표적으로 홀짝성(mod 2). 예제를 보자. 1. 탁자 위에 하얀 칩, 검은 칩, 빨간 칩이 각각 a,b,c,개씩 있다. 한 번에 서로 다른 색깔의 칩 두 개를 선택해서, 그 두 개를 버리고 나머지 색깔의 칩 한 개를 어디선가 가져오자.1 - 1) 칩 하나만 남을 경우, 그 칩의 색깔은 (a,b,c)에 대해 한 가지만 존재함을 보여라.(즉 중간에 어떤 칩을 고르든 상관이 없다)..

$N$개의 숫자가 늘어서 있다. L번째 숫자부터 R번째 숫자까지의 합을 구하라는 질문이 여러 개 들어올 때, 각각을 모두 빠르게 구할 수 있을까? 2018/07/27 - [알고리즘 문제풀기/# 자료구조] - 구간의 합 구하기prefix sum 기법을 사용하면 이 "구간의 합 구하기" 문제를 빠르게 풀 수 있다. 또한, 어떤 문제에서는 prefix sum을 구해보면 생각하지 못했던 성질이 나타나서, 그게 문제를 푸는 열쇠가 되기도 한다. 아예 prefix sum 값에 관한 문제가 나오기도 한다. prefix sum은 간단하지만 중요한 개념이다. 그래서 도대체 그 prefix sum이란게 무엇인가 하면, 다음과 같다. $a_1$부터 $a_n$까지의 $n$개의 숫자가 늘어서 있을 때, prefix sum 배열..