그냥 하는 노트와 메모장

* BOJ 1742 레이싱 결과[분류 : 다이나믹 프로그래밍, DAG, 그래프 이론, 조합론] [풀이] 1. [그래프 구조] 먼저 구성되는 컴포넌트의 구조는 양방향 그래프가 아닌 DAG(Directed Acyclic Graph)이어야 한다. 즉, 사이클이 존재하면 모순이 발생하므로 경우의 수는 0이 돼야 한다. 2. [컴포넌트 집합] 하나의 컴포넌트에 여러 노드가 존재할 수 있다. 따라서 같은 컴포넌트에 있는 노드를 집합으로 둔다. 3. [진출 간선?] 나는 경기결과를 작성할 때 맨 뒤에서 시작해서 작성하는 걸 채택했다. 구성되는 dag 컴포넌트에서 진출 간선이 0인 것들부터 넣는 방식을 생각해보자. 진출 간선이 없다는 의미는 더 이상 자신이 반드시 이기는 상대가 존재하지 않는다는 뜻이다. 따라서 리프(..

* BOJ 11097 도시계획 (https://www.acmicpc.net/problem/11097) [ 분류 - SCC(Strongly connected components) ] 다소 까다로운 문제? 였다. 반면 접근 방식이 매우 여러가지라 아래 해설도 그 중 하나라고 봐주시면 되시겠당 :) 문제가 물어보는 것은 플로이드의 결과라고 생각할 수 있는 인접 행렬이 주어졌을 때, 이를 구성할 수 있는 가장 적은 도로를 쓰는 도로망을 구성하는 것이다. 그리고 일방통행 도로이기 때문에 방향 그래프인 것을 알 수 있다. 이 문제를 "최대한 도로를 지우는" 과정으로 볼 수 있다. 인접 행렬에서 지울 수 있는 도로를 모두 지워야 최소 크기의 도로망을 구성할 수 있기 때문이다. 임의의 정점에 대해서 생각해보자. 정점 ..

* 강한 연결 요소(SCC, Strongly connected components) 문제들 Topological sort, dynamic programming, DSU 등 다양한 알고리즘과 연결하여 풀 수 있는 문제들을 Random하게 소개해 보겠당. 1. 백준 온라인 저지 1-1. Strongly connected component(https://www.acmicpc.net/problem/2150) 기본적인 SCC 문제다. 모든 SCC를 저장하고 이를 정렬하여 출력하면 된다. - 코드 #include #include #include #include using namespace std; int min_v(int a, int b) { return a < b ? a : b; } vector adj; int ..

* 강한 연결 요소 (SCC, Strongly connected components) 방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 말한다. if vertex u has paths to vertex v and also v has paths to u, either u and v are involved in same SCC. 이 SCC 집합은 하나의 component 내에 여러개가 생길 수 있다. 아래 그림을 보면 하나의 component에 대해 3개의 SCC가 있음을 직관적으로 알 수 있다. SCC의 특성 중 하나는 SSC 간의 방향 그래프를 그려보면 DAG가 나온다는 것이다. 이는 연역적으로 정리가 가능하다. 1. 현재 구성할 수 있는..

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다. 1. 이진 트리다. 2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다. 하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다. 정확히는 DAG(Directed acyclic graph)를 나타낸다. 따라서 나는 세 단계를 거쳐 AC를 받게 됐다. 1. MLE 2. TLE 3. AC (만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.) * 기본 아이디어 그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터..