Info-Tech

선택정렬은 첫번째에 인덱스의 값을 선택후 내부 반복을 통해 ‘최소값’을 찾는다. 오른쪽으로 계속 이동하여 ‘최소값’일 경우 위치를 스왑한다. [10 , 8 , 3 , 1, 5]가 있다고 가정한다. 최초로 10이 선택되어 진다. [8,3,1,5] 에서는 최소값이 1이다. 즉 선택된 ’10’은 8부터 시작해 최소값 인 ‘1’과 자리를 바꾸게 된다. 1회전 결과 -> [1,8,3,10,5] 두번째는 8이 선택되어 진다. [3,10,5] 에서 최솟값은 ‘3’이다. 8과 3이 자리를 바꾸게 된다. 2회전 결과 -> [1,3,8,10,5] 3번째는 다시 8이 선택되어 진다. [10,5] 에서 최솟값은 ‘5’이다. 8과 5가 자리를 바꾸게 된다. 3회전 결과 -> [1,3,5,10,8] 4번째는 10이 선택되어 진다..

삽입정렬 2번째 자료부터 자기 바로 왼쪽 부터 index가 0이 될때까지 비교하는 방법. [2,5,3,4,1] 첫번째로 5(2번째 자료)가 선택되어 진다.

플로이드 와샬 변의 가중치가 음이거나 양인 가중 그래프에서 최단경로를 찾는 알고리즘 알고리즘 한번 수행시 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge (u,v) 3 dist[u][v] ← w(u,v) // 변 (u,v)의 가중치 4 for each vertex v 5 dist[v][v] ← 06 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← di..

동적 프로그래밍에서 지나치게 많이 일을 해서 좀 줄여보자는 취지로 만들어졌음. 미래를 생각하는게 아니라, 현재상황에서 최선을 택하는 기법이다. 활동선택문제와 백팩문제에서 쓰인다. 1.활동선택문제 이문제는 한 강의실에서 여러 수업을 진행한다고 했을 때, 가장 많이 할 수 있는 경우를 선택하는 문제이다. Si는 시작시간, Fi는 종료시간이다. 위 표를 보면 a1, a4와 a1,a2는 동시대에 진행되기 때문에 선택을 할 수 없다. 하지만 a1,a3은 선택이 가능하다. 즉 결과적으로 A1, a3, a6,a8 || A1, a3, a7, a9 이 후보지이다. G18을 a1이후, a8 이전으로 보면 선택 될수 있는 후보는 {a3,a5,a6,a7} 이다. 이중에서도 겹치지 않게 골라보면 {a3,a6} {a3,a7} {..

이진탐색을 하기 위해서는 데이터가 정렬이 먼저 되어 있어야 한다. 배열 { 1, 2, 4, 5, 6, 10,13,15 } 에서 4 ( = target값) 를 찾는다고 가정하자. 이진탐색의 기본 방법은 left의 Index와 해당 범위 내의 right Index를 2로 나뉘어 mid값을 찾아가는 가정이다. 처음의 mid = (0+7)/2arr[mid] = arr[3] = 5 즉, 우리가 찾고자 하는 값보다는 크다. 그럴 때는 right의 값을 현재 mid - 1을 해준다. 만약 target 값이 컸다면 left = mid+1을 해준다. 두번쨰 mid = (0+2)/2;(right = mid-1)을 해줬음.arr[mid] = arr[1] = 2, 즉 우리가 찾고자 하는 값보다는 작다 세번째 mid = (1+..

disjoint set 이라고도 불리며 서로소 집합이라고도 한다. 우선 서로소 집합이라는 표현부터 알아봐야 한다. 1 2 3 4 5 6 이처럼 각각의 서로다른 요소가 들어있다. 123 4 5 6 1과 2를 합친 상태이다. 123 456 4,5,6 을 합친 상태이다. 즉 이말은 4와 5를 합친 후에 5와 6을 합친 상황이다. 123 456 만약 1과 4를 합치면 이렇게 된다 -> 그 이유는 (1,2)하나의 집합이였고 (4,5,6)집합이 합쳐졌기 때문이다. 즉 두 집합에 속한 요소들을 합치게 되면 두 집합 자체가 합쳐지게 된다. 노드를 트리구조로 만들기 int parent[100];int size[100]for(int i=0; i

출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘 int distance [ ] = new int [n+1]; // 최단 거리를 저장할 변수 boolean check[ ] = new boolean[n+1]; //해당 노드를 방문했는지 체크할 변수 알고리즘 순서 1. distance는 처음에 나올 수 있는 가장 큰 값으로 초기화 하기 (Integer.MAX_VALUE)와 같은 값 2. 시작노드의 거리를 0으로 표시 (자기자신까지 거리는 0), 시작노드의 check값은 true로 바꾸기 3. 시작노드와 연결이 되어있는 노드들의 distance 값을 갱신하기 4. 방문하지 않은 노드중 distance 값이 최소인 노드(min_node)를 찾는다 5. min_node의 check값을 true로 변경한..

최악일때도 (nlogn) N개를 정렬하는 알고리즘이다. n개를 n/2로 나눈다. 그리고 왼쪽 n/2개와 오른쪽 n/2를 정렬한다. 정렬한 결과를 합친다. void sort(int start, int end){ if (start == end){ return; } int mid = (start+end)/2; sort(start, mid); sort(mid+1,end); merge(start,end); } void merge(int start, int end){ int mid = (start+end)/2; int s = start; int j = mid+1; int k = 0; //위에서 정해진 구간에 맞게끔 값 넣어주기 while( s