✏️ 알고리즘

[AtCoder] ABC295 A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 앳코더 ABC295에 대해 업솔빙하는 글입니다. 이번 대회는 약 60분 정도부터 시작하였다. A번 - 단순 구현 문제이다. B번 - 단순 구현 문제로 $O(R^2 \cdot C^2)$으로 해결할 수 있다. - 조금 더 효율적으로 구현하면 $O(R \cdot C \cdot 9^2)$으로 해결할 수 있다. C번 - 약간의 사고력을 요구하는 문제이다. - sort(정렬)을 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. - map 자료구조를 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. D번 - 대회가 끝나고 본 문제이며, prefix xor을 이용하면 $O(N)$으로 해결할 수 있다. A. Probably English $N$개..

[18강] 최소 신장 트리 (MST)

안녕하세요 Gliver 입니다. 이번 글에서는 최소 신장 트리 (MST, Minimum Spanning Tree)에 대해 알아보겠습니다. 목차 최소 신장 트리란? 유니온-파인드 자료구조 크루스칼 알고리즘 정리 최소 신장 트리란? 최소 신장 트리(MST, Minimum Spanning Tree)에 대해서 알아보자. 트리(Tree)란? 트리(Tree)란 노드 N개와 N-1개의 간선으로 이루어져 있으며 모든 노드가 서로 연결되어 있는 구조이다. 즉, 트리는 그래프에 포함되는 개념이며 그래프의 특별한 경우라고 할 수 있다 예를 들어, 아래의 그래프는 간선의 개수가 '노드의 개수-1'이므로 트리라고 할 수 있으며 아래의 그래프는 간선의 개수는 '노드의 개수-1'이지만 노드 D가 다른 노드들과 연결되어 있지 않으므..

[17강] 사이클이 없는 방향 그래프 (DAG)

안녕하세요 Gliver 입니다. 이번 글에서는 사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)에 대해 알아보겠습니다. 목차 사이클이 없는 방향 그래프 위상 정렬 정리 그래프는 비선형 자료구조이기 때문에 보통 정렬이 불가능하지만 특별한 경우에는 정렬이 가능합니다. 사이클이 없는 방향 그래프일 때 정렬이 가능하며 이때의 정렬을 위상 정렬이라고 합니다. 이번 글에서는 사이클이 없는 방향 그래프(DAG)와 위상 정렬에 대해서 알아보겠습니다. 사이클이 없는 방향 그래프 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)는 말 그대로 사이클이 없는 방향 그래프를 의미한다. 사이클이 없는 방향 그래프에서는 정렬이 가능할까? 방향 그래프에서 아래와 같은 상황이..

[16강] 그래프(Graph) 최단 경로 알고리즘

안녕하세요 Gliver 입니다.이번 글에서는 그래프(Graph) 최단 경로 알고리즘에 대해 알아보겠습니다. <span style="color: #00000..

[15강] 그래프(Graph) 순회 (DFS & BFS)

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 순회 (DFS & BFS)에 대해 알아보겠습니다. 목차 그래프 순회란? 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (BFS) 정리 지난 글에서 그래프를 코드로 표현하는 법에 대해서 알아보았습니다. 이번 글에서는 어떻게 그래프를 순회(탐색)할 수 있는지 알아보겠습니다. 지난 글에서 말했듯이 그래프 탐색에 있어서는 인접 리스트 방식을 이용할 예정임 그래프 순회란? 그래프 순회(탐색)란 그래프 내의 모든 노드를 한 번씩 살펴보는 것을 의미한다. 선형 자료구조에서 탐색 선형 자료구조란 순서가 있는 자료구조를 의미한다. 즉, 배열 같은 경우는 원소들이 인덱스 순으로 구성되어 있으니 선형 자료구조라고 할 수 있다. 이러한 선형 자료구조에서의 탐색은 ..

[14강] 그래프(Graph) 기본

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 기본에 대해 알아보겠습니다. 목차 그래프를 코드로 표현하기 인접 리스트 (Adjacency List) 인접 행렬 (Adjacency Matrix) 간선 리스트 (Edge List) 정리 지난 글에서 그래프는 노드(정점)와 간선으로 이루어져 있다고 설명하였습니다. 이번 글에서는 이러한 그래프를 어떻게 코드로 표현할 수 있는지 알아봅시다. 그래프를 코드로 표현하기 그래프를 코드로 어떻게 표현할 수 있을까? 그래프는 노드와 간선으로 구성되어 있으므로 노드와 간선을 각각 어떻게 표현할 수 있는지 살펴보자. 노드는 하나의 정점으로 노드의 개수만큼의 공간으로 표현할 수 있다. 간선은 노드와 노드를 선을 잇는 것이므로 간선 1개는 노드 2개로 표현할 ..

[13강] 그래프(Graph)를 배우는 이유

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph)를 배우는 이유에 대해 알아보겠습니다. 목차 그래프란 무엇인가? 그래서 그래프가 어디에 쓰이는데? 그래프를 배우는 이유 그래프 공부의 상한선 그래프란 무엇인가? 정점과 간선으로 이루어진 구조를 그래프(Graph)라고 칭한다. (위키피디아) 보통 정점은 node 또는 vertex, 간선은 edge라고 부른다 아래의 그림1은 정점과 간선이 둘 다 존재하므로 그래프이지만, 그림2는 간선이 존재하지 않으므로 그래프가 아니다. 간선의 방향 유무에 따라 방향 그래프, 간선의 가중치 유무에 따라 가중 그래프, 서브 그래프를 컴포넌트라고 하는 등 그래프는 굉장히 다양한 개념을 가지는 데 이는 다음 장에서 살펴보도록 하겠다. 그래서 그래프가 어디에 쓰이는데..

[12강] 투 포인터 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 투 포인터 알고리즘에 대해 알아보겠습니다. 목차 투 포인터 알고리즘 실제 문제에서 투 포인터 알고리즘 1. 투 포인터 알고리즘 투 포인터 알고리즘은 두 개의 포인터(지점)를 이용하는 알고리즘이다. 정의는 간단하지만, 단순히 두 개의 포인터를 이용하는 것만으로 문제가 쉽게 풀리는 경우가 종종 있다. 투 포인터(Two Pointer) 알고리즘을 어떤 상황에서 사용할 수 있는지와 어떻게 동작하는지 문제를 통해서 살펴보자. [문제] (백준 2003번) 크기가 N인 양의 정수로 이루어진 배열이 있다고 해보자. 이때, 부분 구간의 합이 M인 부분 구간이 몇 개인지 구하여라. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 300,000,000) (시간 제한: 1초) 먼저,..