원당컴퓨터학원

Topological Sorting(위상정렬) 이란 위상정렬은 유향그래프(방향그래프)의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명하는 예는 선수과목의 구조를 예로 들 수 있다. 특정 수강과목에 선수과목이 있다면 그 선수과목을 먼저 수강해야 하므로 특정과목을 수강해야 할때 위상정렬을 통해 올바른 수강순서를 찾아 낼 수 있다. Topological Sorting(위상정렬) 조건 사이클이 없는 유향 그래프 Topological Sorting(위상정렬) 특징 모든 정점을 일렬로 나열 정점 x에서 정점 y로 가는 간선이 있다면 x는 반드시 y보다 앞에 위치한다. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다. Topological Sorting(위..

트라이의 정의를 위키백과의 내용을 인용하면 다음과 같습니다. 트라이(trie)는 컴퓨터 과학에서 탐색트리의 일종이다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 트라이(trie) 란? 문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸릴 수 있습니다. N개의 원소를 갖는 이진검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교만으로 찾을 수 있습니다. 이러한 이진 검색 트리에서 착안을 하여 고안된 문자열 특화 자료구조가 바로 트라이(trie) 로 집합 내에서 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 그렇다면 어떻게 가능한지 다음을 살펴 보시죠~ 그림은 문자열집합 S={"A","to","tea","ted","ten","inn"} 을 저장하..

비트연산 활용 1. 모든 부분집합 순회하기 예) 피자의 토핑 종류가 (페페로니,소시지,양파) 라고 하면 {페페로니},{페페로니,소시지},{페페로니,소시지,양파},{소시지},{소시지,양파},{양파} 와 같이 하나 하나 열거하는 경우 다음과 같이 처리 1 2 3 4 5 6 for (int subset = pizza; subset; subset = ((subset-1) & pizza)) { //subset 은 pizza의 부분 집합 } Colored by Color Scripter cs 2. 비트마스크를 활용하여 에라토스테네스 체 치기(체치는 메모리를 적게 잡기 때문에 훨씬 더 많은 양의 체를 칠 수 있다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

비트마스크란? 컴퓨터는 모든 정수형변수를 이진수로 표현합니다. 이 때 이진수의 한 자리를 비트(bit)라고 부릅니다. 비트는 0 또는 1의 값을 가지며 컴퓨터가 표현하는 모든 자료의 근간이 됩니다. 이러한 이진수표현을 자료구조로 사용하는 기법을 비트마스크(BitMask) 라고 부릅니다. 비트마스크는 엄밀하게 ㅏ료구조라고 할 수는 없지만 굉장히 유용하게 사용 됩니다. 비트마스크를 왜 사용하는가? 1. 더 빠른 수행시간 : 비트마스크 연산은 O(1)으로 구현이 됨, 따라서 여러번 수행하는 경우에는 작은 최적화로 속도 향상을 가져올 수 있음 2. 더 간결한 코드 : 반복문 없으 한줄에 사용하므로 짧은 코드를 작성 3. 더 작은 메모리 사용 : 32비트형 정수형 자료형에 32개의 0/1 형태의 정보를 저장 비트..

2차원 펜윅트리를 구현하기 전에 1차원펜윅트리를 먼저 이해합니다.(https://wondangcom.tistory.com/1582) 1차원 배열이 여러개 인 행렬 구조의 데이터가 업데이트가 많은 경우 사용하게 되는데 1차원펜윅트리를 여러 개 이어 붙인 것이 2차원 펜윅트리라고 생각할 수 있다. 2차원의 구간합을 구하기 위해서 2개의 인덱스(y,x)가 필요하다. 그림으로 이해하면 다음과 같다. (x1,y1) ~ (x2,y2) 의 구간합을 구하는 방법을 살펴 보면 먼저 (0,0)~(x2,y2) 의 구간합을 구한다. 이때 녹색과 하늘색 부분인 (0,0) ~ (x1,y2), (0,0)~(x2,y1) 구역을 빼 주면 되는 것을 확인 할 수 있다. 이렇게 두개의 구간 합을 빼 주면 (0,0) ~ (x1,y1) 구간..

펜윅트리(Fenwick Tree)란? - Binary Indexed Tree 라고도 하며 이진수를 이용하여 위치값을 표현하는 세그먼트 트리와 유사한 트리 펜윅트리(Fenwick Tree) 의 개념 10진수 수를 이진수로 표현해 보면 다음과 같다. 3 = 00000011 4 = 00000100 5 = 00000101 6 = 00000110 8 = 00001000 9 = 00001001 10 = 00001010 11 = 00001011 12 = 00001100 16 = 00010000 여기서 이진수의 마지막 1의 위치를 확인하면 다음과 같다. 3= 왼쪽에서 첫번째 자리 (10진수의 값으로 1) 4= 왼쪽에서 3번째 자리 (10진수의 값으로 4) 5= 왼쪽에서 첫번째 자리(10진수의 값으로 1) ... 16 ..

세그먼트 트리(Segment Tree)란? - 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조 - 구간 중에 Max,Min,Sum(최대,최소,구간의 합) 등을 빠르게 갱신할 수 있는 자료구조 세그먼트 트리(Segment Tree) 구현 목적 배열의 데이터 수 : 10개 배열의 데이터 A[10] = {1,2,3,4,5,6,7,8,9,10} 목적 : 구간에 대한 합 예) 4번째 부터 6번째까지의(배열의 3번지부터 5번지까지의) 구간합은? 15 이러한 구간합을 구하는 가장 간단한 방법은 합을 미리 구해 놓고 1번째 부터 6번째의 합 21 에서 1번째 부터 3번째의 합 6을 빼면 15가 나온다. 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 하지만 각 데이터가 ..

위의 그림과 같이 x1,y1,r1/ x2,y2,r2 가 주어진 경우 겹치는 영역의 넓이를 구하는 방법에 대해 살펴 보도록 하겠습니다. 두 원의 중심과 중심 사이의 거리 d는 피타고라스의 정리에 의해서 d * d = (x1-x2) * (x1-x2) + (y1-y2)*(y1-y2) 가 됩니다. 여기서 부채꼴의 넓이를 구하는 공식을 살펴 보자. S(부채꼴의 넓이) = πr2 * x/360 으로 구할 수 있다. 각도를 θ/2π 와 같이 나타낼 수 있으므로 S(부채꼴의 넓이) = πr2 * θ/2π -------------(1) 여기서 겹치는 영역의 값을 구한다고 하면 다음과 같이 구할 수 있다. S1(부채꼴 1의 넓이) + S2(부채꼴 2의 넓이)를 먼저 구한다. 그러면 우리가 구하려고 하는 겹치는 영역의 넓이..

Lazy Propagation 이란? 기존 세그먼트 트리에서 i 에서 j 까지의 구간을 업데이트 하기 위해서는 수행시간은 O(NlogN)의 시간이 걸리게 된다. 이 구간 없데이트 시간을 단축 시키기 위한 알고리즘이 필요한데 이때 사용하는 알고리즘이 Lazy Propagation(게으르게 전파) 알고리즘이다. 이 알고리즘의 수행 속도는 O(logN) 이다. Lazy Propagation 동작 방법 배열 {1,2,3,4,5} 가 있는 구간합의 예를 살펴 봅니다. 세그먼트 트리 구현시 다음과 같은 트리가 생성 됩니다. 이때 0번지 부터 2번지까지에 3을 더해 준다고 하면 다음과 같이 계산이 됩니다. 파랑색 부분을 계산하면서 노랑색 부분은 (0~1) 위치는 2번, (0~2) 위치는 3번, (0~4) 위치는 3번..

Convex Hull trick 란 Convex Hull trick 란 Convex Hull(블록껍질) 알고리즘과는 다른 알고리즘이다. 최적의 값을 찾아가는 형태가 Convex Hull 을 닮아서 Convex Hull trick 라고 알려져 있는데~ Convex Hull Optimization 이라고도 한다. 이 알고리즘은 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. 일차 함수식이 위와 같이 여러개가 들어 오는 경우 각 x의 입장에서 최솟값을 찾는 알고리즘 동적알고리즘에서 다음과 같은 형태의 점화식 작성시 사용됨 dp[i] = min(dp[j] + a[i]b[j])( 0 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ....