Back-End/알고리즘
[필수 알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 이해
다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다. 다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다. 그리디 알고리즘과 다이나믹 프로그래밍 기법은 아래의 글에 포스팅되어있다. 그리디 알고리즘 https://cobi-98.tistory.com/44 [필수 알고리즘] 그리..
[필수 알고리즘] 그리디 알고리즘(Greedy Algorithm) 이해
그리디 알고리즘 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란, "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 루트 노드부터 시작하여 거쳐 가는 노드 값의 최대로 구한다면, 값은 5+7+9 = 21로 다음과 같지만 거쳐가는 노드의 경우에서 가장 큰 값(최적의 값만) 구한다면, 값은 5+10+4 = 19 가 된다. 이처럼, 그리디 알고리즘은 최적의 값을 도출해내지 못하지만 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 그리디 알고리즘 기법 활용..
[필수 알고리즘] 이분 탐색(Binary Search) 이해
이분/이진 탐색 Binary Search 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 이진 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 이진 탐색 기법 활용 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다. 이때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료한다. (..
[필수 알고리즘] 동적계획법 DP (Dynamic Programming) 이해
동적계획법 DP (Dynamic Programming) 동적 계획법은 프로그래밍 대회 문제에 자주 출현하는 알고리즘 기법 중 하나이며, 프로그램이 실행되는 도중, 실행에 필요한 메모리를 기억하여 할당하는 기법을 의미한다. : 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식이다. 중복되는 부분 문제 피보나치 수열을 예시로 코딩하려고 한다. 점화식이 F(n) = F(n-1) + F(n-2)이기 때문에 단순 재귀 함수로 구현된다. public class fibonacciEx{ static int fibonacci(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacci(n - 2) + fibo..
[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해
BFS 너비 우선 탐색 (Breadth-First Search) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다. 그렇게 되면 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문할 수 있다. Queue를 활용해야만 순서대로 접근이 가능하다. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다. ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 철수와 영희사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색(DFS)의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름 너비 우선 탐색(BFS)의 경우 - 철수와 가까운 관계부터 탐..