노는 게 제일 좋아

플로이드 알고리즘으로 해결했다. 플로이드를 조금 더 풀어봐야겠다. https://www.acmicpc.net/problem/11403 #맞는 풀이 #include #define MAX 101 using namespace std; int N; int adj[MAX][MAX]; void floyd() { //i -> j는 바로 안가도 다른 노드를 거쳐서 가도 된다. //i -> k -> j 가능 for (int k = 1; k N; for (int i = 1; i adj[i][j]; //방향 그래프임. } } floyd(); for (int i = 1; i

한 번 갔던 간선에 대해 다시 갈 수 있으므로 연결해줄 때 양방향으로 연결해줘야 했다. 남들은 잘보이지만 나는 이것만 30분 넘게.. 걸렸다. 그리고 어차피 최단경로 = 최단경로 + 최단경로라고 생각해도 된다. https://www.acmicpc.net/problem/1504 #맞는 풀이 #include #include #include #include #include #include #define MAX 803 #define INF INT_MAX using namespace std; int N, E; vector adj[MAX]; //인접행렬 long long dist[MAX]; long long dist1[MAX]; //v1을 위한 long long dist2[MAX]; //v2를 위한 int v1, ..

다익스트라의 개념이 조금 더 나아간 것이다. 최단거리로 갱신했을 때는 해당 경로가 정해진다는 것을 기록하면 되는 문제다. https://www.acmicpc.net/problem/11779 #맞는 풀이 #include #include #include #include #include #include #define MAX 1002 #define INF 987654321 using namespace std; int st, ed; int N, M; int dist[MAX]; vector adj[MAX]; int path[MAX]; void dijkstra() { dist[st] = 0; priority_queue heap; heap.push({ dist[st], st }); while (!heap.empty()..

다익스트라 알고리즘 또 까먹었다. 오늘은 3문제 정도 풀어봐야겠다. https://www.acmicpc.net/problem/1916 #맞는 풀이 #include #include #include #include #include #define MAX 1001 // 1000개 정도면 인접행렬 만들만하다. #define INF 987654321 //적당히 큰 숫자여야한다. using namespace std; int N; //도시 수 int M; //버스 수 int st, ed; //시작노드, 목표노드 vector adj[MAX]; //벡터를 넣는 배열 {거리, 노드} int dist[MAX]; //최소거리 테이블 void dijkstra(){ dist[st] = 0; //전역으로 시작노드를 받음. prior..

우선 이 알고리즘을 쓰기 위해서는 몇가지 조건이 필요하다. 1. 각 간선에 대한 가중치가 음수여선 안된다. -> 양수여야만 한다. 2. 단일 시작점에 대한 최단 경로이다. -> 해당 시작점에 대해서만 최단경로고 다른 vertex는 다시 돌려야 한다. 3. 프림의 MST 알고리즘과 유사한 형태다. -> 프림 알고리즘은 경계로부터의 최소 거리를 정점의 거리 값으로 설정 -> 다익스트라에서는 시작 정점으로부터 각 정점까지의 전체거리 사용 -> 다익스트라에서는 목적 정점만 파악하면 종료 아무튼 조금 다르다. 우선 기본적으로 해야 할 것들을 알아보자 1. 모든 정점에 대해서 거리 값을 무한대로 초기화한다 -> 계산하지 않았음을 의미한다. 2. 시작정점 자기자신과의 거리는 0이므로 0으로 설정한다. 3. 모든 거리..

어렵다기 보다.. 엄두를 못냈다. 사실 DP란 것을 알았으면.. N번째부터 생각해봤을텐데.. 그게 안된다. https://www.acmicpc.net/problem/9465 #맞은 풀이 #include #include #include using namespace std; int sticker[2][100002]; int dp[2][100002]; // DP int tc; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //테스트케이스 여러개 while(tc--){ //해당 테스트케이스에 대한 입력 int length; cin >> length; //DP 초기화 for(int i = 0; i

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 어떻게 구현할까? 의 선택지에서 DFS를 골랐다면 고생을 덜 할 것이었다 https://www.acmicpc.net/problem/14500 #맞는 풀이 #include #include #include using namespace std; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int map[500][500]; bool visited[500][500]; // 멍청했따.. 어차피 4칸을 사용하는 건데... DFS로 풀었으면 되었다는 힌트를 듣고.. 현타온다. //즉 DFS로 4칸 탐색하는 과정에 일자 모양도 있고 네모도있고 기역자도 있다. //다만 ㅗ 모양만 DFS로 탐색은 불가능하다. in..

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 범위에 신경쓰도록 사용자 입력만이 범위가 아니란 것을 명심하자 https://www.acmicpc.net/problem/21608 #맞는 풀이 #include #include #include #define X first #define Y second using namespace std; int seat[21][21];//자리 배치 1~N만 쓸 것임 int dx[4] = { 1,-1,0,0 }; //방향 int dy[4] = { 0,0,1,-1 }; //방향 int good[5] = { 0,1,10,100,1000 }; //점수 int N; vector info[401]; //학생 번호와 선호하는 학생을 저장 int main() { cin >> N; i..

그냥 시키는 대로 하면 된다. 다만 빼먹으면 안된다. 모든 조건을 빼먹으면 안된다. https://www.acmicpc.net/problem/20055 #맞는 풀이 #include #include #define X first #define Y second using namespace std; using ll = long long; int N, K; // 칸과 제한 deque deq; // 로봇이 있는지 1,0 내구도 int int main() { cin >> N >> K; int num = 2 * N; while (num--) { int x; cin >> x; deq.push_back({0,x }); //로봇이 없는 채로 deq 초기화 } int stage = 0; while (1) { stage++;/..

사실 처음 들었을 때 이분그래프의 정의가 알아듣기 힘들었다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. ??음.. 무슨 말이지?? 즉, 나는 내 집합의 정점과 연결되면 안된다...? 그렇다. 그냥 색을 2가지로 칠할 수 있을 때 인접한 노드가 나와 같은 색을 가지면 안된다는 말과 같다. https://www.acmicpc.net/problem/1707 #맞은 풀이 #include #include #define X first #define Y second #define MAX 20001 using namespace std; int K; // 테스트케이스 수 in..