본문 바로가기

computer science/알고리즘17

[알고리즘] 구간 합(prefix sum) 구간 합 알고리즘은 1차원배열에서 i ~ k번째 사이의 값들의 합을 구하는데 사용합니다. 단순히 for문을 사용하여 i~k사이의 값을 더해가면서 할 수도 있지만 이 경우 시간복잡도는 O(N)입니다. 하지만 구간 합 알고리즘의 경우 O(1)성능을 가집니다. 그리고 sum[]이라는 배열을 사용하는데, 이 배열은 현재 인덱스까지의 총 합을 저장하게 됩니다. j번째 바로 앞까지의 총합에 arr[j]번째 값을 더하면 j번째까지의 총합을 의미하기 때문에 이 값은 sum[j]에 저장하며 이는 sum[j] = sum[j-1] + arr[j]가 됩니다. 이후 5,8의 구간합을 구하기 위해서는 sum[8] - sum[5-1]로 한번에 구할 수 있습니다. #include using namespace std; int main.. 2020. 9. 25.
[알고리즘] 투포인터(two pointers) 투포인터는 전혀 알지 못했는데 카카오 코딩테스트 문제를 풀다가 우연히 알게 되었습니다. 처음 봤을 때 2개의 변수값을 조금씩 움직여가는것이 매개변수 탐색과 비슷하다고 생각했습니다. 투포인터는 1차원 배열에서 각각의 index를 가리키는 2개의 변수를 조작해가면서 문제를 해결하는 기법입니다. 투포인터를 백준문제를 보면서 설명하겠습니다. www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제는 1차원 배열에서 i번째에서 j번째까지의 합이.. 2020. 9. 25.
[알고리즘] 최단거리 알고리즘(Dijkstra,Floyd Warshall) Dijkstra Algorithm 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘 입니다. A,B,C,D,E,F 노드가 있을 때 하나의 정점A를 기준으로 A-B, A-C, A-E ...까지의 최단거리를 구할 수 있습니다. 이전에 구한 값을 재사용한다는 의미에서 다이나믹프로그래밍, 항상 가장 짧은 거리의 노드를 선택한다는 점에서 그리디 알고리즘으로 분류하기도 합니다. 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 거리를 저장 3. 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택 4. 해당 노드를 거쳐가는 경우와 거쳐가지 않은 경우를 비교하여 최단거리 갱신 5. 3,4 과정을 반복 A를 기준으로 각 노드의 거리 저장하였습니다. D,E의 경우 .. 2020. 9. 22.
[알고리즘] 최소비용 알고리즘(Kruskal's, Prim's) 최소신장트리(MST : Minimum Spanning Tree) 크루스칼 알고리즘을 알기 전에 먼저 최소신장트리에 대해 간략하게 공부하고 넘어 가겠습니다. 신장트리란 트리의 특수한 형태로 모든 정점을 포함하고, 정점간 서로 연결되면서 사이클이 존재하지 않는 그래프를 의미합니다. 여기서 최소신장트리는 신장트리들 중에서 간선의 가중치가 최소를 만족하는 신장트리를 의미합니다. 아래의 사진을 보면 여러 정점들 사이에 간선이 존재하고, 이 간선에는 가중치값이 존재합니다. 아래의 왼쪽 그래프에는 다양한 신장트리가 나올 수 있습니다. 하지만 여러개의 신장트리 중에서 그 가중치의 합(간선에 배정된 값)이 최소가 되는 트리가 최소신장트리 입니다. 여기서 최소신장트리를 만드는 알고리즘이 이번시간에 배울 크루스칼 알고리즘과.. 2020. 9. 18.

티스토리툴바