본문 바로가기

전체 글

 (87)
C++ 백준 2252 (줄 세우기) 백준 2252 (줄 세우기) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 설명 이 문제는 위상정렬(DFS)를 통해 간단히 풀 수 있는 문제였다. 위상정렬에 대한 설명은 위상정렬(링크)에 자세히 설명이 되어있다. 예제입력으로 각 일에 대한 순서들이 주어지는데 각 일을 하나의 노드로 생각하고 방향성이 있는 그래프로 생각하면 된다. 예를 들어 1 2 가 입력되었다면 1번노드에서 2번노드로 가는 길이있다고..
유니온 파인드(Union Find) 설명 유니온 파인드는 집합의 표현을 빠르게 구현하는 알고리즘이다. 예를 들어보자. 사람 P1, P2, P3, P4가 있다. 각 사람은 자신의 소속집단 C1, C2, C3, C4에 가입되어 있다고 가정하자. 1. C3에 속한 P3가 P1과의 합병을 진행한다. 그렇다면 P1, P2, P3, P4의 각 소속집단은 C1, C2, C1, C4으로 바뀔 것이다. 2. C1에 속한 P1이 P4와의 합병을 진행한다. 그렇다면 P1, P2, P3, P4의 각 소속집단은 C4, C2, C4, C4으로 바뀔 것이다. 2번 과정에서, P1(C1)과 P4(C4)의 병합을 위해 C1소속 사람과 C4소속 사람의 합병이 진행되었다. 이로인해 C1에 소속이었던 P3의 소속집단도 C4로 변한것을 확인할 수 있는데, 이 방법은 최악의 경..
위상정렬 (Topological Sort) 알고리즘 위상정렬 해당 내용을 이해하기 위해선 DFS(링크)에 대한 이해가 필요하다. 위상정렬(Topological Sort)는 DFS를 사용하는 대표적인 알고리즘이다. DFS말고 indegree의 개수를 측정하는 방법도 있다. 알고리즘의 목표는 일의 순서를 정하는 것이다. 예를 들어 W1, W2, W3 (W는 할 일이다)이 있다고 가정하자. W2는 W1을 끝내야만 할 수 있고, W3은 W2를 끝내야만 할 수 있다. 그렇다면 일의 순서는 W1 → W2 → W3로 하면 될 것이다. 예시는 3개밖에 없어서 간단한 암산으로 금방 해결할 수 있지만, 주어진 정보가 많아진다면 골치가 아파진다. 이때 사용하는 알고리즘이 바로 위상정렬이다. 다음과 같은 그래프가 있다. 각 노드는 위에서 언급한 '일'이라고 생각한다. 모든 노..
펜윅트리(Fenwick Tree) 자료구조 펜윅트리(Fenwick Tree) 펜윅트리를 공부하기 전에 우선 세그먼트 트리에 대한 이해와 그 필요성에 대해 알아야한다. 세그먼트 트리는 구간의 정보를 빠르게 가져올때 사용한다. 기존 세그먼트 트리를 설명하면서 크기 N의 배열에 대해 필요한 트리의 사이즈는 2^(트리의 높이+1)이라고 잠시 짚고 넘어갔었다. 트리의 높이는 밑이 2인 logN이므로 트리를 구성하기 위해선 대충 4N정도의 크기가 필요하다. 또한 세그먼트 트리는 구현도 복잡하다..ㅎㅎ 펜윅트리은 이 문제를 해결할 수 있다. 결론부터 말하자면 크기 N의 배열에 대해 N만큼의 크기가 트리구성에 필요하고 구현또한 매우매우 간단하다. (이해만 한다면..) 펜윅트리를 이해하기 위해서는 또 한가지를 알아야 한다. 바로 비트마스크연산이다. 비트마스킹을 ..
세그먼트 트리(Segment Tree) 자료구조 세그먼트 트리(Segment Tree) 구간의 정보를 업데이트하고 가져올때는 어떤 방법을 사용할까? 가장 쉽게 생각나는 방법은 업데이트시 해당 배열의 값을 바꾸고, 다시 가져오는 방법이다. 예를 들어 arr[4] = {1,2,3,4}라는 배열이 있고, 다음의 작업을 수행한다고 가정하자. 1. arr[0]~arr[3]까지의 합을 구한다. 2. arr[3]의 값을 5로 변경한다. 3. arr[0]~arr[3]까지의 합을 구한다. 해당 내용을 위에서 언급한 방식대로 진행하면 인덱스 0~3까지의 배열의 합을 구하고 (Θ(N)) arr[3]의 내용을 바꾼뒤 다시 0~3까지의 배열의 합을 구해야 한다(Θ(N)). 위의 예시는 배열의 크기가 작기때문에 위의 방식대로 해도 큰 문제가 없지만, 배열의 크기가 매우 커지고..
DFS(Depth-First Search) DFS BFS와 같이 탐색에 이용되는 대표적인 알고리즘이다. BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예 seongmok.com 너비를 우선으로 단계적으로 탐색했던 BFS와 달리 DFS는 깊이를 우선으로 탐색하기 때문에 방문하지 않은 이웃 단계를 최대한 깊게 탐색할 수 있는 만큼 하는 것을 목적으로 한다. 예제를 보며 이해해보자. 다음과 같은 그래프가 있다. 정점1에서 출발하여 모든 정점을 탐색하는데, 이때 위 목적을 바탕으로 움직일 것이다. 불필요한 중복 방문을 막기 위해 현재 정점을 방문체크 한 뒤, 이웃한 정점 중..
BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예로 들 수 있다. 또한, 어떤 작업의 처리에 대한 최소 단계 등을 요구하는 문제에서도 사용될 수 있다. BFS를 구현하기 위해선 Queue가 필요하다. Queue는 선입선출으로 동작하기 때문에 가장 먼저 방문했던 단계의 이웃을 우선으로 탐색할 수 있다. 예제 보며 이해해보자. 다음과 같은 그래프가 있다. 정점1에서 시작해 그래프에 존재하는 모든 정점을 방문할 것이고, 한 정점에서 또 다른 정점은 간선을 통해 이동할 수 있다. 이때, 정점1에서 출발하여 각 정점 단계적으로 모두 방문하고 싶다. 단계적인 탐색이 필요하므로, B..

티스토리툴바