본문 바로가기

코딩테스트 준비/알고리즘

 (13)
위상정렬 (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..

티스토리툴바