Solved.ac26 [BOJ] 백준 2150번: Strongly Connected Component https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 강한 연결 요소 (SCC, Strongly Connected Component) 알고리즘은, v에서 u로가는 경로가 있을 때, 반대로 u에서 v로 갈 수 있는 경로가 존재하는 최대의 그룹 크기를 찾는 알고리즘입니다. 코사라주 알고리즘과 타잔 알고리즘으로 강한 연결 요소를 찾을 수 있는데, 본 포스팅에서는 코사라주 알고리즘에 대하.. 2020. 7. 17. [BOJ] 백준 2098번: 외판원 순회 TSP (traveling salesman problem) 로 잘 알려진 외판원 순회문제는 NP-Hard 문제로, 마을의 수 n에 대해 다항식의 형태로 복잡도가 계산될 수 없다. 그래서 N의 개수가 매우 적고, 비트마스크를 사용하여 방문한 마을을 1로 표기하여 001011 처럼 1,2,4 번째 마을을 방문했다를 표현할 수 있다. TSP는 시작점을 어느 마을로 하든 동일한 값이 나오기 때문에 시작 마을을 인덱스 0으로 편의상 둔다. if (state == (1 2020. 6. 25. [BOJ] 백준 1509번: 팰린드롬 분할 Class 5에는 대부분 DP로 구성된 것 같네요 recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면 i = e) { return pal[s][e] = 1; } int& ret = pal[s][e]; if (~ret) return ret; ret = 0; if (str[s] == str[e]) { return ret = ispal(s + 1, e - 1); } return ret; } int recv(int node) { if (node == n) { return 0; } int& ret = dp[node]; if (~ret) return ret; ret = 2e9; for (int i = node; i < n; i++) { if (ispal(node, i.. 2020. 6. 25. [BOJ] 백준 14939번: 불 끄기 첫 줄에서 스위치를 누를수 있는 모든 경우 (1024가지)를 미리 정해놓고 두번째 줄부터 이전 줄의 전구의 켜짐 상태를 그리디하게 끄면서 마지막 줄에 켜진 전구의 유무로 경우의 수를 구하는 문제 #include #include #include #include #include #include #include #define INF (10001) using namespace std; typedef pair pii; typedef long long ll; int nx[5] = { 0,0,0,-1,1 }; int ny[5] = { 0,-1,1,0,0 }; char map[11][11]; char tmp[11][11]; void click(int x, int y) { for (int i = 0; i < 5; i++.. 2020. 6. 23. 이전 1 2 3 4 5 6 7 다음
