분류 전체보기52 KMP KMP Algorithm Knuth-Morris-Pratt Algorithm 문자열 S와 T가 주어질 때 S가 T를 포함하는지 판단하는 문자열 검색 알고리즘 1. 문자열 T에 대한 pi 배열(size=M)을 구한다. pi배열은 문자열 T 내의 반복된 문자열을 찾아 탐색 시간을 줄이는 데에 쓰인다. pi[ i ] = k ⇔ T[ 0 ~ k ] = T[ i-k ~ k ] ⇔ T의 부분문자열(0~i)의 앞/뒤에서부터 길이 k인 부분문자열이 서로 같다. // Get pi int M = T.size(); vector pi(M, 0); for (int i = 1, j = 0; i 0 && T[i] != T[j]) j = pi[j - 1]; if (T[i] == T[j]) p.. 2021. 4. 9. SDBMS ⑤ The Z-Ordering Tree SDBMS 공간데이터베이스 ⑤ The z-Ordering Tree 0. Z-Ordering 여러 개의 quadrant를 이용하여 하나의 다각형을 mbb가 아닌 형태로 나타낼 수 있다. degree=3으로 공간을 나눈 경우 가장 작은 quadrant는 전체 공간의 1/64 크기가 되고 label 길이는 3이 된다. 이때 도형 A의 경우 위처럼 표현할 수 있다. 만약 degree=2로 공간을 나눴다면 A={01,02,03,12,20,21,23,31}가 된다. 이런 방식으로 객체 정보를 저장하고 인덱싱 한 게 Z-Ordering Tree이다. 1. The Z-Ordering Tree Z-Ordering tree는 linear quadtree와 마찬가지로 quadrant의 label을 key로 하는 B+tree.. 2021. 4. 8. 구현 (2) 지난 주 푼 문제 10253 헨리 구현 수학 써져있는 대로 구현하기만 하면 되는 문제. 5577 RBY팡! 구현 시뮬레이션 나 진짜 멍청했던게 RRRBRR 처럼 가운데에 하나 낀 애들만 색깔 바꿀 생각해서 계속 틀렸었다. 그래서 RRRBB있으면 하나도 팡! 안했었음 ㅋㅎㅋ RRRRBB로 바꿔서 팡 할 수 있는데,,, 한 이틀 뒤에 깨달았다.. 한 번 막힌 사고는 다시 흐르기가 참 어렵다.. 14601 샤워실 바닥 깔기 (Large) 분할정복 구현 처음에는 대칭성을 이용해 풀려고 했는데,,, 너무 복잡해졌고 ㄱ자 모양은 정사각형에서 한 칸 뺀 거라는 사실을 이용해서 생각해내야 했다. 사분할한 각 정사각형이 모두 비어있을 때만 꼭짓점을 채워 ㄱ을 만드는 형식을 반복하면 된다. 솔직히 너무 씽크빅이었지만 이런 것도 풀 줄 아는.. 2021. 4. 5. SDBMS ④ The Linear Quadtree SDBMS 공간데이터베이스 ④ The Linear Quadtree 0. The Quadtree 공간을 사분할하여 데이터를 저장하는 구조 단순하게 NW, NE, SW, SE로 사분할하여 공간 상에서의 quadrant ↔ 트리의 leaf node ↔ page 로 대응, quadrant와 겹치는 데이터의 [mbr,oid]를 해당 page에 저장한다. 아주 직관적이고 구현이 쉽다. 그러나 - node 당 child의 수가 4개로 고정되어있다. 빈 quadrant에 대응되는 node도 생겨 page waste 발생 - quadrant가 작을수록 겹치는 게 많아 중복저장이 증가한다. (grid file에서와 같음.) - 한쪽으로 데이터가 집중될 경우 leaf node의 깊이가 각각 달라진다. 따라서 (B+tree와.. 2021. 4. 2. SDBMS ③ SAM, The Grid File SDBMS 공간데이터베이스 ③ SAM, The Grid File 0. SAM The main purpose of spatial access methods is to support efficient selection of objects based on spatial properties. * SAM = 공간적 특성이 있는 객체를 좀 효율적으로 고르는 방법. 이라고 이해하면 된다. 점, 선, 면을 object자체보다 단순화해서 MBR(Minimum Bounding Rectangle)이나 MBB(Minimum Bounding Box)로 나타내는 방법을 사용하면 복잡한 도형도 간단히 표시할 수 있고, 일정한 크기의 entry로 사용할 수 있다는 장점이 있다. 즉 각 entry의 자세한 정보는 page에 저장하고 .. 2021. 3. 29. BOJ13141 Ignition BOJ13141 Ignition 그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력 불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며 시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다. 두 가지가 필요하다. 1. 한 vertex에 불이 도달할 수 있는 최소 시간 2. 두 vertex 간 edge가 모두 타는 시간 1의 경우 같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다. 결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다. 2의 경우 두 vertex 간 가장 긴 edge.. 2021. 3. 17. SDBMS ② ER Diagram and Relational Schema SDBMS 공간데이터베이스 ② ER Diagram and Relational Schema ER Diagram 데이터 모델의 entity를 직사각형, attribute를 타원, relationship를 마름모로 표현한 그림. Pictogram을 이용해 객체의 공간적 정보를 나타낼 수도 있다. Relational Schema 데이터 모델을 logical model로 나타낸 것. Logical model을 디자인할 때는 relationship을 entity로 표현할 지, attribute로 표현할 지가 관건이다. ...그냥 그림을 보자... 각 그림을 비교해서 무얼 어떤 식으로 나타냈는지 보면 된다. E를 ER Diagram, R을 Relational Schema, P를 ER Diagram with Picto.. 2021. 3. 15. SDBMS ① Spatial Data Model and Topological Relationship SDBMS 공간데이터베이스 ① Spatial Data Model and Topological Relationship 1. Data Model 데이터를 활용하기 위한 데이터 모델은 여러 종류가 있겠으나 일반적인 데이터 모델은 Spatial ADT 지원이 안 돼 공간적 데이터에는 적합하지 않다. 이 과목에서 다루는 내용은 Applicatoin Domain specific한 데이터 모델 *ADT: Abstract Data Type *Application Domain specific: 솔직히 이 말 잘 이해 못하겠으나,, '지리적 정보에 대한 개념이 탑재된' 정도로 이해하면 될 듯 Spatial 모델은 위치에 초점을 두느냐 객체에 초점을 두느냐로 나눠 생각할 수 있다. 이 글에서 주로 설명할 건 object b.. 2021. 3. 15. 그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15. 기하학 (2) 계산 문제들 1207번 고층건물 - 기울기16190번 Rising Sun - 좌표, 기울기16115번 팬이에요 - 삼각함수1798번 원뿔좌표계상의 거리 - 좌표, 삼각함수1207번 고층 건물같은 간격으로 떨어져 있는 건물의 높이가 정수로 주어질 때각 건물의 옥상에서 보이는 다른 건물의 개수 중 최댓값 출력현재 건물과 보려고 하는 건물의 옥상을 이은 선분에 다른 건물이 교차하거나 만나면 안 된다. 즉, 현재 건물의 옥상을 점 A라 하고현재 건물에서 볼 수 있는 건물의 옥상을 왼쪽에서 오른쪽 순서로 각각 점 B1, B2, ...라 하면선분 AB1, AB2, ...의 기울기가 순서대로 증가해야 함 기울기가 같으면 안 됨. 8에서는 7만 보이고 6은 볼 수 없다. 높이가 극댓값인 건물만 보면 틀린다.낮은 건물에서 다른 건물.. 2021. 3. 15. 이전 1 2 3 4 5 6 다음
