404 not found

퀵 정렬과 계수 정렬 퀵 정렬 : 기준데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 : 병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 : 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준데이터(Pivot)로 설정 ex) pivot = 3, 왼쪽에서는 피벗값보다 큰 값을 오른쪽에서는 피벗 값보다 작은 값을 골라 바꿔준다. 위치가 엇갈리는 경우, 피벗과 작은데이터의 위치를 서로 변경한다. 위치가 바뀐 피벗을 기준으로 오른쪽 왼쪽의 정렬에서 각각 퀵정렬을 수행한다. 3 4 0 1 5 2 > 3 2 0 1 5 4 > > 1 2 0 3 5 4 > 1 0 2 3 4 5 > 0 1 2 3 4 5 array = [3, 4, 0, 1, 5, 2] def ..

정렬알고리즘 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 1. 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에있는 데이터와 바꾸는 것을 반복 ex) 가장 작은 값을 골라 탐색범위 가장 앞자리와 자리를 바꾼다. 3 4 0 1 5 2 > 0 4 3 1 5 2 > 0 1 3 4 5 2 > 0 1 2 4 5 3 > 0 1 2 3 5 4 > 0 1 2 3 4 5 array = [3, 4, 0, 1, 5, 2] for i in range(len(array)): #i는 가장 작은 데이터와 위치가 바뀔 인덱스 min_index = i #가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: ..

트리 : 가계도와 같은 계층적인 구조를 표현할 때 사용할 수있는 자료구조 루트노드: 부모가 없는 최상위 노드 단말노드: 자식이 없는 노드 크기: 트리에 포함된 모든 노드의 개수 깊이: 루트 노드부터의 거리 높이: 깊이 중 최댓값 차수: 각 노드의 간선 개수(기본적으로 트리 크기가 N일 때, N-1개) 이진탐색트리 : 왼쪽자식노드 < 부모노드 < 오른쪽 자식노드 : 부모 노드보다 왼쪽 자식노드가 작다 : 부모 노드보다 오른쪽 자식노드가 크다 트리의 순회 : 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법 1) 전위순회: 루트를 먼저 방문 2) 중위순회: 왼쪽 자식을 방문한 뒤에 루트를 방문 3) 후위순회: 오른쪽 자식을 방문한 뒤에 루트를 방문 전위순회: A - B - D - E - ..

우선순위 큐(Priority Queue) : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 1) 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현(단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일) : 완전 이진 트리 자료구조 : 항상 루트노드를 제거한다 최소힙 - 루트노드가 가장 작은 값을 가진다 / 값이 작은 데이터가 우선적으로 제거 최대힙 - 루트노드가 가장 큰 값을 가진다 / 값이 큰 데이터가 우선적으로 제거 * 완전 이진 트리 : 루트 노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서대로데이터가 차례로 삽입되는 트리 * 최소 힙 구성 함수 : 부모 노드로 거슬러 올라가며, 부모다 값이 더 작은 경우에 위치를 교체 Python import sys im..

스택 자료구조 : 먼저 들어 온 데이터가 나중에 나가는 형식 : 입구와 출구가 동일한 형태 ex) 박스 쌓기 파이썬(Python) stack = [] #기본 리스트가 stack구조 stack.append(5) stack.append(7) stack.append(2) sack.pop() stack.append(3) stack.append(1) stack.pop() print(stack[::-1]) #최상단 원소부터 출력 print(stack) # 최하단 원소부터 출력 결과================================================= [3,7,5] [5,7,3] 자바(JAVA) import java.util.*; public class Main { public static void..

9. 합병정렬(Merge Sort) ​ 분할정복법(Divide and Conquer) ex) merge sort, quick sort ​ 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복: 각각의 작은 문제를 순환적으로 해결 합병: 작은 무네의 해를 합하여 원래 문제에 대한 해를 구함 ​ 합병정렬(Merge Sort) ​ 데이터가 저장된 배열을 절반으로 나눈다. 각각을 순환적으로 정렬한다. 정렬된 두 개의 배열을 합쳐 전체를 정렬한다. 크기가 n/2인 정렬된 두 배열 ⇒ 크기가 n인 추가 배열 이용 void merge (int data[], int p, int q, int r) { int i = p, j = q+1, k = p; int tmp [data.length()]; while (i

1. Class 오브젝트의 템플릿, 데이터와 메소드 필드를 가지고 있음 2. Object 클래스의 인스턴스, 자신 고유의 속성을 가지며 클래스에서 정의한 행위를 수행 3. 캡슐화(Encapsulation) 객체의 데이터와 메서드를 하나로 묶고, 실제 구현 내용 일부를 외부에 감추어 은닉함 4. 상속(Inheritance) 자식 클래스가 부모 클래스의 자료와 연산을 이용할 수 있게 하는 기능 5. Overloading, Overriding (Polymorphism) Overloading: 같은 이름의 메소드가 인자의 개수나 자료형에 따라서 다른 기능을 하는 것 Overriding: 같은 이름의 메소드가 여러 클래스에서 다른 기능을 하는 것 6. 추상화(Abstraction) 자료추상화 / 알고리즘 추상화

8. 기본적인 정렬 알고리즘 Bubble sort, Insertion sort, Selection sort : simple, slow Selection Sort (선택정렬) 1. 가장 큰 값을 찾는다. 2. 가장 큰 값을 가장 끝에 있는 값과 위치를 바꾼다. 3. 위치가 바뀐 가장 끝 값을 제외한 그 앞 부분에서 1,2번을 반복한다. 실행시간: 1) n-1번 반복 2) 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2, n-3,...,2,1 3) 위치 교환은 상수시간 작업 T(n) = O(n²) =n(n-1)/2 ⇒ 최악, 최선, 평균이 항상 같다. Bubble Sort 1. 자기자신을 다음 값과 비교하여 자신이 더 크면 다음 값과 교환한다. 2. 가장큰 값이 마지막으로 가게 되면 마지막 값을 제외하..