CS (53) 썸네일형 리스트형 두 수의 최대공약수는 유클리드 호제법 유클리드 호제법은 다음과 같이 정리할 수 있습니다. 정수 X와 Y(X>=Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X로 한다. 이를 활용해서 126과 90의 최대 공약수를 구해보자 126(X)와 90(Y)의 나머지 값은 36(R), 90(X) 와 36(Y) 의 나머지 값은 18 (R) , 36(X) 와 18(Y) 의 나머지 값은 0 (R) 따라서 126과 90의 최대공약수는 18이 된다. 참고도서 : 그림으로 배우는 알고리즘 basic - 스기우라 켄 힙 : 최소값을 구할때 적합한 자료구조 힙은 부모노드의 값이 자식 노드의 값보다 항상 적은 이진트리를 뜻한다. 조건 : 부모 노드의 값은 항상 하위 노드의 값보다 작다. (또는 부모 노드의 값은 항상 하위 노드의 값보다 크다) 자식 노드의 값은 둘 중 어느쪽이 크더라도 상관없다.(왼쪽 오른쪽 어느쪽이 크더라도 괜찮다) 따라서 뿌리 부분에 반드시 모든 값중에서 가장 작은 값(또는 가장 큰 값)이 배치된다. => 데이터 열 중에서 최소값(또는 최대값)을 효율적으로 구하는 용도에 적합하다. 실제로 힙을 구현할 때는 일반적으로 배열을 사용한다. 힙의 뿌리를 1번째 요소로, 그 다음은 아래의 절차를 따라 대입한다. '깊이'는 작은쪽에서 큰 쪽으로 노드의 왼쪽에서 오른쪽 방향으로 이 그림을 배열로 나타내면? 인덱스 [0] [1] [2] [3] [4] [.. 배열 및 배열 활용 자료구조 배열 2차원 배열 BASE0인 경우 ARRAY[2][6]의 위치 : 행, 열 0 1 2 3 4 5 6 0행 1 2 여기 3 문자열은 각 요소에 문자가 저장된 문자 배열이라고 볼 수 있다.\ N번째 요소의 참조가 빠른 것은 배열, 느린것은 연결리스트구조 *java의 ArrayList는 Array와 비슷하다. ArrayList는 내부적으로 Default 10개의 공간을 가진 배열로 구성되어있다. 책에서는 배열과 연결리스트를 비교하고 있음. 자료구조 읽기(참조) 추가/삭제 ArrayList 빠르다 느리다 LinkedList 느리다 빠르다 시간복잡도 ArrayList LinkedList 탐색 O(1) O(1) 맨 뒤 데이터 추가/삭제 O(1) or O(n) O(1) 맨 뒤 외의 위치에 데이터 추가/삭제 O(n).. 구조적 프로그래밍 알고리즘의 기초가 되는 구조적 프로그래밍의 개념 컴퓨터 프로그래밍에서 프로그램을 효율적으로 작성하고, 설계상의 오류를 최소화하기 위한 방법론으로 구조적 프로그래밍이라는 개념이 있다. 구조적 프로그래밍에서 모든 프로세스의 흐름은 다음 3가지 구조를 조합해서 설명할 수 있어야 한다. 순차 구조 : 작성된 순서대로 순차 실행한다 선택 구조: 조건에 따라 수행할 작업의 흐름을 바꾼다 반복 구조: 조건이 일치하는 동안 일정 과정을 반복해서 실행한다. 처리의 흐름을 설명하는 알고리즘 역시 이 3가지 구조의 조합으로 설명한다. 참고도서 : 그림으로 배우는 알고리즘 Basic - 스기우라 켄 도수 정렬 도수정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 데이터를 비교,교환하는 작업이 필요 없어 매우 빠르다. 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우에만 사용할 수 있다. public class CountingSort { public static void main(String[] args) { System.out.println("도수정렬"); System.out.println("요솟수: 7 "); int nx = 7; int[] x = new int[]{22,5,11,32,120,68,70}; int max = x[0]; for (int i = 1; i max) max = x[i]; } count.. 힙 정렬 힙 정렬은 선택 정렬을 응용한 알고리즘이다. 힙을 사용하여 정렬한다. 여기서 '힙'은 '부못값이 자식값보다 항상 크다'라는 조건을 만족하는 완전이진트리이다. 모든 부모와 자식의 관계는 항상 부모값>= 자식값 힙정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다. - 힙에서 가장 큰 값인 루트를 꺼냅니다 - 루트 이외의 부분을 힙으로 만듭니다 이 작업을 반복한다. import java.util.Arrays; public class HeapSort { static void swap(int[] a, int idx1, int idx2){ int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } public static void main(String[] a.. 병합정렬 병합 정렬 알고리즘 배열의 요솟수가 2개 이상인 경우 배열의 앞부분을 병합 정렬로 정렬합니다 배열의 뒷부분을 병합정렬로 정렬합니다 배열의 앞부분과 뒷부분을 병합합니다 배열 병합의 시간복잡도는 O(n), 병합정렬까지 생각하면 전체 시간복잡도는 O(n log n). + 안정적인 정렬방법이다. 실습 public class MergeSort { static int[] buff; // 작업용 배열 // a[left] ~ a[right] 를 재귀적으로 병합정렬 static void __mergeSort(int[] a, int left, int right){ if(left < right){ int i; int center = (left + right) / 2; int p = 0; int j = 0; int k = l.. 퀵정렬 퀵정렬은 요솟수가 많은 배열을 정렬하는 경우 효과적이다. O(n log n) ~ O(n²)의 시간복잡도를 가진다. 재귀적인 퀵 정렬 구현 left < pr, pl < right 는 모두 그룹의 요솟수가 1개일때는 성립하지 않는 조건임. 이 조건은 요솟수가 2개 이상인 그룹을 나눌 때 필요하다. import java.util.Scanner; public class QuickSort { static void swap(int[] a, int idx1, int idx2){ int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right) static void quickSort(int[] a ,int left, int r.. 이전 1 2 3 4 5 ··· 7 다음
