본문 바로가기

알고리즘4

[Algorithm] 다익스트라 알고리즘 인접리스트로 풀기 인접 리스트로 풀기 다익스트라 문제의 경우 인접 리스트로 푸는 경우가 많다고 한다. 왜냐하면 힙을 이용해 시간 복잡도를 줄일 수 있기 때문이다. 여기서 힙이란 스택과 대비되는 자료구조 중의 하나로 개발자가 직접 할당해서 사용하는 메모리 부분이다. 그렇다면 아래 문제를 한번 인접리스트로 풀이해 보겠다. 문제 무방향 그래프의 한 정점(vertex)에서 다른 정점까지의 최단 거리를 리턴해야 합니다. 입력 인자 1: num number 타입의 자연수 그래프에 존재하는 정점의 개수 정점은 1부터 num까지 존재 인자 2: edges 배열(간선에 대한 정보)을 요소로 갖는 배열 edges [i]는 number 타입을 요소로 갖는 배열 edges [i]. length는 3 edges [i]의 요소는 차례대로 정점, .. 2022. 3. 25.
[Algorithm] 플로이드 와샬 알고리즘 이번에는 최단거리 알고리즘의 마지막! 플로이드 와샬에 대해 알아보자. 플로이드 와샬은 다른 최단거리 알고리즘 중에서 제일 느리다. 왜냐하면 딕스트라나 벨만 포드는 모두 출발점이라는 개념이 있는데 플로이드 와샬은 그런 거 모르겠고 모든 노드의 최단거리를 다 구해 버리기 때문이다. 자바스크립트 구현 코드 const INF = Infinity; const floydWarshall = function(dist){ const len = dist.length; for (let i = 0; i dist[j][i] + dist[i][k]) dist[.. 2022. 3. 25.
[Algorithm] 벨만포드 알고리즘 오늘은 딕스트라 알고리즘에 이은 벨만 포드! 음수의 값이 있을 때 최단거리를 구하는 데 사용할 수 있다. 실제 상황에서 음수 거리라는 게 있을 수는 없지만... 저번 코딩 테스트 문제로 나와 당황했던 기억이 있으니 오늘 한번 풀어보려고 한다. 방식은 아래와 같다. 1. 노드 수만큼 최단거리를 표시하는 배열을 생성한다. 이 때 시작점을 제외하고는 INF 값을 넣는다. 시작점은 0을 넣어준다. 2. 노드 수 만큼 루프 하면서 모든 간선을 루핑 하는데 이때 최단거리에서 INF가 아닌 시작점이면서 도착점까지의 거리에 가중치를 더했을 때 현재의 거리보다 작아진다면 최단거리 배열을 수정한다. 3. 마지막으로 위 과정을 한번 더 적용했을 때 만약 최단거리가 또 수정된다면 이는 무한 루프에 빠진 것으로 정답이 없는 게.. 2022. 3. 25.
[Algorithm] Powerset 알고리즘 뽀개기 어제 Powerset 알고리즘 공부를 하다 결국 침대에 누워 서럽게 울다 지쳐 잠이 들었다... 나만 이해가 안되는 건가..? 하지만 정신을 차렸으니 다시 한 번 꼼꼼이 파헤처 보도록 하자. 일단은 Poserset에 대한 기본적인 이해부터 해보도록 해보겠다. Powerset = 멱집합 The power set is a set which includes all the subsets including the empty set and the original set itself. 멱집합이란 빈집합부터 원래 요소를 모두 포함한 집합까지의 모든 하위 집합을 말한다. 즉 {1, 2, 3}의 멱집합은 다음과 같다: {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} Power.. 2021. 12. 14.

티스토리툴바