🖥 dev-ruby

이진 탐색 (이분 탐색, Binary Search) 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, mid, end)를 사용하여 탐색한다. 찾고자하는 데이터와 배열의 중간(mid) 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색이다. 이진 탐색(Binary Search)의 탐색 과정 위의 데이터 집합에서 8이란 데이터를 탐색하도록 하자. 우선 첫번째로 배열의 중간 요소를 선택한다. mid = 7; 두번째로는 중간 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중간 값보다 작다면 중앙 요소의 왼쪽에서 중간 값을 다..

동적계획법(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. dp의 핵심은 "메모이제이션" 기법인, 이미 계산된 결과를 별도의 메모리에 저장하여 필요한 경우 다시 계산하지 않고 사용하는 방식이다. 작은 문제들이 계속 반복되고, 그 작은 문제의 결괏값은 항상 같을 때 DP 알고리즘 적용할 수 있다. 가장 대표적인 예로 피보나치 수열을 들 수 있다. 피보나치 수열 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 피보나치 수열을 구할 때는 재귀를 쓴다. 다음과 같이 이전 결과와 전전 결과의 합으로 계속 구해나가는 방식이다. return f(n) = f(n-1) + f(n-2) 그런..

Dijkstra 다익스트라 알고리즘은 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 사용된다. 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다. 단, 가중치는 음수(-) 값을 가지지 않는다. 구현방법 다익스트라 알고리즘은 각각의 정점에 대해서 정점 s에서 정점 v까지의 최단 거리를 d[v]에 저장하면서 탐색한다. 알고리즘 시작 시, d[s] = 0이고, s가 아닌 다른 모든 정점에 대해서는 d[v] = 해당가중치 로 시작한다. 알고리즘이 종료 시, d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 된다. 다익스트라 알고리즘은 다음과 같다. Graph[A][B]는 A에서 B까지 가는 데 드는 비용 이라고 하자. 1. 주어진 N개의 정점 그래프에서 NxN 2차원 배열을 만들고..