728x90 Algorithm (C++ based)/Algorithm 이론9 구간 합 (Prefix sum) 구간 합 (Prefix sum) array 에서 누적 합을 통해 구간 합을 구할 수 있다. 정의 Array 에서 누적 합을 통해 원하는 구간의 합을 구할 수 있다. 설명 1차원 Array 에서의 구간 합 arr Array 는 1차원 배열이고, sum Array 는 0 번째 index 를 가지는 원소부터 그 index 값의 원소까지의 누적 합 배열이다. 위와 같이 3번째(index == 2) 원소 부터 7번째(index == 6) 원소 까지의 구간 합을 구하고 싶으면? sum[6] - sum[1] 을 하면 구할 수 있다 ;) 관련 Code sum[0] = arr[0]; for (int i = 1; i < n; i++) { sum[i] += sum[i - 1] + arr[i]; } // 6 ~ 17 번째 원.. 2022. 4. 19. 최소 스패닝 트리 / 최소 신장 트리 (MST) 최소 스패닝 트리 / 최소 신장 트리 (MST : Minimum Spanning Tree) by Kruskal Algorithm & Prim Algorithm 정의 최소 스패닝 트리(최소 신장 트리, MST : Minimum Spanning Tree)란, 모든 노드들이 가중치가 있는 무방향 간선에 연결이 되어있을 때, 모든 노드들을 연결하는 방법 중 사이클이 없으면서 가중치의 합이 최소가 되는 트리를 의미한다. 좌측과 같은 그래프가 있다고 할 때, 최소 스패닝 트리은 우측의 빨간 간선들로 이루어진 그래프가 된다. 완성된 최소 스패닝 트리는 모든 노드들이 전부 연결이 되어있으며, 사이클이 존재하지 않는다. 또한 V개의 정점을 가진 그래프라고 할 때, 최소 스패닝 트리는 V - 1 개의 간선을 가진 트리가 .. 2021. 8. 9. 유니온 파인드 (Union Find, Disjoint set) 유니온 파인드 (Union Find, Disjoint set) 정의 유니온 파인드(Union Find) 는 서로소 집합(Disjoint-set) 이라고도 불린다. 이는 집합 혹은 그룹 관리를 효율적으로 할 수 있는 알고리즘 이다. 그룹은 트리의 구조로 관리가 된다. 한 트리에 여러 그룹이 있는 것이 아니라 그룹의 개수만큼 트리가 생성이 되는 것 이다. 설명 위 예시의 경우는 두 가지 트리가 존재한다. 그룹이 두 개 존재하는 경우인 것 이다. 두 노드끼리 같은 그룹인지 아닌지 판단하는 기준은 해당 노드의 루트 노드가 같은지 판단하면 된다. 위 예시에서 2, 4번째 노드는 둘 다 루트노드가 1로 동일하다. 따라서 같은 그룹이다. 하지만 3, 6번째 노드는 각각 루트노드가 1, 5번째 노드이다. 따라서 이 두.. 2021. 8. 6. 위상 정렬 (Topological Sort) 위상 정렬 (Topological Sort) 위상정렬 위상정렬은 무향 비순환 그래프 (DAG : Directed Acylic Graph) 에서 정해진 순서에 맞게 나열을 하는 것 이다. 일상에서의 예시로 대학교 과목 이수도 에서 선수과목이 있는 것을 생각해 볼 수 있다. 과목 F 를 듣기 위해선, 과목 D, E 를 들어야 한다. 또 과목 D를 듣기 위해선 과목 A를, 과목 E 를 듣기 위해선 과목 B, C 를 들어야 하고 과목 B를 듣기 위해선 과목 A를 들어야 한다. 이 경우 가장 처음에 들을 수 있는 과목은 선수과목이 없는 과목 A와 과목 C 이다. 위상 정렬은 이러한 선수과목이 없는 경우 즉, 진입 간선이 없는 경우를 따져가면서 정렬을 해 나가는 알고리즘 이다. 설명 1. 주어진 노드와 간선에 대한.. 2021. 8. 5. 투 포인터 알고리즘 (Two pointer Algorithm) 투 포인터 알고리즘 (Two pointer Algorithm) 개요 위와 같은 Array 에 대해서 array[0] + array[1] + ... + array[k] 의 값이 20이 넘을 때 k의 최소값을 구하라고 한다면, 위 주황색 포인터를 계속해서 1씩 증가시켜 가면서 20이 처음으로 넘는 index를 찾게 될 것 이다. 위의 경우 이 때의 정답은 5이다. 이 경우는 사실 많이 기초적이며 array에 대해서 이해를 하려고 공부를 할 때나 다루는 부분일 것이며 대부분의 사람들이 생각할 수 있을 것 이다. 그렇다면, 위와 같은 Array 에 대해서 부분합인 array[k] + array[k + 1] + ... + array[n] 의 값이 6에 해당이 되는 index가 연속되는 부분집합의 개수를 구하라면 .. 2021. 7. 20. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) What is Floyd-Warshall Algorithm? Dijkstra (다익스트라) 알고리즘이 시작하고자 하는 한 vertex에서 나머지 vertex들로 가는 최소 비용을 구하는 알고리즘 이라면, 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로 가는 최소 비용을 2차원 array 혹은 vector 에 저장을 해 둔다. 아래 코드에선 floyd[ i ][ j ]로 표기했고, 이 의미는 vertex i 에서 vertex j 로 가는 최소 비용을 의미한다. floyd[ i ][ j ]의 값을 vertex i, vertex j 를 제외한 모든 vertex 를 경유해보면서 더 작은값을.. 2021. 2. 20. Dijkstra (다익스트라) Dijkstra What is Dijkstra? 그래프의 한 노드에서 다른 노드로 갈 때 드는 가중치들의 합의 최소값을 구하는 알고리즘이다. 이 '가중치'를 문제가 요구하는 바에 따라 거리, 비용 등의 형태로 문제에 다양하게 적용시킬 수 있을 것 같다. Explanation A정점부터 탐색을 시작해봤다. 실제 코드에서 알고리즘을 사용할 땐 처음에 시작하고자 하는 정점을 정해주면 된다. 좌측의 표에서 빨간색은 확정된 최소 비용을 나타낸다. A에서 A로 갈 때에는 당연히 비용이 0이므로 확정이다. 숫자 앞에 A를 붙인 이유는 직전에 A에서 왔다는 의미이다. B, C, D E 열에 차례대로 비용을 적어준다. F열은 A에서 F로 가는 간선이 없으므로 inf 라고 하자. 저렇게 나열해준 뒤 확정이 된 빨간색 칸을.. 2021. 2. 8. Palindrome (팰린드롬) Palindrome Definition 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어 혹은 구를 의미한다. Example 팰린드롬 "madam" "오디오" "안경안보여" 1234321 44 팰린드롬이 아닌것 123432 2021. 2. 5. Greedy algorithm (탐욕 알고리즘) // Greedy algorithm What is Greedy algorithm? 답을 하나씩 골라가는데, 미리 정해놓은 기준에 따라 매번 가장 좋아 보이는 답을 선택하는 것이다. 하지만 을 이용하여 설계를 한다면 항상 최적의 해는 보장할 수 없다. Example 의 예시로 가장 많이 보여지는 것들 중 하나인 "거스름돈 문제"를 예시로 들어보자. "거스름돈 문제"란, 임의의 액수만큼 거스름돈을 주어야 하는데 최소한의 개수의 동전을 사용하여 주어야 할 때 해당되는 동전들을 고르는 문제이다. 예를 들어 만약 거스름돈으로 520원을 주어야 한다. 이때 520원을 줄 수 있는 방법은 다양하다. 하지만 상식적으로 10원짜리 동전 52개로 거슬러주는 것보단 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는.. 2020. 11. 10. 이전 1 다음 728x90
