hibye1217 hibye1217

난이도: Platinum II 태그 더보기 Stack → Parenthesis Matching Dynamic Programming (on Tree) → Kth Smallest Element (Ordered) Set Backtracking 풀이 1. 괄호 문자열을 토대로 트리를 만들어보자. 더보기 각각의 괄호 쌍에 대해, 이 안에 있는 다른 괄호 쌍이나 숫자를 이어줍시다. 그러니까... 대강 이런 식으로요. 하나의 괄호 쌍은, 자식으로 다른 괄호 쌍이나 어떤 수를 가지게 됩니다. 그럼, 특정 괄호 쌍을 나타내는 정점에서 만들 수 있는 문자열은, 각 자식에서 만들 수 있는 문자열을 들고 온 뒤, 그 순서대로 concat하는 것으로 볼 수 있겠죠. 또한, 이렇게 트리를 만들면, ()를 뒤집는 건 그 서브트리 ..

난이도: Platinum III 태그 더보기 Fibonacci Number Binary Search Exponentiation by Squaring → Matrix Exponentiation 풀이 1. 오징어 수를 분석해보자. 더보기 (일반성을 잃지 않고) 오징어가 출발하는 위치 (고양이의 집)을 \( 0 \)으로 고정시켜봅시다. 그리고, 당근의 위치는 \( a \), 토끼의 집의 위치는 \( b \)라고 해봅시다. 오징어는 당근을 건너뛰어야 하기 때문에, \( 0 \Rightarrow a-1 \rightarrow a+1 \Rightarrow b \)의 경로를 타야 합니다. 즉, 오징어가 선택할 수 있는 경로의 수는 \( 0 \Rightarrow a-1 \)의 가짓수 × \( a+1 \Rightarrow..

난이도: Platinum IV 태그 더보기 Breadth First Search (In 2D grid) 풀이 1. 그래프를 정의해보자. 더보기 정점은 튜플 \( (r, c, i) \) = \( i \)개의 글자를 쓴 뒤 \( (r, c) \) 위치로 오는 경우 로 잡고, 간선은 각 \( (r, c) \)에서 상/하/좌/우/선택 중 하나의 키를 누를 때 가게 되는 위치에 연결하면 됩니다. 선택의 경우, 실제로 맞는 글자일 때만 연결해야겠죠. 문제의 답은 \( (1, 1, 0) \)에서 출발해서 \( (*, *, |S|) \)로 가는 최단 경로가 됩니다. 2. 시간복잡도 / 공간복잡도에 대한 걱정 더보기 시간복잡도와 공간복잡도 모두 \( O(NM|S|) \)가 됩니다. AC를 받아도, TLE/MLE를 받아도..

난이도: Platinum V 태그 더보기 Depth First Search Dynamic Programming on Tree 풀이 1. 트리 \( A \)와 \( B \)에 대해, \( A \times B \)의 지름은? 더보기 (\( A \)의 지름) + 2 × (\( B \)의 깊이)가 됩니다. // \( A \)의 지름의 두 끝점에서 \( B \)를 타고 최대한 많이 내려가는 걸 생각해봅시다. ...한 가지 예외가 있는데, \( A \)의 크기가 1일 때입니다. 하지만 크기가 1인 트리는 Tree Product의 항등원이기 때문에 (아무리 곱해도 결과가 바뀌지 않음) 따로 빼놓을 수 있기 때문에, 걱정하지 않아도 됩니다. 2. 트리 \( A \)와 \( B \)에 대해, \( A \times B \..

난이도: Gold II 태그 더보기 Breadth-First Search Combinatorics Meat In the Middle (알고 있을 필요는 없지만, 뭔가 그런 느낌이 있다.) 풀이 1. 원래의 최단 경로를 알고 있을 때, 간선을 하나 추가한 뒤의 최단 경로는? 더보기 원래의 최단 경로를 \( [s = v_0, v_1, \ldots, v_k = t] \)라고 하고, 추가된 간선을 \( {x, y} \)라고 합시다. 그럼, 새로운 그래프의 최단 경로는 원래의 최단경로이거나, \( [s, \ldots, x, y, \ldots, t] \)라는 새로운 경로가 됩니다. \( d(v, w) \)를 \( v \)에서 \( w \)로 가는 최단 경로의 길이라고 하면, 우리가 찾은 경로의 길이는 \( d(s,..

난이도: Gold III 태그 더보기 Diameter of a Tree 풀이 1. 답의 Upper Bound는? 더보기 ceil( (트리의 지름) / 2 )입니다. 트리의 지름을 정확히 절반으로 나누는 어떤 점을 선택했을 때, 그 점에서부터 지름의 두 끝점까지의 거리죠. 2. 근데 그 Upper Bound보다 더 잘 할 수 있나? 더보기 트리의 지름의 두 끝점을 \( v, w \)라고 해봅시다. 그럼, 임의의 정점 \( u \)에 대해 \( d(v, u) + d(u, w) \ge d(v, w) \)가 됩니다. 즉, \( u \)로 무슨 정점을 잡아도 \( d(v, u) \)랑 \( d(u, w) \) 둘 중 하나는 UpperBound 이상의 값을 가지게 되니, [1]에서 구한 UpperBound가 실제로..

난이도: Gold IV 태그 더보기 Greedy Two Pointer 풀이 1. 맨 앞 글자와 맨 뒷 글자가 다르다면, 무슨 글자를 선택해야 할까? 더보기 사전순의 정의에 따라, 둘 중 더 빠른 글자를 선택해야 합니다. 2. 맨 앞 글자와 맨 뒷 글자가 똑같은데... 앞에서부터 2번째 글자와 뒤에서부터 2번째 글자가 다르다면? 더보기 2번째 글자를 비교한 뒤, 더 빠른 쪽을 선택하면 됩니다. 이유는, 다음에 보여지게 되는 글자를 생각해보면 됩니다. [2]에 대한 증명 더보기 길이 \( N \)의 문자열 \( S \)에 대해, 일반성을 잃지 않고 \( S_{1} = S_{N}, S_{2} < S_{N-1} \)이라고 해봅시다. 그럼, 아래 경우로 나눠볼 수 있습니다. \( S_{1} < S_{2} \): ..

난이도: Gold V 태그 더보기 Greedy 풀이 1. 방향이 다른 두 그림이 겹칠 수 있을까? 더보기 만약 겹친다면, 아래와 같은 느낌이 될 겁니다. 하지만 위 경우를 만들어낼 수 있는 벽의 배치가 존재하지 않기 때문에, 걱정하지 않아도 된다는 결론이 나옵니다. 2. 방향을 고정했을 때, 걸 수 있는 그림의 개수는? 더보기 하나의 벽의 길이가 \( X \)라면, 그 벽에 \( \left\lceil \frac{X}{2} \right\rceil \)개의 그림을 걸 수 있습니다. 위 식을 특정 방향을 보는 모든 벽에 대해 다 구해주면 되겠죠. 3. 구현 디테일 더보기 저의 경우는 벽의 길이를 계산하는 대신, 그림을 걸 수 있는 경우가 나오면 바로 그림을 건다고 한 뒤 그림이 겹치게 되는 경우를 건너뛰게 했..