최단 거리 알고리즘 - 다익스트라 [Java]

목차 1. 서론 2. 작동원리 3. 구현 1. 서론 다익스트라 알고리즘은 한 정점에서 다른 정점들까지의 최단 거리와 경로를 구하는 알고리즘이다. 단, 간선의 거리 정보는 항상 0 이상이어야 한다. 2. 작동원리 1. 방문하지 않은 정점 중 가장 시작점으로부터 거리가 짧은 정점으로 이동한다. 이 때, 해당 정점까지의 최단 거리는 확정된다. 2. 현재 정점과 인접한 모든 정점들 중 방문하지 않은 정점들을 돌면서 거리를 갱신시켜준다. 즉, 현재 정점까지의 최단 거리를 A, 현재 정점과 인접한 정점 V를 잇는 간선의 거리를 B, 현재까지 구한 V까지의 최단거리를 C라고 했을 때, A+B < C 이면 V까지의 최단 거리를 A+B로 갱신해준다는 의미이다. 위 과정을 아래에서 그림으로 한번 살펴보자. 아래 그림은 영..

→2021.11.29

이분 탐색 알고리즘 헷갈리는 내용 정리(while 조건, lo/hi 갱신 처리, 반환 값, lo/hi 범위)

이분 탐색을 이용한 백준 문제들을 풀다가 헷갈리는 부분들이 생겨 그에 관해 정리해본다. 일단 이분 탐색 알고리즘의 대표적인 코드를 한번 보자. int BinarySearch(int lo, int hi, int target) { while(lo + 1 < hi) { int mid = (lo + hi) / 2; if(arr[mid] target) hi = mid; } return lo; } 여기서 헷갈리는 부분들이 4가지가 있었다. while문 안의 조건 다른 사람들의 이분 탐색 코드를 살펴보면, 대표적으로 많이 쓰이는 3가지가 있다. (lo + 1 < hi), (lo < hi), (lo = target 라면, hi = mid로 갱신을 해줘야한다. while문을 탈출하는 lo + 1 == hi의 경우에, h..

→2021.09.16

시간 복잡도 / 공간 복잡도

1. 시간 복잡도, 공간 복잡도란? 좋은 알고리즘이란 무엇일까? 얻고자 하는 결과를 짧은 시간과 적은 메모리 공간을 이용하여 구해내는 알고리즘을 좋은 알고리즘이라 할 수 있다. 이 때 알고리즘 수행에 드는 시간 효율과 공간 효율을 알아내는 방법이 필요한데, 그것이 시간 복잡도와 공간 복잡도이다. 2. 시간 복잡도 알고리즘의 시간 복잡도를 계산할 때는 알고리즘의 연산의 횟수를 계산하여 정한다. 알고리즘은 경우에 따라 연산 횟수가 최선의 경우, 평균적인 경우, 최악의 경우로 달라질 수 있다. 대체로 최악의 경우를 산정하고 시간 복잡도를 파악한다. 그렇다면 이 때 연산이라고 할 수 있는 것에 무엇이 있을지 알아보자. 대입 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈) 비교 연산 함수의 호출 public int..

→2021.08.12

위상 정렬(Topological sorting) [Java]

목차 1. 위상정렬이란? 2. 위상정렬의 과정 3. 위상정렬 구현 1. 위상정렬이란? 위상정렬은 사이클이 존재하지 않는 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 대표적인 실생활의 예로 대학교의 선후수 교과과정이 있다. 위와 같은 상황에서 과목을 듣는 순서를 짜는 것이 위상정렬의 한 예이다. 만약 사이클이 있다면 선후 관계가 모호해지기 때문에 사이클은 올 수 없다. 2. 위상정렬의 과정 위 그래프를 한번 위상정렬해보자. 먼저 들어오는 간선이 없는 A가 제일 앞에 올 것이다. A에서 나가는 간선을 보면 B, C, D를 향해 있다. 이것의 의미는 B, C, D를 거치기 전에 반드시 A가 등장해야한다는 의미이다. 지금 상태에서는 A가 제일 앞에 등장했으니 A에서 나가는 간선은 의미가 없다. 그러므로 A와..

→2021.08.07

투 포인터

투포인터 알고리즘 동작 흐름 배열에서 두 지점을 가리키는 포인터를 만들어 배열을 검색하는 알고리즘이다. 투 포인터를 사용하는 주된 이유는 시간복잡도를 낮추기 위함이다. 투 포인터 알고리즘에서 포인터 2개를 배치하는 방식에 2가지 경우가 있다. 1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우 2) 두 포인터가 배열의 시작에서 같이 방향으로 진행하는 경우 1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우 N개의 원소를 가진 배열 arr에서 합이 M인 경우를 찾는다고 해보자. (N, M은 정수) 하나의 포인터는 배열의 첫번째 원소, 나머지 포인터는 배열의 마지막 원소를 가리킨다. 두 포인터는 서로 마주 보며 이동한다. 두 포인터가 만나거나, 가리키는 원소의 합이 M이 될 때까지 이동..

→2021.07.24