본문 바로가기

Algorithm5

[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] 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.
[Algorithm] D.P Top-Down vs Bottom-up Dynamic Programming에서 최적의 값을 찾기 위해 두 가지의 방법을 사용한다. 바로 Top-Down 방식과 Bottom-Up 방식! 오늘은 이 둘의 차이점에 대해 Deep 하게 파헤쳐 보자. 레츠 기릿! Difference Between Top-Down and Bottom-up Approach 알고리즘은 탑다운과 바텀업 접근법으로 나뉘어 디자인된다. Top-down 접근법에서는 복잡한 모듈이 작은 모듈로 나누어진다. 반면에 Bottom-up 접근법에서는 기초적인 모듈을 점점 합쳐나가는 방식을 이용한다. 알고리즘의 최우선 목표는 데이터 구조 속 데이터를 작동시키는 것이다. 다른 말로 설명하자면, 알고리즘은 데이터 구조속의 데이터 연산을 실행하기 위해 사용된다. 복잡한 알고리즘은 모듈이라고 부르.. 2021. 12. 13.
[Algorithm] Greedy Algorithm 오늘부터 본격적으로 알고리즘 공부를 시작하려 한다. 쫄지마 나 자신...! 우선 그 첫 번째 시작을 Greedy Algorithm에 관한 포스팅으로 시작하려 한다. Greedy Algorithm 이란 무엇인가? 탐욕적 알고리즘(Greedy Algorithm)은 각각의 작은 단계에서 최선의 선택을 내림으로서 전체적으로 최적의 솔루션을 찾아내는 알고리즘 전략을 말한다. 즉 탐욕적 알고리즘은 순간순간마다 결과는 신경 쓰지 않고 최선의 솔루션을 선택하게 된다는 뜻이다. 최선의 아웃풋을 즉각적으로 골라내지만, 전체적인 그림은 고려하지 않기 때문에 '탐욕적'이라고 부른다. 탐욕적 알고리즘은 각가의 단계에서 최적의 해답을 선택하고 끝이 나타날 때까지 다음 단계로 넘어가는 방식으로 동작한다. 각각의 단계에서 선택하는 .. 2021. 12. 13.

티스토리툴바