algorithm/theory

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍를 활용한 최단 경로(Shortest path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다익스트라 알고리즘이 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 다양한 루트가 존재하기 때문'이다. 그렇기에 기존에 하나의 최단 거리를 구할 때 까지 모든 루트를 그대로 사용한다. 아래의 그래프에서 1에서 다른 정점으로 가는 최단 거리를 구한다고 해보자. 1에서 각 정점으로 한 번에 가는 최단 거리는 각 3, 6, 7이다. 이 때 한 번에 가는 것이 아닌 2를 거쳐 정점 3과 정점 4로 간다면 3 > 1과 3 > 1 >..

플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 문제들이 있다. 이 경우 플로이드 와샬 알고리즘을 사용하면 쉽게 모든 정점의 최단 거리를 구할 수 있다. 플로이드 와샬을 기본적으로 DP를 기반으로 진행된다. 플로이드 와샬 알고리즘의 주요 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 위 와 같은 그래프가 존재한다고 가정하자.이 때 각 정점에서 다른 정점으로 가는 비용을 이차원 배열로 정리하면 아래와 같다. 해당 테이블이 의미하는 바는 '현재까지의 최단 거리'이다. 해당 테이블을 통해 지나치는 정점으로 다른 정점으로 가는 테이블을 그릴 것이다. 1. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 노드 2와 노드 3이다. 이를 테이블로 나타내면 아래와 같다..

소수(Prime number) 판별법/ javaScript

소수 (Prime number) 판별법 소수란 1, -1과 자기 자신, 자기 자신의 반수로 밖에 나누어 떨어지지 않는 1 이외의 정수, 즉 양의 약수가 2개인 자연수를 의미한다. 소수는 다양한 알고리즘 문제에 자주 등장하는 개념이다. 그러므로 소수를 판별하는 법을 알아두고, 효율적인 방법을 기억해두는 것이 좋다. 1. 3부터 자기 자신까지 비교 첫 번째 방법은 말 그대로 3부터 자기 자신까지 모든 수를 숫자에 나누어보아 약수 여부를 판단하는 것이다. 아래 코드를 보자 const isPrime = ( num ) => { if(num < 2) return false;// 0과 1은 소수가 아니다. if(num === 2) return true;// 2는 유일한 짝수인 소수이다. if(num % 2 === 0..

순열/조합 (Permutation / Combination)

1. Combination (조합) 조합 : 순서 없이 n개 중에 r개를 뽑는 것 예) 10C3 = 1098 / 321 = 120 nCr = nCn-r이므로 10C3 = 10C7 const getCombinations = (array, selectNumber) => { const results = []; if(selectNumber === 1){ return array.map((element) => [element]); } array.forEach((fixed, index, origin) => { const rest = origin.slice(index+1); const combinations = getCombinations(rest, selectNumber - 1); const attached = co..

탐욕법(Greedy)

탐욕법은 말그대로 탐욕적으로 눈앞에 보이는 상황에서 가장 좋은 상황(최선의 선택)을 고르는 것을 말한다. 탐욕법은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다. 탐욕법 사용 가능 조건 Local minimum과 Global minimum이 같을 경우 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 ( 동적계획법과 동일) Problem들의 solution들이 서로 영향을 주면 안된다 탐욕법 예제 탐욕법의 가장 대표적인 예시는 coin change이다 예를 들어 760원을 [10,50,100,500]의 동전으로 주는데 동전을 최소로 주는 방법을 구하는 것이다. 이 때는 가장 큰 500원 부터 차례..

해쉬(Hash)

해쉬 테이블은 key-value system을 이용하여 자료를 정리하는 구조이다. 이 구조는 사전과 같은 의미라고 볼 수 있다. 만약 사전에서 단어를 찾는다면 해당 단어를 찾고 그 단어의 해석을 확인할 것이다. 이 때 해당 단어가 key이고, 단어의 해설이 value이다. 해쉬 테이블을 사용하는 이유는 무엇일까? 바로 효율성 때문이다. 아래는 배열과 해쉬에서 하나의 데이터를 찾는 과정이다. 배열 위에서 보이는 배열에서 원하는 메뉴를 찾는다고 가정하자. 만약 pizza의 가격을 찾는다면 위에서부터 선형 탐색(Linear Search)을 진행한다. 이렇게 선형 탐색을 하게되면 매우 시간이 오래 걸리게 된다. 해쉬 테이블 위 해쉬 테이블에서 같은 pizza의 가격을 찾는다면 간단하게 pizza를 호출하면 된다..