아무 말

\(O\)-표기 \(O\)-표기는 가장 흔하게 볼 수 있는 점근적 표기법입니다. 간단하게 말해 \(O\)-표기는 함수의 점근적 상한을 결정짓는 표기입니다. \(c g(n)\)이 특정한 상수 \(n_0\)보다 큰 모든 \(n\)에 대해 \(f(n)\)보다 크기만 하다면, \(f(n)\)을 \(O(g(n))\)으로 표기할 수 있습니다. \(O\)-표기가 많이 사용되는 이유 또한 이러한 특성 때문인데, Problem Solving을 할 경우에 특정 문제에 대해 적용한 풀이가 문제에서 주어진 시간제한을 넘어서는지 아닌지를 나타낼 수 있기 때문입니다. \(O\)-표기를 함수의 집합으로 나타내면 아래와 같습니다. \(O(g(n))\ =\ \{ f(n)\) : 모든 \( n \geqslant n_0 \) 에 대해 \..

점근적 표기 점근적 표기는 함수의 증가 양상을 점근적으로 표현하는 방법입니다. 점근적인 증가 양상을 나타내기 때문에, 함수의 각 변수에 대한 발산 속도가 가장 큰 항을 제외한 나머지와 모든 상수를 무시하여 나타낼 수 있습니다. \(\Theta\)-표기 \(\Theta\)-표기는 다음을 의미합니다. \(\Theta \left( g \left( n \right) \right) \ =\ \{ f \left( n\right) \ : \)모든\( n \geqslant n_0\)에 대해 \( 0 \leqslant c_{1}g\left( n \right) \leqslant f \left( n\right) \leqslant c_{2}g\left( n \right) \) 인 양의 상수\( c_{1}\),\( c_{2}\..

교과서나 인터넷의 블로그 등을 보면, (혹인 계산기를 보면) "mod"라고 적힌 것을 찾아볼 수 있습니다. 정의 모듈러 산술(modulo arithmetic, 또는 합동 산술)은 정수의 합과 곱을 나머지(Remainder)에 대해 정의하는 방법입니다. 이와 달리 계산기에서 찾을 수 있는 모듈러 연산(modulo operation)은 어떤 두 정수가 주어졌을 때, 한 정수로 다른 정수를 나눈 나머지를 반환하는 연산입니다. (컴퓨팅을 기준으로) 일반적으로, \(a\)를 \(b\)로 나눈 나머지를 \(a\ mod\ b\)라 표기합니다. 모듈러의 사칙연산 초등학교 교육과정에서 곱셈, 나눗셈, 덧셈, 뺄셈을 배웠으며, 고등학교 교육과정에서 행렬을 공부할 때 까지도, 새로운 개념과 연산을 배울 때면, 항상 이러한 ..

보호되어 있는 글입니다.

인접 행렬 인접 행렬(Adjacency matrix) 그래프를 나타내기 위한 방법 중 하나로, 다른 방법으로는 인접 리스트(Adjacency list)가 있습니다. 인접 행렬의 \((i,j)\) 항은 정점 \(i\)로 부터 \(j\)로 뻗어 나가는 간선의 개수입니다. 왼쪽의 그래프와 인접 행렬을 보면 알 수 있듯이, 무향 그래프에서의 인접 행렬은 대칭 행렬입니다. 이에 반해서, 유향 그래프의 인접 행렬은 대칭 행렬이 아닐 수 있습니다. (모든 간선에 대해 그 간선의 역방향 간선이 존재한다면, 인접 행렬이 대칭 행렬이 된다.) 인접 행렬의 유명한 성질 중 하나는 행렬의 n승의 항이 정점 i에서 j로의 n개의 간선을 이용하는 보행의 수입니다. 이는 무향 그래프이든 유향 그래프이든 관계없이 성립하게 됩니다. ..

그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어져 있습니다. 조금 더 직관적으로는 점과 그 점 사이를 잇는 선분으로 이루어진 그림이라고 할 수 있겠습니다. 참고로, 정점은 꼭짓점이나, 노드(Node)라고 부르기도 합니다. 간단하게 용어를 정리하자면 정점(Vertex) 그래프의 정점 간선(Edge) 그래프의 두 정점을 잇는 간선 루프(Loop) 하나의 정점만을 연결하는 간선 보행(Walk) 정점과 간선을 이용하여 나타낸 열. 이때, 정점과 정점 사이에 나오는 간선은 두 정점을 연결한다. 보행에서 시작하는 정점과 끝나는 정점이 같을 경우, 이 보행은 닫혀있으며, "닫힌 보행(Closed Walk)"이라고 한다. 트레일(Trail) 간선이 중복되지 않는 보행 경로(Path) 정점이 중복..