윤깡패 블로그

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘 특징 - 음수 가중치 에지가 있어도 수행할 수 있다. - 동적 계획법의 원리를 이용해 알고리즘에 접근한다. - 시간복잡도 : O(V³) (노드 수 : V) 플로이드-워셜 핵심 이론 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다. 플로이드-워셜 점화식 D[S][E] = min(D[S][E], D[S][K] + D[K][E]) 플로이드-워셜 알고리즘 구현 방법 1. 배열을 선언하고 초기화한다. D[S][E] : 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열 초기화 - S == E ⇒ D[S][E] = 0 (자기 자신에게 가는 데 걸리는 최단 경로값) - S != E ⇒ D..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 soobin0821.tistory.com 코드 #include #include #include using namespace std; int main() { ios::..

문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 soobin0821.tistory.com 코드 #include #include #include using namespace std; int main() { ios::sync_with_std..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 신장 트리(Minimum Spanning Tree) 자료구조 최소 신장 트리(Minimum Spanning Tree) 자료구조 최소 신장 트리(Mininum Spanning Tree) 자료구조 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 신장 트리 * 신장 트리(Spanning Tree) : 하나의 그래..

최소 신장 트리(Mininum Spanning Tree) 자료구조 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 신장 트리 * 신장 트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 그래프(Graph) 자료구조 그래프(Graph) 자료구조 그래프(Graph) 자료구조 노드와 노드 사이에 연결된 에지의 정보를 가지고 있는 자료구조 노드(Node) : 데이터를 표현하는 단위 에지(Edge) : 노드를 연결 에지 리스트(Edge List) 노드를 배열에 저장하 soobin0821.tistory.com 최소 신장 트리 특징 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문) N..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 이분 그래프가 불가능하다 ⇒ 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같은 경우 입력된 그래프 데이터를 인접 리스트로 구현한다. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다. 실행 결과가 이분 그래프가..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 D[N][H] : 길이가 N인 계단에서 H 높이로 종료되는 계단 수를 만들 수 있는 경우의 수 - (H = 0) D[i][H] = D[i - 1][H + 1] - (H = 9) D[i][H] = D[i - 1][H - 1] - (H = 1 ~ 8) D[i][H] = D[i - 1][H - 1] + D[i - 1][H + 1] 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법(Dynamic Programming) 알고리즘 ..

문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 soobin0821.tistory.com 코드 #include #include #include using namespace ..

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 2차원 배열에서의 k번째 수는 k를 넘지 않는다. ( = 2차원 배열의 1 ~ k번째 안에 정답이 있다.) ⇒ 이진 탐색으로 작은 수의 개수가 k - 1개인 중앙값을 구한다. 이진 탐색 조건 - 중앙값 크기보다 작은 수가 K보다 작으면 시작 인덱스 = 중앙값 + 1 - 중앙값 크기보다 작은 수가 K보다 크거나 같으면 종료 인덱스 = 중앙값 - 1, 정답 변..

문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 soobin0821.tistory.com 코드 #include #include #include using namespace std; int m..