Byeo

설명은 나중에... RUST use std::io::{stdin, Read}; const DR: [i32; 6] = [-1, -1, 0, 1, 1, 0]; const DC: [i32; 6] = [-1, 1, 1, 1, -1, -1]; fn dfs(i: usize, graph: &Vec, visited: &mut Vec, parent: &mut Vec) -> usize{ for _r in graph[i].iter(){ if visited[*_r] == true{ continue; } visited[*_r] = true; if parent[*_r] == -1 || dfs(parent[*_r] as usize, graph, visited, parent) == 1{ parent[*_r] = i as i32; r..

개요 Boj 17435 - 합성함수와 쿼리는 중첩함수를 미리 계산해놓은 테이블을 갖고 얼마나 빨리 찾도록 구현할 수 있냐의 문제입니다. $f_n(x) = f(f(f(f(...f(x)...))))$ 를 구하는데 최적화하기 위해서 어떻게 사전에 계산해놓을 수 있을까요? 그 비결은 $f_{(a+b)}(x) = f_a(f_b(x))$ 에 있습니다. 그리고 몇몇 포인트들만 사전에 계산해두는 것이지요. 설명 $f_{(a+b)}(x)$ 는 풀어쓰면 $f$가 $a$번 중첩된 $f(f(....(f_b(x))))$로 풀어쓸 수 있습니다. 즉, $f_b(x)$의 값 $B$을 미리 계산해놓는다면 그 값에 단순히 $f_a(B)$를 구하면 최종 함수 값을 알 수 있지요. 이 문제는 그래서 $f_n(x)$에서 $n$의 2의 거듭제..

1. 설명 MST를 구하는 유명한 알고리즘의 두 번째로는 크루스칼 알고리즘은 greedy 알고리즘으로 볼 수 있다. 간선의 가중치가 작은 것부터 하나하나 MST에 포함시켜보면서 cycle이 생기는 지 매번 판단하는 방법으로 이뤄진다. 이전 포스트의 프림 알고리즘 예제에서 사용했던 예제를 그대로 사용해보자! 추가로 MST가 무엇인지 알고 싶다면: 링크 2. 예제 (1) 초기 환경이 다음과 같다고 하자. 크루스칼 알고리즘은 가중치가 작은 간선부터 차례로 MST에 포함시켜 보는 것이다. 만약 포함시켰는데 MST에 위배된다면 뺀다. 오른쪽은 union-find array를 나타낸다. 자세히는, 각 vertex가 속해있는 그룹의 주인 (root, 특별한 역할이 있는 노드는 아니다. 단순히 학창 시절 '주번' 같은..

1. MST란 MST, 최소 신장 트리 (Minimum Spanning Tree)란? MST란, 가중치가 있는 무방향성 그래프 (weighted undirected graph)가 주어졌을 때, 모든 vertex를 연결할 수 있도록 edge를 선택하는데 그 가중치의 합(비용)이 최소가 되도록 하는 edge set을 말한다. MST 알고리즘을 통해 구한 edge들로만 그래프를 재구성하면, 임의의 vertex a와 b사이에는 항상 경로가 존재하며, 그래프에서는 cycle이 없다. 이를 구하기 위한 방법으로는 대표적으로 프림 알고리즘과 크루스칼 알고리즘이 있다. 프림 알고리즘은 우선순위 큐를 이용해서, 크루스칼은 union-find를 이용해서 해결한다. MST 특성 MST는 다음과 같은 특성을 지닌다. [참고]..

VSCode 설치 - vscode를 설치해봅니다! - 그리고 vscode를 이용해 원격 서버 접속 개발을 해봅니다. 1. Download https://code.visualstudio.com/download Download Visual Studio Code - Mac, Linux, Windows Visual Studio Code is free and available on your favorite platform - Linux, macOS, and Windows. Download Visual Studio Code to experience a redefined code editor, optimized for building and debugging modern web and cloud application..

목차 개요 설명 코드 풀이 과정 개요 삼각함수를 이용해서 겹쳐진 두 원의 넓이를 구하는 문제입니다. 두 원이 존재할 수 있는 방법은 다음과 같이 세 가지 경우가 있습니다. 1) 두 원이 완전히 겹쳐지지 않은 경우 2) 일부가 겹친 경우 3) 한 원이 다른 원에 완전히 속한 경우 설명 먼저, 두 원의 원점 사이의 거리는 $d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ 입니다. 1) 두 원이 완전히 겹쳐지지 않은 경우 두 원이 겹쳐지지 않기 위한 조건은 $d > r1 + r2$ 입니다. 이 때, 겹치는 넓이는 $0$ 입니다. 2) 일부가 겹친 경우 두 원이 일부만 겹치기 위한 조건은 $|r1 - r2| < d < r1 + r2$ 입니다. 이 때, 부채꼴을 이루는 각 $\alpha$와 $..

목차 개요 요약 설명 코드 개요 이 문제는 Segment Tree 자료구조와 Sweeping 알고리즘을 함께 활용하여 풀어야 하는 문제입니다. 추가로 좌표의 범위가 상당히 넓기 때문에 ($0$ ~ $1,000,000,000$) 좌표 압축까지 병행해야 합니다. 문제의 Key Idea는 Segment Tree에 어떤 정보를 저장할 것이냐 입니다. 예를 들어, x축으로 Sweeping을 진행한다고 할 때, 직사각형의 넓이를 구하기 위해서는 각 x좌표 별로 직사각형에 포함되는 y영역과 그렇지 않은 영역을 구분해야 합니다. 이를 구분하기 위해서 기존 방식의 Segment Tree보다는 구간 Update query를 통해 현재 활성화 된 직사각형의 개수가 몇 개인지 구간 별로 관리하고, 넓이를 단번에 파악할 수 있..

목차 개요 설명 코드 개요 시청자가 어떠한 패턴으로 영상을 감상하는지 정보가 주어질 때, 어느 구간에서 가장 좋은 광고 효과를 낼 수 있는지 찾아내는 문제입니다. 이 문제의 Key point는 00:00:00 ~ 99:59:59 의 시간을 하나의 배열 (0 ~ 359999)로 표현하고, $O(N)$의 복잡도로 결과를 찾아내는 것입니다. 사용자의 play time이 주어지면 0 부터 359999 사이의 값으로 환산 한 뒤, 각 배열 원소 (1초)마다 총 몇 명이 시청하는지 저장합니다. 이후, 광고 삽입 시간을 0부터 359999까지 차례로 조사하면서 총 시청 인원이 가장 많은 구간을 구하면 되겠습니다. 설명 다음과 같이 간단한 예제와 그림을 통해서 살펴보도록 하겠습니다. 재생 가능한 시간 0 : 00 ~ ..

목차 개요 설명 코드 개요 어떤 tree가 주어졌을 때, 임의의 node에서 자신 혹은 자식 노드들 중에서 하나만 선택하면서 그 선택의 비용의 최솟값은 얼마인가를 구하는 문제입니다. 이 문제는 Tree DP인데, 특정 노드를 선택하는 Tree DP 특징 중에 하나로는 자신의 노드가 선택 되었는지, 안되었는지 구분해서 구하는 문제가 많습니다. 각각의 배열을 dpYes (dpYes[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택 되었을 때 그 비용) dpNo (dpNo[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택되지 않았을 때 그 비용) 로 구분하여 구하면 되겠습니다. 이 때, dpYes는 자식들을 순회하면서 min(dpYes[child], d..

목차 개요 설명 코드 개요 정확성과 효율성을 동시에 체크하는 문제입니다. 무지와 어피치는 같이 택시를 합승해 어느 지점까지 이동한 뒤에, 각자 개인 택시를 이용하여 집으로 귀가합니다. 시점은 동일하고 중간 경유지까지 함께 간 뒤에 헤어져 각자의 목적지로 향하는 방식입니다. 따라서 직관적으로 (출발지 → 경유지), (경유지 → 무지의 집), (경유지 → 어피치의 집) 의 합이 최소가 되도록 하는 "경유지"를 구한 뒤, 비용을 계산하면 됩니다. $$Answer =min( d[S,\ l]\ +\ d[l, \ A]\ +\ d[l,\ B])$$ 여기서 $l$은 경유지 입니다. 플로이드 워셜을 사용하면 모든 시점 → 종점의 비용을 계산할 수 있습니다. 그러나 시간복잡도는 $O(V^3)$으로 상당한 시간복잡도를 지니..