코딩테스트 준비 (35) 썸네일형 리스트형 세그먼트 트리(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.. 이전 1 2 3 4 5 다음
