오리 (Dev)

그래프 최단거리를 구하는 알고리즘1. 다익스트라2. 벨만 포드3. 플로이드 와샬 벨만 포드 알고리즘은 다익스트라 알고리즘처럼 그래프에서 한 노드에서 다른 모든 노드까지 가는 최소비용을 구할 수 있는 알고리즘이다. 다익스트라와의 차이점은 음수 가중치가 존재하는 경우에도 적용 할 수 있다. 벨만 포드 알고리즘의 시간복잡도는 O(VE)이다. (V: 정점, E: 간선)다익스트라에서 시간복잡도는 O(VlogE)이므로 다익스트라가 더 빠르다. 다익스트라 알고리즘의 한계다익스트라 알고리즘은 그리디알고리즘 + 다이나믹 프로그래밍이 합쳐진 알고리즘이다. 그리디 알고리즘 한계점 때문에 다익트스라 알고리즘은 음수 가중치를 가질 수 없다.위 그림에서 1번 -> 3번 이동할때 최소비용을 구하게하면다익스트라는 1->3 경로인..

다익스트라 알고리즘V = vertext(정점) , E = edge(간선) , adjNode = adjacentNode(인접노드) - 최단경로를 구하는 알고리즘- 하나의 정점을 기준으로 다른 정점까지 가는 최단거리를 구한다. (출발지에서 다른 정점까지의 최단거리들을 구한다)- 음수 가중치가 없어야한다- 인접 행렬로 표현된 그래프로 다익스트라 알고리즘을 구현시 시간 복잡도 O(V^2)- 우선순위 큐+리스트를 사용해서 다익스트라 알고리즘 구현시 시간복잡도 ( ElogV) 까지 낮출수 있다고 한다.- 탐욕법(그리디 알고리즘) 과 동적 계획법(다이나믹 프로그래밍)을 사용한다. -> 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 (그리디 알고리즘) -> 해당 노드로부터 갈 수 있는 노드들의 비..

배열을 비교할때는 Arrays.equals() 메소드를 사용한다. static void solve() throws IOException { int[] a = {1, 2, 3,}; int[] b = {1, 2, 3,}; if (a == b) { bw.write("동일한 배열입니다."); } else { bw.write("동일하지않습니다."); } } ==로 비교하게되면 원하는 결과가 나오지않는다. ==연산자는 각 배열의 주소값을 비교하기 때문이다. Arrays.equals()를 사용하면 원하는 결과가 나온다. static void solve() throws IOException { int[] a = {1, 2, 3,}; int[] b = {1, 2, 3,}; if (Arrays.equals(a,b)) { ..

우선순위 큐(Priority Queue)란? 큐는 일반적으로 선입선출의 구조이지만 우선순위큐는 우선순위가 높은 순서대로 나가는 구조입니다. 우선순위큐는 최대힙 또는 최소힙을 이용하여 구현됩니다. 최대힙을 이용하고, 숫자 데이터라면 숫자가 큰 순서대로 데이터가 나가고, 최소힙을 이용하고, 숫자데이터라면 숫자가 작은 순서대로 데이터가 나갈것입니다. Priority Queue(우선순위큐) 선언 import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) PriorityQueue priorityQueue = new PriorityQueue(); //int형 priorityQueue 선언 (우선순위가 높은 숫자 순) Priorit..

Heap(힙) 힙은 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다. 힙을 알기전에 트리구조 부터 알아보자. Heap(힙)은 우선순위큐 구현에 사용된다. 트리구조란? 위와 같은 구조가 트리구조이다. 부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B) 자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H) 루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다. 단말 노드(leaf node) : 리프 ..

DFS(깊이 우선 탐색, Depth-First Search)루트노드(혹은 다른 임의의 노드)에서 다음 분기(Branch)로 넘어가기 전에, 해당 분기(Branch)를 모두 탐색 하는 방법탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 특징1. 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택으로 구현)->조합에서 뽑고, 재귀적으로 호출하고, 뽑은거 취소하는것처럼 , 자기 자신을 호출함으로서 해당 수를 뽑은 경우의 모든경우를 탐색한다. 2.그래프탐색인 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. ( 검사하지않을경우 무한루프에 빠질수 있다.) ex) visited[index] = true , if(!visited[index]) -> 일반 조합에서 중..

Stack ~을 쌓다는 의미, 벽돌을 쌓는다 생각했을때 가장 먼저들어온 벽돌은 가장 아래에 위치할 것이고, 가장 나중에 들어온 벽돌은 가장 위에 위치할 것이다. 그리고 다시 이 벽돌들을 치운다고 생각할때 , 맨위에있는 벽돌부터 빼낼것이다. 이렇게 먼저 들어온 데이터가 마지막에 나가는 구조를 후입선출(LIFO = Last in First out) 또는 선입후출(FILO = First in Last out)이라고 한다. (둘 다 같은 말이다.) search() 메소드 스택 내부 배열의 인덱스 값이 아니라 스택의 '상단으로부터 몇 번째에 위치 하는지'를 반환하는 것이다. 즉, 거리 개념이라고 보면 된다. Stack a = new Stack(); a.add(1); a.add(2); a.add(3); bw.wri..

그리디 알고리즘Greedy(탐욕) 알고리즘은 매 번의 선택에서 가장 좋아보이는 선택을 하여 적절한 답을 찾아간다예를 들어 다음과 같이 서울에서 부산을 가는 경로가 있다고 해보자.서울-대전을 가는 경로중 가장 빠른 경로인 80분 걸리는 경로를 선택하고대전-부산을 가는 경로중 가장 빠른 150분 걸리는 경로를 선택하여총 230분이 걸리는 경로가 가장 빠른 경로일것이다.이렇게 각 단계별로 최선의 선택지를 선택하는것이 그리디 알고리즘이다. 하지만 그리디 알고리즘은 항상 최적의 해를 도출해내는것이 아니다. 조건이 필요하다. 아래의 예시를 보자.똑같이 부산을 목표로 가장 짧은 소요시간을 구해보자.서울에서 원주로 가는 경로가 생긴 예시이다. 서울-대전 , 서울-원주를 보니 가장 적은 소요시간인 80분을 선택하고다시 ..

동적프로그래밍DP, 동적프로그래밍은 하나의 큰 문제를 여러개의 작은 문제로 나눠서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는것으로특정한 알고리즘이 아닌 하나의 문제해결법이라고 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 , 작은 문제의 답을 저장하고 저장한 답을 이용하여 점점 큰 문제를 해결하면서 저장한다. 그렇게 원하는 값까지 도달한다.(기억하며 풀기라고 불리기도 한다.) DP를 쓰는이유일반적인 재귀방식 또한 DP와 유사하다. 하지만 일반적인 재귀는 똑같은 작은 문제들을 여러번 계산하게 되서 비효율적이라는것이다. 예를 들어 피보나치 수열을 구하는 재귀의 동작방식을 살펴보자.1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 처럼 진행되는 ..

BigInteger를 사용해야 하는 이유 int나 long과 같은 자료의 범위가 다음과 같다. 저 범위를 넘어서면 모두 0으로 출력된다. 알고리즘 문제를 풀다 팩토리얼 문제나, 조합 문제에서 큰 수를 다뤄야 할때가 있다. (최악의 경우에 대비하여) 동적프로그래밍으로 해결해도 되지만 BigInteger의 사용도 답일때가 있다. 또는 프로그램 개발에서 특히 돈과 관련된 개발에서는 항상 최악의 상황을 생각해야하므로 무한의 정수가 들어갈 수 있는 BigInteger 클래스를 활용하는것이 좋다. BigInteger는 문자열 형태로 이루어져 있어 숫자의 범위가 무한하기 때문에 어떤 숫자라도 담을 수 있다. BigInteger 사용법 BigInteger 생성 및 초기화 BigInteger를 초기화하려면 문자열을 이용..