Dynamic Programing복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과  Dynamic Programing은1. 하위 문제로 쪼개지며, 하위 문제의 정답으로 해당 문제의 정답을 구할 수 있을 때(Optimal Substructure)2. 하위 문제가 겹칠 때 (Overlapping Subproblem)사용할 수 있다. Top-Bottom방식과 Bottom-Up방식이 있는데이름에서 알 수 있다시피 위에서아래로, 아래에서 위로 가는 방식인 것 같다.Top-Bottom은 재귀를 통해 메인 문제에서 작은 문제들로 쪼개어가는 과정이고Bottom-U..

투포인터1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터(idx)를 조작해가며 원하는 것을 얻는 형태이다. 부분 배열 중 그 원소의 합이 조건과 일치하는 경우의 수를 구하는 것이다.모든 경우의 수를 다 테스트한다면 구간의 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이기 때문에 시간 복잡도를 고려하는 문제라면 풀 수 없다. 배열의 최대 범위가 너무 크기 때문이다.  예시 / 그림 참조 : https://butter-shower.tistory.com/226X = 5를 구하는 문제에서

깊이 우선 탐색 ( Depth-First Search )루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징1. 모든 노드를 방문하고자 하는 경우에 사용한다.2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다.3. 검색이 아닌 순회를 할 경우 많이 사용한다.공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다.미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.  장점1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.2. 목표 노드가 깊은 단계에 있을 ..

너비 우선 탐색 ( Breadth-first search )트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법.   탐색 방법1. 루트노드에서 시작한다.  2. 자식노드들을 저장한다.  3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며  4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다.   특징1. 어떤 노드를 방문했는지 반드시 검사 해야 한다.2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다.3. Prim, Dijkstra알고리즘과 유사하다.  장점1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.3. 너비..

[  플로이드-워셜(Floyd-Warshall)  ]그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.다익스트라(Dijkstra) 알고리즘다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다음의 간선을 포함할 수 없지만 현실 세계에서는 음의 간선이 존재하지 않기 때문에 현실 세계에..

탐욕법(Greedy Algorithm)※ Greedy : 탐욕스러운, 욕심 많은...탐욕 알고리즘 : 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법최적해를 구하는 데에 사용되는 근사적인 방법이다.여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하지만 그것이 최적이라는 보장은 없다.탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.     탐욕 알고리즘 문제를 해결하는 방법선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.적절성 검사(Feasibility Check) : 선택된 값이 문제의 조건을 만족하는..

Binary Search정렬된 데이터 집합을 이분화 하면서 탐색하는 방법정렬되어 있어야 한다  보통 세 개의 변수를 지정해 두고 (ex : left, mid, right)찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 찾아낸 값보다 오른쪽에 위치하고 작다면 왼쪽에 위치한다public static int binarySearch(int arr[], int x) { int mid; int left = 0; int right = arr.length - 1; // 배열을 다 돌때까지 반복 while (left