블로그 이사 중입니다 >> gumgood.github.io

원문 : https://stackoverflow.com/questions/1506078 permutation of n elements가 있을 때, integer로 mapping하는 방법에 대해 설명한다. n!의 permutation이 있을 수 있고, 이를 n!가지의 정수에 1:1 mapping하는 것이 목적이다. n개의 원소로 이루어진 permutation을 설명할 때, 첫 번째 원소가 있을 수 있는 위치는 n가지가 있다. 따라서 이 원소의 위치를 0~n-1 사이의 수로 나타낼 수 있다. 그 다음 원소가 있을 수 있는 위치는 남은 n-1가지이다. 그래서 이 원소의 위치를 0~n-2 사이의 수로 나타낼 수 있다. 이를 위치를 나타내는 n개의 수를 얻을 때까지 계속 반복한다. n=5인 경우를 예로 들어, '..

Today I want to introduce you some very very useful data structures. Trees Trees are one of the most useful data structures. A tree is a connected-acyclic graph. Ther are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc. Partial sum There are two types of problems solvable by partial sum. 1. Problems which you are asked to answer some queries about the sum..

원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속된 부분에 대한 query들을 처리할 때 사용한다. 첫번째 예로 다음 두 명령어를 생각해두자. 1. 배열에 있는 한 원소를 수정한다. 2. 어떤 범위에 대한 원소들의 합을 찾는다. Perfect binary tree 다음은 segment tree를 도식화한 것이다. 표기법은 node_index: corresponding segment [left border included, right excluded)이다, 트리의 leaf에 해당하는 맨 밑에 행은 우리의 배열에 해당한다. Perfect..

양의 정수 N이 2의 지수라고 하자. 길이가 N인 배열 \(a\)의 각 원소를 \(a_i\)라고 하자\((i \in [0, N-1])\). 어떤 원소 \(a_i\)를 수정하는 규칙이 있을 때, 이것을 \(a_x\)와 \(a_y\) 사이 모든 원소들에 적용시킨다고 생각하자. 이것을 Range modification이라고 부를 것이다. 결합법칙(Associative property)과 교환법칙(Commutative property)을 만족하고 항등원(identity element)를 가지는 어떤 이진연산을 예를 들어 \(\times\)로 나타내자. \(a_x\)와 \(a_y\) 사이 모든 원소들간에 연산을 적용한 결과\((a_x \times a_{x+1} \times ... \times a_{y-1} \ti..

Binary Search(이분 탐색)는 일반적으로 간단한 알고리즘에 속한다. 막상 문제를 풀다보면 'exit conditions'나 'midpoint calculation'에 있어서 헷갈릴 여지가 있다. 풀려는 문제의 조건에 따라 미묘한 구현의 차이가 존재하기 때문이다. 이를 명확하게 정리해두고자한다. Algorithm Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. - If the target value matches the middle element, its position in the array is return. - If..

Fenwick Tree : *부분합을 빠르게 계산하면 구간합도 계산할 수 있음을 이용한 구간합 treeBIT(Binary Indexed Tree)라고 부르기도 한다. (*부분합 psum[pos] : 배열의 첫 부분부터 연속된 합 (A[0] + A[1] + ... + A[pos]))구간합 [i, j]는 psum[j] = psum[i-1]으로 쉽게 구할 수 있다. * 여기 종만북과 비슷한 설명이 잘 되어있다. * Seg-tree보다 간단하고 빠르고 메모리 적게 먹음. 1. Fenwick Tree와 Segment Tree Segment tree에서 [0, 15] node의 자손으로 [0, 7], [8, 15] node가 있는데, 사실상 [0, 7]을 알면 [8, 15]의 node는 필요가 없다. Seg-tre..

무방향성 가중치 그래프 G에 대해- Spanning tree : 그래프 G의 모든 node를 포함하는 Tree를 말한다. 그래프 G의 부분그래프- MST(Minimum Spanning Tree) : G에 대한 spanning tree 중 가중치의 합이 가장 작은 tree MST를 찾는 Greedy method가 있다. (Prim, Kruskal, Sollin...)대표적인 Kruskal's algorithm에 대해서만 서술한다. 1. Kruskal's algorithm 수행과정 ① graph의 모든 edge를 가중치의 오름차순으로 정렬한다. ② edge의 가중치가 작은 순으로 spanning tree에 추가해나간다. ③ 추가했을 때 spanning tree와 cycle이 생기는 간선은 제외한다. ④ ②~..

- LIS(Longest Increasing Subsequence) : 최대 부분 증가수열- 수열에서 증가하는 순으로 고를 떄, 최대 길이를 갖는 수열을 말한다. (not unique) 설명이 굉장히 잘 되어있는 블로그가 있다. 여기도 괜찮다. 'LIS의 길이를 구하는 여러가지 방법이 있다. 시간 복잡도, 구현이 간단한지 등을 고려하여 문제에 맞는 알고리즘을 써야한다. 1. Dynamic Programming 구현과 역추적이 쉽다. 1차원 DP로 $(O^2)$에 해결할 수 있다. C++11 2. Binary Search 구현은 간단한 편이다. 다음과 같은 수행과정을 따른다. ① vector 하나를 생성한다. ② 수열 arr를 처음부터 돌면서 vector의 마지막 원소보다 - 큰 경우, vector에 pu..