DevBoi

투 포인터의 대표 적인 예제는 아래와 같다. 리스트 A가 있고, 타겟값 S가 있다. 이 리스트에서 두수의 합이 타겟값 S가 되는 걸 찾는다고 가정하면? 리스트 1개씩 비교해 가면서 체크를 할수있겠지만. 리스트의 크기에 따라, 시간 복잡도는 정비례하게된다. 그러면 이럴 경우에는 ? 리스트를 정렬하고 투포인터 알고리즘을 사용하면 된다. 사용 방법은 아래 순서와 같다. 1. 리스트를 오름차순으로 정렬한다. 2. 포인터 left는 리스트의 시작점을 포인터 right는 리스트의 끝점을 가리킨다. 3. left 와 right가 만날때까지 다음을 반복한다. 3-1. left + right 의 합이 타겟 값과 같으면 출력, 3-2. left + right 가 타겟 값보다 작으면 left 1증가 3-3 left + ri..

최단 경로에 대한 알고리즘을 정리해보자. 엇 최단 경로면 BFS 아닌가? 응 아니야~ 그러면 시작해보자 특정 시작노드에서부터 가중치를 더해가면서 계산하는 다익스트라 알고리즘이라는 것을 써야한다. 다익스트라 알고리즘이란? BFS랑 유사하지만 조금 다른 개념이다. BFS는 단순 가장가까운 노드부터 계산해서 큐에 넣고 빼서 체크를 했다면 다익스트라는 가까운 노드만 업데이트를 하는것이다. 그래서, 우선순위 큐는 minHeap방식을 활용해서 가장 짧은 거리를 가진 노드 정보만 꺼내고 업데이트한다. 좀더 자세히 알아보자 * 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,..