플로이드 워셜 주의해야할 점(k > i > j 순서로 돌기)

2224번: 명제 증명 명제가 주어질때 참으로 가능한 명제들을 모두 출력하는 문제 p => p같은 전건과 후건이 같은 명제는 출력하지 말고 삼단논법에 의해서만 참이 될 수 있는 명제만 출력하는 문제 전건 후건으로 가능한 것은 알파벳 대소문자이고 총 52개여서 이를 노드 번호로 바꿔주고 from sys import stdinn = int(stdin.readline())node = {chr(i+65):i for i in range(26)}for i in range(26,52): node[chr(i+71)] = ichange = {v:k for k,v in node.items()}  A => b,  b => C이면 A노드에서 b노드로 갈 수 있다는 의미이고, b노드에서 C노드로 갈 수 있다는 의미..

• format_list_bulleted 최단거리 알고리즘
• · 2025. 1. 11.
• textsms

그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

1. 문제 정확히 하나의 사이클을 포함하는 무방향 연결 그래프(connected undirected graph)가 주어진다. 각 노드 번호가 0부터 n-1까지 n개의 노드를 가진다. 노드 a와 b 사이 거리가 a에서 b로 가기 위해 필요한 최소 간선의 수 노드 i = 0,1,2,..,n-1에서 이 그래프에 존재하는 사이클에 있는 임의의 노드까지의 최소 거리를 구한다면? 당연히 사이클에 포함된 노드는 사이클 까지의 거리가 0이다.   위 그래프는 1,2,3,4가 사이클을 이룬다. 1,2,3,4는 각각 사이클까지 거리가 0이고, 0번 노드는 사이클 까지 거리가 1 5번 노드는 사이클 까지 거리가 1, 6번 노드는 사이클 까지 거리가 2이다.  2. 풀이 사이클에 포함된 노드는  위상정렬에 포함되지 않는다는 ..

• format_list_bulleted 위상정렬
• · 2024. 11. 13.
• textsms

그래프에서 서로 연결된 세 정점의 차수 합의 최솟값 찾기

17089번: 세 친구 (acmicpc.net) 서로 친구인 a,b,c에 대하여 a의 친구 수 + b의 친구 수 + c의 친구 수가 최소가 되도록 만들고 싶다. a의 친구 수에는 b,c는 제외해야한다. 마찬가지로 b,c의 친구 수에는 a,c, a,b는 제외해야한다. a의 친구 수 + b의 친구 수 + c의 친구 수 - 6의 최솟값을 찾아야한다는 소리 친구 관계를 그래프로 만드는데 각 정점에 연결된 정점을 set()으로 만들어서 O(1)로 서로 친구인 정점을 찾도록 만들자 from sys import stdinn,m = map(int,stdin.readline().split())graph = [set() for _ in range(n+1)]for _ in range(m): a,b = map(int,s..

• format_list_bulleted 브루트포스
• · 2024. 9. 10.
• textsms

군집을 찾는 알고리즘2 - Louvain algorithm

주어진 그래프의 개별 정점에서부터 점점 군집을 병합해가는 상향식 알고리즘  1. first phase - modularity optimization 처음 주어진 상태에서는 개별 node 1개씩이 하나의 군집이라고 생각 특정 node i를 그것의 이웃(neighbor)인 j에 병합시키면서 modularity의 변화량을 계산함 원래 상태의 modularity와 이웃인 j에 병합시킨 뒤 modularity의 차이를 계산한다. 병합시키면 군집이 생기니까 modularity는 최소한 감소하지는 않음 이 때 최대로 modularity가 증가하는 이웃 j가 있을 것인데 그곳에 i를 포함시킨다. 증가하는 경우가 없다면 어떠한 곳에도 포함시키지 않는다. 다시 다른 node v를 선택하여 위 과정을 반복, 모든 node에..

• format_list_bulleted Graph
• · 2024. 9. 4.
• textsms

그래프 전파 모형3 - 전파 최대화 문제(influence maximization)

1. viral marketing 소비자들로 하여금 상품에 대해 긍정적인 입소문을 내게하는 기법 효과적으로 상품 정보가 소비자들에게 알려질려면 소문의 시작점이 중요하다. 시작점에 따라 입소문이 전파되는 범위가 달라지기 때문이다.  2. importance of seed set SNS 인플루언서들이 높은 광고비를 받는 이유가 있다. 전파 모형에서 첫 시작점을 seed set이라고 부르는데 viral marketing에서는 이 시작점을 잘 선택해야 광고 효과를 극대화할 수 있다.   케이트 미들턴을 광고 모델로 선택했더니 판매량이 급증했다 선형 임계치 모형에서도 seed set의 중요성을 볼 수 있는데 처음에 u와 v를 선택했을 때 총 9명(7명 전파)이 A를 선택했다.    만약 위 모형에서 다음과 같이 ..

• format_list_bulleted Graph
• · 2024. 9. 2.
• textsms

군집을 찾는 알고리즘1 - Girvan-Newman algorithm

1. idea 군집을 찾는 대표적인 하향식 알고리즘으로 전체 그래프에서 시작하여 군집들이 서로 분리되도록 link를 순차적으로 제거함 서로 다른 군집을 연결하는 다리 역할을 하는 link를 먼저 제거해나가야 군집들이 분리 될 것이다.   2. betweenness centrality 그래프의 임의의 두 node의 최단 경로 위에 특정 link가 몇번이나 놓이는지 계산    link A-B는 양 옆 4개의 node중 하나를 선택하여 만든 최단 경로에 모두 존재해야하므로 4*4=16가지가 있다. 따라서 그림을 보면 직관적으로 betweenness centrality가 높은 link는 두 군집을 연결하는 다리 역할을 할 가능성이 높다.   3. algorithm 주어진 그래프에서 모든 link의 매개 중심성을..

• format_list_bulleted Graph
• · 2024. 9. 1.
• textsms