분류 전체보기 (97) 썸네일형 리스트형 [알고개념] 5. Strongly Connected Component 이 글은 https://blog.naver.com/kks227/220802519976 을 참고하여 작성하였습니다. 1. SCC의 개념 SCC는 그래프 내의 모든 두 정점에 대해서 도달할 수 있는 경로가 존재하는 그래프를 의미한다. 아래 그래프에 대해서 {a, b, e}, {f, g}, {c, d, h}가 각각 하나의 SCC를 이룬다. SCC는 Maximal한 성질을 갖는다. 즉, 아래에서 c, d만 포함해도 경로가 존재한다는 성질은 만족되지만 h까지 포함해야 최대 크기의 SCC이기 때문에 반드시 h를 포함해야 한다. 2. 타잔 알고리즘 그래프에서 SCC를 찾는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 존재한다. 그 중에서 타잔 알고리즘을 알아보자. 그래프의 각 컴포넌트에 대하여 DFS를 돌려서 D.. [알고연] (4주차-2) 768B. Code For 1 768B. Code For 1 Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a traine.. [알고연] (4주차-1) 448C. Painting Fence 448C. Painting Fence Bizon the Champion isn't just attentive, he also is very hardworking. Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height o.. [알고연] (3주차-3) 160A. Twins 160A. Twins Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like. Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hast.. [알고연] (3주차-2) 158B. Taxi 158B. Taxi After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group sh.. [퐁키] 퐁키를 루디 욕조에 빠뜨렸더니.. https://youtu.be/QXuAE_KyTWY [220321] 백준 450문제 달성 군대가기 약 한달 전 450문제를 달성하였다. 최근 한달간은 알고리즘 스터디를 통해서 문제를 많이 풀어서 꽤 빨리 올릴 수 있었다. 특히 알고리즘 중급 스터디에서 플래티넘 이상의 문제를 풀어서 티어도 많이 오르게 되었다. 450번째로 푼 문제도 Strongly Connected Component (2150번) 로, 스터디에서 공부하는 알고리즘 문제다. 이제 군대가기 전까지 500문제를 달성하는 것이 목표이다. [PS] 백준 #11661. 해의 개수 문제 정보 난이도: 플래티넘 I 문제 주소: https://www.acmicpc.net/problem/11661 이 문제를 푼 이유: 알고리즘 스터디 - 유클리드 호제법 문제 방정식 Ax + By + C = 0의 해의 개수를 구하는 프로그램을 작성하시오. A, B, C, x, y는 모두 정수이고, x1 ≤ x ≤ x2, y1 ≤ y ≤ y2인 해의 개수를 구해야 한다. 나의 풀이 자세한 개념은 https://pongkijoa.tistory.com/91 이 글에 작성해두었다. $d = gcd(a,b)$라 하자. 먼저 유클리드 호제법을 이용하여 a와 b의 최대공약수 d를 구한다. 유클리드 호제법을 역산하여 d를 a와 b의 일차결합 형태로 나타낸다. 이 때의 특수해를 $x_1, y_1$ 이라 하자. $ax +.. 이전 1 2 3 4 5 ··· 13 다음
