컴공생 일상 블로그 컴공생 일상 블로그

조합, 순열, 중복 조합 등 (실버)N과 M(1) https://www.acmicpc.net/problem/15649 ✅ 07.15N과 M(2) https://www.acmicpc.net/problem/15650  ✅ 07.15N과 M(3) https://www.acmicpc.net/problem/15651  ✅ 07.16N과 M(7) https://www.acmicpc.net/problem/15656  ✅ 07.16N과 M(9) https://www.acmicpc.net/problem/15663  ✅ 07.17N과 M(11) https://www.acmicpc.net/problem/15665  ✅ 07.17 백트래킹 활용 (실버)스타트와 링크 https://www.acmicpc.net/problem/1..

문제https://www.acmicpc.net/problem/11408 MCMF문제, 최대유량 + SPFA기존의 flow문제에 대해서 mcmf를 추가해 탐색하는 느낌SPFA에서는 음의 사이클 존재에 대해 체크하기 위한 코드가 있는데, MCMF문제에서는 필요 없는듯?(그렇다고 한다. - https://www.acmicpc.net/board/view/1291) 코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;int capacity[808][808];int flow[808][808];int cost[808][808];//0 source//1 ~ 400 pers..

SCC, 강한 연결 요소(Strongly Connected Componet)방향이 존재하는 유향 그래프에서 서로 강하게 연결된 부분 집합을 의미, 강하게 연결되있다 -> 사이클이 형성된다.설명보다 아래 그림을 보면 쉽게 이해된다. 각각의 영역이 SSC를 이룬다. 코사라주 알고리즘(Kosaraju's Algorithm)1. 입력된 그래프에 대해 역방향 그래프를 만듬2. 그래프에 대해서 DFS를 수행하고, 끝나는 순서대로 스택에 push3. 스택을 하나씩 pop하면서 역방향 그래프에서 DFS를 수행- 이미 방문한 정점의 경우 pop만 수행- 방문하지 않은 정점에 대해 DFS를 수행하고, 이 때 탐색되는 정점들이 하나의 SCC 동작 방식0.  Input, 그래프와 역방향 그래프를 생성해준다.# Input7 9..

문제1738번 골목길: https://www.acmicpc.net/problem/1738 오랫만에 고통 좀 받은 문제, 얼른 풀고 SCC공부하려 했는데 시간 다 뺏김 ㅜㅜ 양 또는 음의 가중치를 가지는 그래프에서 사이클을 판별하고 경로 추적을 하는 문제 (그래프, 벨만-포드)벨만 포드는 몰라서, SPFA로 품   풀이1. 역방향 그래프를 생성해서 BFS를 돌려 해당 정점에서 N정점에 도달 가능한지 여부를 판단만약 해당 정점이 N정점에 도달하지 않는 정점이라면 1에서 N정점간의 비용을 구할 때 고려하지 않아도 된다. (사이클이 존재하지만 정답을 출력하는 경우!)2. SPFA 돌리기, SPFA 경로추적은 몰라서 그냥 다익스트라처럼 비슷하게 추적함if(check[nxt.n] == 0) continue; 와 같..

문제https://www.acmicpc.net/problem/11406 풀이Network flow 문제, Network flow는 각 제한들을 어떻게 capacity로 줄 것인지 생각하면서 풀어야 하는듯그냥 많이 풀어보면서 다양한 유형을 접해봐야할듯...그래도 이 문제는 금방 풀었다. 각각의 입력(사려하고 하는 책의 개수, 사람이 서점에서 구매할 수 있는 책의 개수, 서점이  가진 책의 개수)을 다음과 같이 간선에 매핑하고, capacity를 준 뒤 풀면 된다. 코드#include #include #include #include #include #include #include #include using namespace std;int N, M;int capacity[401][401];int flow[40..

SPFA, Shortest Path Faster AlgorithmSPFA는 최단 경로 알고리즘으로, MCMF(Mininum Cost Maximun Flow)를 구현할 때 사용된다.BFS와 벨만포드 알고리즘을 섞은 것과 비슷하다. 모든 간선의 가중치가 같은 그래프에서 SPFA를 수행하면 BFS와 똑같이 동작한다. 최단 경로 알고리즘다익스트라: O(ElogV)로 동작하지만, 음수 간선은 처리 불가플로이드-와셜: 음수 간선은 처리 가능하지만, 모든 정점들간의 거리를 구하는데 사용되고 O(V^3)으로 동작벨만-포드: 음수 간선 처리 가능, O(VE) 음수간선이 포함된 사이클이 존재한다면, 비용은 점점 작아져 -INF가 된다.해당 정점이 N번 이상 방문되었는지를 체크하여, 음수사이클의 존재 여부를 확인할 수 있다..

https://school.programmers.co.kr/learn/courses/30/lessons/214293 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  구현자체는 어렵지 않은데, 최단 경로를 이루는 경로 중 유일 경로임을 판별하여하는 부분이 어려웠던 문제최근데 다익스트라 문제를 잘 안풀어서, 역방향 탐색할 생각 조차 안 떠올라 시간 좀 썼습니다.  문제 설명 암튼 간단히 요약하자면... 다음과 같다.1. 도로의 비용은 도로의 길이와 도로의 교통량의 합이다.2. 간선하나에 대해 교통량이 증가/감소 할 수 있고, 이 교통량에 따라 최소 비용이 바뀔 ..

https://school.programmers.co.kr/learn/courses/30/lessons/67260 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 프로그래머스 플랫폼에 다시 적응할 겸, 간간히 프로그래머스도 풀려고 하는 중!옛날에는 프로그래머스 3Lv도 엄청 어렵다 싶었는데, 또 풀만 한 것 같기도 하고...대충 백준 골드? 1, 2, 3?? 모르겠다. tc 하나가 pass가 안돼서 좀 걸렸다. ㅜㅜ 문제에서 방문 순서 조건을 A->B 유일로 주었기 때문에아직 방문할 수 없는 노드를 탐색하게 되면 맵에 저장해 둔다. 그 외의 경우는 정상적으로 ..