알고리즘/개념 (5) 썸네일형 리스트형 투 포인터 투 포인터 1차원 배열이 있고 두개의 포인터를 이용해 원하는 값을 찾아내는 알고리즘이다. 가장 대표적은 예로는 N개의 수에서 합 M의 개수를 찾는 문제이다. 포인터로 사용할 s,e와 합을 저장할 S가 있다고 한다면 이론적으론 다음과 같다. 1. S >= M 이면 S -= A[s++] 2. e == N 이면 break 3. S < M 이면 s += A[e++] 4. S == M 이면 ans++ 이 과정을 거쳐서 M의 개수를 찾는 방식이다. 그림과 같이 이해하면 다음과 같다. 처음은 다음과 같다. 초록색 화살표를 s, 파란색 화살표를 e라고 한다면 처음은 0에서부터 시작한다. 현재 S값이 M보다 작기 때문에 3번 과정이 수행된다. 지금 상태는 S == M인 상태이다. 그렇기 때문에 ans를 4번이 실행되고 .. 구간 트리(세그먼트 트리) 세그먼트 트리 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 답할 수 있도록 하는 방법이다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것이다. 구간 트리의 루트는 항상 배열의 [0,n-1]을 표현한다. 구간 트리에서 질의에 응답하는 시간복잡도는 O(logn)이다. 구간 트리에서 구간을 모두 저장하기 위한 배열의 길이는 n이 2의 거듭제곱이라면 2n이면 된다. 그렇지 않다면 가장 가까운 2의 거듭제곱으로 n을 올림한 뒤 2를 곱해야 한다. 하지만 간단한 방법으로 4n으로 배열의 길이를 잡으면 된다. 메모리가 낭비된다는 단점이 있지만 편리하게 쓸 수 있다. 구간 트리 초기화 static long init(int node, int s, int e) { i.. 다익스트라,벨만포드,플로이드 워샬 다익스트라 한 정점에서 다른 정점까지 최소로 가는 경로를 구하는 최단 경로 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식. 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다. 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다. 음의 가중치가 있을 경우 사용하지 못한다. 시간복잡도는 일반적으로 O(V^2), 우선순위큐를 사용한다면 O(ElogV)이다. 동작과정 1. 시작 정점을 입력 받는다. 2. 거리를 저장할 D배열을 무한대로 초기화 한 후 시작점에서 갈 수 있는 곳의 값은 바꾼다. 3. 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치 합이 작다면 변경한다. 4.. Permutation & Combination import java.util.Arrays; public class Permutation { static int[] arr = {1,2,3}; public static void main(String[] args) { perm(arr.length,0); } static void perm(int n, int k) { if(k == n) { System.out.println(Arrays.toString(arr)); return; } for(int i = k; i < arr.length; i++) { swap(k,i); perm(n,k+1); swap(k,i); } } static void swap(int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp.. DISJOINT-SETS, MST MST(최소 신장 트리) MST의 목적 낭비를 줄이고 최적의 비용으로 모두를 연결하기 위함 그리디한 기법을 쓴다. 팩토리얼 보다 적게 만들기 위해서 쓴다. 모든 경로의 합이 최소를 찾기 위해서 쓴다.(나중에 나올 다익스트라와 용도가 다르다.) MST를 만들기 위한 기법은 두가지 프림, 크루스칼 프림 disjoint-sets을 기반으로 깔고 들어간다. 크루스칼 크루스칼에서 다음 노드를 선택했을 때 그 노드를 union한다. 또한 사이클이 발생할 수 있는 경우를 방지한다. 트리이기 때문에 사이클이 발생하지 않아야 한다. 간선이 많으면 터진다. 간선이 적으면 크루스칼, 간선이 많으면 프림 DISJOINT-SETS 서로소 집합을 의미한다. 각 집합의 부모 노드를 가지고 있고 부모 노드가 다르면 다른 집합을 의미.. 이전 1 다음
