반응형 알고리즘42 네트워크 플로우(Network Flow) 알고리즘, 포드-풀커슨 (Ford-Fulkerson) 네트워크 플로우(Network Flow) 알고리즘이란? - 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘 - 그래프 내 source 정점에서 유량을 발생시켜 간선을 통해 sink 정점에 도달시키는 것이 목표 = 최대 유량(Maximum Flow) 알고리즘 기본 용어 정리 용량 (Capcity, c(u,v)) : 정점 u에서 v로 가는 간선에 흐를 수 있는 최대 유량(가중치) 유량 (Flow, f(u,v)) : 정점 u에서 v로의 간선에 실제로 흐르는 유량 잔여 용량 (Residual Capacity: r(u,v)) : c(u,v) - f(u,v) 소스 (Source) : 유량이 시작되는 정점 싱크 (Sink) : 모든 유량이 도착하는 정점 증가 경로 (Augm.. 2023. 5. 22. [cpp 알고리즘] 백준 11046 팰린드롬?? [백준] 11046 팰린드롬?? cpp 풀이 매내처, manacher's, 문자열 문제출처: https://www.acmicpc.net/problem/11046 11046번: 팰린드롬?? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 요약 - 자연수 N개(1> s >> e; s--; e--; if (A[s+e+1] >= e-s+1) cout 2023. 5. 17. [cpp 알고리즘] 백준 10942 팰린드롬? [백준] 10942 팰린드롬? cpp 풀이 DP, 다이나믹 프로그래밍 문제 출처: https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 요약 - 자연수 N개(1> M; for(int i=1; i s >> e; if(dp[s][e] == 1) cout 2023. 5. 6. [cpp 알고리즘] 백준 22984 반짝반짝2 문제 풀이 1. 첫번째는 어떻게든 0과 1의 배열의 모든 경우의 수가 2^N만큼 있으면 이를 비교해서 문제를 풀 수 있을 거라 생각했는데 0과 1의 배열의 모든 경우의 수를 구할 때 O(2^N) 으로 시간초과가 발생한다. 이를 비교해서 문제를 푼다는 것은 불이 켜졌다는 의미인 1의 개수 + 연속되는 두 수가 00,01,10,11인 경우에 대해 추가 카운트를 더한 후에 이 때의 확률을 곱하면 된다고 생각했다. 2. 그래서 배열에 저장해서 값을 바로 이용하면 될 거라 생각했지만, 메모리가 2^N만큼 발생할 것이고, N의 최대 크기가 100000이기 때문에 메모리 초과가 발생할 것이라 생각했다. 3. 이에 dp를 사용해보자고 생각해서 dp[i][j]를 이용해 i번째 까지 전구에 대해서 끈 경우를 j=0, 켠 .. 2022. 9. 13. 이전 1 ··· 4 5 6 7 8 9 10 11 다음 반응형
