문제 해결을 위한 자료구조 & 알고리즘

정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점은 무엇일까? 투 포인터를 활용한 대표적인 예로 아래와 같은 문제가 있다

그래프를 탐색하는 방법에는 크게 너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS) 두 가지가 있는데, 먼저 너비 우선 탐색에 대해 알아보도록 하자. 너비 우선 탐색 너비 우선 탐색은 가장 먼저 시작 정점을 방문한 후, 그 시작 정점과 인접한 모든 정점들을 우선적으로

깊이 우선 탐색 DFS 역시 BFS와 마찬가지로 그래프를 탐색하는 알고리즘의 하나로, 시작 정점으로부터 하나의 방향을 잡아 끝까지 탐색한 후 마지막 분기점으로 돌아와 다시 다른 방향으로 끝까지 탐색을 반복하는 방식이다. 이렇게 이름처럼 깊이를 우선적으로 쭉 탐색하기 때

다익스트라 알로리즘은 그래프에서 최단 경로를 찾는 알고리즘 중 하나로, 하나의 출발점을 기준으로 다른 모든 정점까지의 최단 거리를 구할 때를 활용할 수 있는 알고리즘이다. 다익스트라 알로리즘은 최단 거리를 찾기 위해 시작 정점에서부터 인접한 정점들을 하나씩 방문하며 해

벨만-포드 알고리즘은 앞서 살펴본 다익스트라 알고리즘과 같이 그래프에서 시작 점점으로부터 다른 모든 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 하지만 중요한 차이점이 있는데, 벨만-포드 알고리즘은 그래프 내에 음수 가중치를 갖는 간선이 있는 경우에도 활용할 수 있

다익스트라, 벨만-포드 알고리즘으로 주어진 하나의 정점으로부터 다른 모든 정점들까지의 최단 경로를 구할 수 있었다면, 플로이드-워셜 알고리즘을 활용하면 모든 정점들간의 최단 경로를 구할 수 있다.다익스트라 알고리즘에서는 출발점이 정해져 있었기 때문에 출발점에서 도달할