아무 말

점근적 표기 점근적 표기는 함수의 증가 양상을 점근적으로 표현하는 방법입니다. 점근적인 증가 양상을 나타내기 때문에, 함수의 각 변수에 대한 발산 속도가 가장 큰 항을 제외한 나머지와 모든 상수를 무시하여 나타낼 수 있습니다. \(\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) 정점이 중복..

백준의 큰 수 연산 시리즈입니다. 이상하게도 큰 수의 나눗셈이 필요한 문제는 따로 등록되어 있다. 큰 수의 연산을 해야 하는 시리즈인 만큼 함께 다루겠다. 특별히 교육적이거나 한 내용은 아니므로 심심할 때 재미 삼아 풀어보길 바란다. * A+B 시리즈의 문제의 경우, 큰 수의 연산을 하기 위한 노력을 필요로 하는 문제들이 아니었으므로 다루지 않겠다. A/B https://www.acmicpc.net/workbook/view/6546 문제집: A/B (시리즈) www.acmicpc.net 풀이 1008번: A/B 그냥 A/B를 출력한다. 15792번: A/B -2 정수 부분을 구해주고, 소수 부분을 따로 구해준다. 16428번: A/B -3 케이스를 적당히 잘 쪼개면 된다. 문제에 나온 식을 만족하는 값을..

들어가기에 앞서.. 단순히 빠른 정렬 방법이 아니라, 특정 상황에서 좋은 정렬법에 대해 설명하고자 한다. BOJ의 '수 정렬하기(시리즈)'의 문제들을 통해 여러 정렬의 방법들을 알아보고자 한다. 본론 2750번: 수 정렬하기는 다루지 않도록 하겠다. 먼저, 10989번: 수 정렬하기 3을 보자. 딱 봐도 Counting Sort의 냄새가 난다. 시간 복잡도는 수의 범위의 크기가 T일 때, O(T+N)이다. Counting Sort는 정렬하고자 하는 수를 배열의 index로 생각하고 배열에서 Count 한 뒤 Count 한 횟수만큼 출력하는 것으로 이루어진다. Counting Sort를 모르는 사람은 많지 않을 것으로 생각한다. 이 Counting Sort의 단점은 수의 범위가 클 때 처리하기 어렵다는 것..

동적 계획법(dynamic programming)은 부분 문제의 해를 결합해 문제를 해결한다. 동적 계획법은 부분 문제가 서로 중복될 때 적용할 수 있다. 동적계획법을 이용하면 모든 부분 문제를 한 번만 풀어 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다. 동정 계획법 알고리즘을 개발할 때는 다음 4단계를 따른다. 최적해의 구조의 특징을 찾는다. 최적해의 값을 재귀적으로 정의한다. 최적해의 값을 일반적으로 bottom-up 방법으로 계산한다. 계산나된 정보들로부터 최적해를 구성한다. 위의 내용이 Introduction to Alogirhtm 에 수록되어 있는 내용이다. 위 내용을 읽고 생각해보면, 동적 계획법은 각 부분에 대한 값을 계산하고 저장해두며, 필요할..

https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M( www.acmicpc.net 풀이를 위한 발상 한 정점을 루트로 하는 트리에서 다른 두 정점의 LCA를 찾아야 한다. 조금 생각을 해보면, 이때의 LCA는 세 정점의 접합점이라는 것을 알 수 있다. 조금 더 구체적으로 표현하자면 다음과 같다. 한 정점으로 트리를 분할했을 때, 정점 r, u, v는 모두 서로 다른 서브 트리에 존재할 수 있게 하는 정점. 이를 토대로 생각하면, 아무 노드나 잡..

21756번: 지우개 풀이 진짜 진짜.. 그냥 시뮬레이션 돌리자. 소스코드 #include using namespace std; int A[103]; int main(){ int N,ans; scanf("%d",&N); for(int i=1;i