Codeforces Round #777 (Div. 2)

A. Madoka and Math Dad 각 자릿수의 합이 N이고, 0을 제외한 숫자를 사용하고, 연속된 같은 문자가 없는 큰 수를 만드는 문제이다. 먼저 1, 2만 사용하는 것이 가장 이득이고, dp[i] = 각 자릿수의 합이 i일 때 최대 숫자로 정의하면 쉽게 풀 수 있다. 6분컷했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..

→2022.03.14

[Unity] 2D Tile Map Occlusion Culling

최근에 프로젝트를 해보면서 2D Tile Map에서 작동되는 Occlusion Culling 을 구현하게 되었다. 카메라에서 일정 구역만 타일을 활성화시켜 성능적으로 이득을 볼 수 있다. 물론 작은 Tile Map에서는 모두 활성화하는 것이 이득이지만 Tile Map이 커질 수록 상당한 이득 볼 수 있을 거라 생각한다. 먼저 정적인 상태에서 Culling 구역을 활성화하는 방법을 생각해보자. 단순히 Tile Map의 모든 타일을 가져온 다음 해당하는 구역에 존재하는 타일만 활성화시키는 방법이다. 모든 타일의 개수를 S라 정의할 때, 시간 복잡도는 \(O(S)\)가 된다. 여기서 전체를 탐색하지 말고 해당하는 구역만 탐색하여 활성화하는 방법을 고민할 수 있다. 전체 Tile Map을 분할 정복으로 해당하는..

→2022.01.31

[백준 15506] 정원사

1. 풀이 세그먼트 트리에 pq를 넣는 다는 신박한 아이디어다. \(2, 3\)번 쿼리를 보면 세그먼트 트리로 관리해야 겠다는 생각이 든다. 또한 \(1\)번 쿼리의 어떤 정원에 존재하는 값은 모두 관리해주어야 된다. 세그먼트 트리의 리프 노드에 pq를 넣자. 그렇다면 \(1\)번 쿼리는 세그먼트 트리의 리프 노드의 pq에 값을 넣는 것으로 처리할 수 있다. \(2\)번 쿼리를 생각해보자. 각 구간의 정원에서 가장 큰 값 가지는 정원의 인덱스를 가져오는 쿼리를 할 수 있다면 쉽게 해결할 수 있다. 그리고 인덱스에 있는 리프 노드의 pq에서 값을 하나 빼주면 된다. 기껏해봐야 M번 반복 될 것이다. 각 정점에 {pq에서 가장 큰 값, 인덱스}를 관리해주면 쉽게 해결해줄 수 있다. \(3\)번 쿼리는 단순히..

→2021.12.21

[백준 20052] 괄호 문자열 ?

1. 풀이 \(( = 1, ) = -1\) 으로 치환하고 구간합을 만들어 보자. 그러면 어떤 구간 \([l, r]\)이 올바른 괄호문자열인 충분 조건은 아래와 같다. 1. \(psum_l = psum_r + 1\) 2. \(psum_r \le min(psum_{[l,r]})\) min은 세그먼트 트리로 쉽게 구해줄 수 있다. \(O(QlogN)\)에 문제를 해결할 수 있다. 추가로 구간 합 아이디어와 스택을 활용하면 쿼리를 O(1)에 해결할 수도 있다. 2. 소스코드 #include using namespace std; struct Segment { int n; vector seg; void Init(int _n) { n = _n; seg.resize(4*n, 1e9); } int update(int n..

→2021.12.21

[백준 17704] Matryoshka

1. 풀이 각 쿼리마다 조건을 만족하는 점들 중에서 \((a, b) (c, d) a d\)를 만족하는 LIS길이가 쿼리의 답이 된다. Dilworth's theorem과 관련이 있다. 그러므로 쿼리를 오프라인으로 잘 스위핑 하면서 LIS는 세그먼트 트리로 잘 구해줄 수 있다. \( O(NlogN)\)에 문제를 해결할 수 있다. 2. 소스코드 #include using namespace std; typedef pair pi; #define R first #define H second stru..

→2021.12.21

세그먼트 트리 (Segment Tree)

Segment Tree란? Segment Tree(구간 트리)는 각 구간을 이진 트리로 관리하여 원소의 변경 혹은 구간의 연산을 효율적으로 처리할 수 있는 자료구조 입니다. 먼저 Segment Tree가 대표적으로 어떻게 활용되는 지 알아보겠습니다. 아래 문제를 해결해봅시다. 길이가 \(N\)인 배열 \(A\)가 주어지고, 아래의 쿼리를 효율적으로 처리해야 됩니다. 1. \([l, r]\) 구간의 합 구하기 2. \(i\)번째 수를 \(x\)로 변경하기 Naive하게 접근하면 \(1\)번 쿼리는 \(O(N)\), \(2\)번 쿼리는 \(O(1)\)에 처리할 수 있습니다. 하지만 Segment Tree는 \(1\), \(2\)번 쿼리 모두를 \(O(logN)\)에 처리할 수 있습니다. 아이디어 Segmen..

→2021.12.20

한국 정보 올림피아드 정리

연도 부문 1 2 3 4 KOI 1996 초등부 단지 번호 붙이기 숫자 고르기 직사각형 네개의 합집합의 면적 구하기 중등부 연속 부분 최대곱 잠수함 식별 여러 직사각형의 전체 면적 구하기 고등부 잠수함 식별 교차하지 않는 원의 현들의 최대 집합 삼각퍼즐 KOI 1997 초등부 직각 이등변 삼각형 찾기 십자 카드 문제 회장 뽑기 중등부 좋은 수열 기업 투자 간척지 만들기 고등부 다각형의 확장 미로 만들기 벽장문의 이동 KOI 1998 초등부 교차점 개수 자동차 경주 대회 블록 맞추기 중등부 안정된 집단 연결 사각형 가장 높은 탐 쌓기 고등부 울타리 치기 통나무 옮기기 화물차의 경로 KOI 1999 초등부 다각형 그리기 전개도 색종이 올려 놓기 중등부 촌수 계산 회로 배치 같은 길이 막대기 만들기 고등부 검..

→2021.12.13

[백준 7994] The Islands

1. 풀이 도형 \(A\)가 도형 \(B\)에 포함 되어 있다는 것은 \(sy_B\) \(ey_B\) 사이에 도형 \(A\)가 포함된다는 것이다. 문제에서 교차하는 도형이 없다고 주어졌기 때문에 이렇게만 고려해주어도 괜찮다. 위의 아이디어를 기반으로 어떤 도형이 주어졌을 때 +\(1\), -\(1\)을 가진 \(y\)가 있고, \(x\)축의 구간으로 분리하자. 문제의 예제 중 도형 하나를 구간으로 분리한 것이다. 이 도형을 분리하는 방법은 lazy seg로 할 수 있다. 1. \(x\)축에 있는 모든 값을 \(0\)으로 초기화한다. 2. 도형에서 \(x\)축에 평행한 구간만 확인한다. 구간의 값이 \(0\)인 경우 +\(1\) 구간이 되고, \(1\)인 경우 -\(1\) 구간이 된다. 모든 도형을 \(x..

→2021.12.13