Problem Solving/BOJ 백준 (132) 썸네일형 리스트형 [ BOJ 백준 7570번 - 줄 세우기 ] 해설 및 코드 https://www.acmicpc.net/problem/7570 목적 맨 앞이나 맨 뒤로 이동시키는 어린이의 수를 최소로하여 n명의 어린이를 번호 순으로 줄 세우자. 접근법 1. 최적의 선택으로 어린이를 맨 앞이나 맨 뒤로 이동시키게 되면, 일련의 연속된 순서로 정렬이 되어야 할 것이다. 정렬 과정을 거꾸로 보자. 6명의 어린이가 있고 1명의 어린이만 맨 뒤로 보내면 되는 상황이다. 6번 어린이를 맨 뒤로 보냄으로써 1에서 5까지 연속된 배열의 길이가 1 증가하여 정렬이 마무리 된다. 이전 상황으로 1에서 4까지 일련의 연속된 배열이 있다. 이 배열의 길이를 증가시키기 위해선 2명의 어린이를 앞 또는 뒤로 이동시켜야 하고 5가 이동하여 1~5의 배열을 형성하게 된다. 한번 더 이전으로 가면 2에서 4까.. [ BOJ 백준 4013번 - ATM ] 해설 및 코드 https://www.acmicpc.net/problem/4013 목적출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 구하자. 접근법1. 백준 2152 - 여행 계획 세우기 와 유사한 문제이다. SCC를 응용한 문제이며, 코사라주 알고리즘과 BFS로 최대값을 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include#define f(i,l,r) for(int i=l;in>>m; while(m--){ int a,b;cin>>a>>b;.. [ BOJ 백준 2152번 - 여행 계획 세우기 ] 해설 및 코드 https://www.acmicpc.net/problem/2152 목적 단방향인 비행기 경로가 m개 주어질 때, S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하자. 접근법 1. SCC이론과 연관되어 있는 문제이다. 2. SCC를 하나의 정점이라고 하고 이러한 정점의 가중치를 요소의 개수로 가정할 수 있다. 이 때, S번 도시가 포함된 정점에서 T번 도시가 포함된 정점으로 가는 경로의 최대값을 구하면 된다. 3. 우선, 코사라주 알고리즘으로 SCC를 구한다. 정점마다 자신이 속해있는 SCC의 번호를 할당하고, 각 SCC의 요소 개수를 구하자. 4. SCC를 정점으로 하는 간선을 구하고, 이를 이용하여 BFS로 최대 경로를 구한다. (BFS에서 메모리 초과를 방지하기 위해.. [ BOJ 백준 3977번 - 축구 전술 ] 해설 및 코드 https://www.acmicpc.net/problem/3977 목적 A구역에서 B구역으로 이동하게 하는 움직임이 주어질 때, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾자. 접근법 1. 코사라주 알고리즘으로 찾은 첫번째 SCC가 정답의 후보이고, 이 SCC에서 다른 모든 정점으로 갈 수 있다면 정답이 된다. 2. dfs만 신나게 돌리자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #define f(i,l,r) for(int i=l;i>tc; while(tc-.. [ BOJ 백준 3682번 - 동치 증명 ] 해설 및 코드 https://www.acmicpc.net/problem/3682 목적 명제의 수 n과 증명된 함축 m개가 주어질 때, n개의 명제가 동치가 되기 위해 증명해야할 최소 함축의 개수를 구하자. 접근법 1. x개의 SCC를 1개로 만들기 위해 필요한 간선의 개수를 구하면 된다. 2. 그래프 내의 모든 정점이 사이클을 형성해야 하므로, 정점의 in-degree가 0인 정점의 개수와 out-degree가 0인 정점의 개수 중 최대값이 필요한 간선의 개수이다. 다시 말해 사이클을 형성하기 위해선, in-degree와 out-degree가 0인 정점이 하나도 없어야 한다. 3. 위와 같이 사이클을 형성하기 위한 조건을 알면 아주 쉬운 문제였다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.. [ BOJ 백준 4196번 - 도미노 ] 해설 및 코드 목적 배치되어 있는 도미노 블록간의 관계가 주어질 때, 모든 블록을 넘어뜨리기 위해 최소 몇 개의 블록을 넘어뜨려야 하는지 구하자. 접근법 1. 결론부터 말하면, 위상정렬을 해준 후에 dfs를 수행하면 된다. (dfs 두번..) 2. 위상 정렬은 사이클이 없는 방향그래프(DAG)에 적용될 수 있지만, 사이클을 형성하는 정점들 간의 위상은 고려하지 말자. 위상 정렬을 한 뒤에는 시작 정점에서 끝 정점 순으로 정렬이 될테니, 정렬된 순으로 dfs 탐색으로 이어지는 다음 정점들을 제거하면서 그래프의 시작 정점들을 카운트 해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 .. [ BOJ 백준 11097번 - 도시 계획 ] 해설 및 코드 https://www.acmicpc.net/problem/11097 목적 방향 그래프의 인접 행렬이 주어졌을 때, 간선의 개수를 최소로 만들자. 접근법 1. 사이클을 형성하는 부분 그래프 단위로 보면 쉽다. 만약 n개의 정점들이 사이클을 형성한다면, 최소 간선의 개수는 n개일 것이다. 그리고 임의의 두 사이클 간에 이동이 가능하다면 간선은 한개만 추가하면 될 것이다. 2. 즉, SCC로 이루어진 서브 그래프들을 구하고 그러한 서브 그래프간의 연결이 있는지 확인하면 된다. 코사라주 알고리즘을 사용하면 SCC는 쉽게 구할 수 있을 것이다. 3. SCC간의 연결은 코사라주 알고리즘 과정에서 만든 스택 데이터를 사용한다. 이 데이터는 정점의 방문 완료시간 순으로 스택에 쌓이기 때문에 가장 나중에 삽입된 정점은 .. [ BOJ 백준 6543번 - 그래프의 싱크 ] 해설 및 코드 https://www.acmicpc.net/problem/6543 목적 한 노드 a부터 출발하여 도달할 수 있는 모든 노드들에서 다시 a로 되돌아 올 수 있다면, a를 싱크 노드라고 한다. 이러한 싱크 노드들을 구하자. 접근법 1. 그래프 이론 중, 방향 그래프에서 싱크 정점(sink vertex)이란 나가는 간선이 없는 정점(outdegree가 0)이다. (문제의 싱크 노드의 정의와는 다르다.) 만약에 여러 SCC로 이루어진 그래프에서 싱크 SCC가 있다면, 그걸 구하는 것이 이 문제의 목적일 것이다. 즉, 한 SCC에서 다른 SCC로 가는 길이 없는 SCC를 구하는 것이다. 2. 코사라주 알고리즘으로 SCC를 구하는 과정에서, 각 SCC에 번호를 매겨 각각의 정점들이 어떠한 SCC에 속해있는지에 대한.. 이전 1 2 3 4 5 6 ··· 17 다음
