본문 바로가기

전체 글105

[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.
[BOJ] 백준 13537번: 수열과 쿼리 1 머지 소트 트리 + 이분탐색 아래글 참고. 2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m, k; int arr[100001]; int mst[17][100002] = { 0, }; void make_tree(int s, int e,int depth) { if (s == e) { mst[depth][s] = arr[s]; } else { int mid = (s + e) / 2; make_tree(s, mid, depth + 1); make_tree(mid + 1, e, de.. 2020. 6. 22.
[BOJ] 백준 11408번: 열혈강호 5 MCMF (minimum cost maximum flow) 알고리즘을 사용하는 문제. 할 수 있는 일을 매칭하기 위하여 NF (Network Flow) 를 수행, 이 때 최소 비용을 구하기 위하여 SPFA + SLF 수행 #include #include #include #include using namespace std; int n, m; int ca[802][802]; int fl[802][802]; int cost[802][802]; int S = 0, D = 801; vector v[802]; int main() { cin >> n >> m; for (int i = 1; i > mo; cost[i][w + 400] = mo; cost[w+400][i] = -mo; v[i].push_back(w + .. 2020. 6. 22.
[BOJ] 백준 1865번: 웜홀 SPFA + SLF 로 풀었지만 일반적인 벨만포드 알고리즘이 더 빠름 웜홀 시작점을 저장하여 탐색하며 update 횟수를 cycle 배열에 저장하여 노드 수 이상 업데이트 되면 음의 사이클 [!] 노드 수가 N개일때 N개를 전부 탐색하는 path는 n-1 개이다 n번 탐색이 된 경우는 n-1번 움직였을때보다 최소의 경로 비용을 뜻하므로 음의 간선이 있음 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; void solve() { int n, m, w; vector v[501]; vector list; cin >> n >> m >> w;.. 2020. 6. 19.

티스토리툴바