최단 경로와 다익스트라 알고리즘

최단 경로(Shortest Path) 최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다. 아래 세 개의 알고리즘이 주로 사용된다. 다익스트라 알고리즘(Dijkstra Algorithm) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 벨만 포드 알고리즘(Bellman-Ford's algorithm) 최단 경로 문제의 특징은 다음과 같다. 도로, 길찾기 문제 도로(길)와 가중치(값, 시간 등)가 주어지는 경우 Ex. A 위치에서 K 를 거쳐 X 로 도착하려고하는 경우에는 플로이드 워셜 알고리즘 사용. (즉, 어디를 거쳐간다고하면 플로이드 워셜 알고리즘일 가능성이 높음) 최단 경로의 문제는 대부분 가중치 방향 그래프..

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming) 동적 계획법을 듣기전에 재귀와 메모이제이션에 대한 이해가 먼저 필요하다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이 있는데 대표적인 방법에 동적 계획법(Dynamic Programming)이 있다. 다이나믹 프로그래밍 방식은 TopDown and BottomUp 두 가지가 있으며 메모이제이션 기법을 자주 사용한다. Memoization : 메모리를 더 많이 사용하여 시간 복잡도를 줄이는 방법 다이나믹 프로그래밍으로 해결할 수있는 대표적인 예시가 피보나치 수열이다. 재귀에서 배웠듯이 재귀를 사용하려면 점화식을 작성해보는 것이 좋다. 피보나치 수열에 대한 점화식은 다음과 같다. $$ n > 2 ? f(n) = f(n-2)..

결정 알고리즘과 파라메트릭 서치

결정 알고리즘(Decision Algorithm)과 파라메트릭 서치(Parametric Search) 결정 알고리즘과 파라메트릭서치를 배우기 전에 이진 탐색(Binary Search, 이분 검색)에 대한 이해가 선행되어야 한다. 따라서, 이진 탐색에 대해서 먼저 배워보도록 하겠다. 순차 탐색(Sequential Search) 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용하며, 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 결과를 찾을 수 있다. 구현 /** * @param n 입력 데이터 개수 * @param target 찾고자 하는 문자열 * @param arr 배열 */..

재귀 함수(Recursion Function)

재귀 함수(Recursion Function) 재귀 함수는 내부적으로 스택(Stack)을 이용한다. JVM(Java Virtual Machine) 의 메모리인 Runtime Data Areas 영역에 스택 영역이 존재한다. 자바에서 함수를 호출하게 되면 함수에 대한 정보들이 스택 공간에 적재되기 때문에, 재귀 함수는 스택 자료구조를 이용한다고 볼 수 있다. 재귀 함수는 자기 자신을 다시 호출하는 함수를 의미 하는데, 재귀 함수를 제대로 이해하기 위해선 다음과 같은 내용에 대한 이해가 되어있어야 한다. JVM 메모리 스택 영역 JVM 메모리 힙 영역 스택 자료 구조 Call Frame(Call Stack) 먼저, 이 부분에 대한 이해를 다루기 전에 팩토리얼(Factorial) 구현을 예시로 들어서 재귀 함..