[자료구조] Directed Graph
References Data Structrue : A Pseudocode Approach with C Contents Graph Directed Graph Graph 그래프는 정점(vertex, vertices)라고 불리는 노드(node)들과 이 정점들을 연결해주는 간선(edge)로 이루어진 자료구조입니다. 아래 그림에서 A, B, ..., E, F에 해당하는 것들을 정점(vertex)라고 부르고, 이 vertex 사이의 선을 간선(edge)라고 합니다. 그리고 그래프는 여러 종류가 있지만, 위 그림처럼 크게 directed graph, 방향을 가지는 그래프와 undirected graph, 방향을 가지지 않는 그래프로 분류할 수 있습니다. 즉, 간선(edge)가 방향을 가지느냐 가지지 않느냐로 나누어 ..
2021. 10. 4.
투 포인터(Two Pointer), 슬라이딩 윈도우(Sliding Window)
이번 게시글에서 정리할 기법은 투포인터와 슬라이딩 윈도우 입니다. 두 기법은 유사해서 하나로 묶었는데, 우선 투 포인터를 살펴보겠습니다. 투포인터는 1차원 배열에서 배열 원소를 가리키는 두 개의 포인터를 조절해가면서 원하는 답을 찾는 기법입니다. 문제를 보면서 살펴보겠습니다. 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 2003번 문제는 N개의 수로 이루어진 배열이 있을 때, 연속된 부분 수열의 합이 M을 만족하는 경우의 수를 ..
2020. 9. 20.