반응형 알고리즘11 [cpp 알고리즘] 백준 1992 쿼드트리 [백준] 1992 쿼드트리 풀이 분할정복, 재귀 문제 출처: https://www.acmicpc.net/problem/1992 문제 요약 - 모두 0으로만 되어 있으면 압축 결과는 "0" - 모두 1로만 되어 있으면 압축 결과는 "1" - 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지 않고, "왼쪽 위/ 오른쪽 위/ 왼쪽 아래/ 오른쪽 아래" 4개로 나누어 압축하고, 이 4개의 영역을 압축한 결과를 괄호 안에 묶어서 표현 예시 문제의 경우: (0(0011)(0(0111)01)1) 로 표현된다. 풀이 정리 1. 모두 0인지 확인, 모두 1인지 확인, 그렇지 않다면 분할정복 2. 분할정복 할 때 n=1인 경우는 먼저 종료시키고 아니면 1의 과정을 반복한다. c++ 코드 #include #include.. 2023. 11. 8. 네트워크 플로우(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 알고리즘] 백준 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. 이전 1 2 3 다음 반응형
