본문 바로가기

알고리즘6

[Algorithm] 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ■ 정의 - 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조 - 힙(heap)을 사용하여 정렬하는 알고리즘 · 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리 · 최대힙: 부모노드 값(key 값) ≤ 자식노드 값 (key 값) · 최소힙: 부모노드 값(key 값) ≥ 자식노드 값 (key 값) ■ 인덱스 관계 - 부모노드 인덱스: a[(i-1) / 2] - 왼쪽 자식노드 인덱스: a[i * 2 + 1] - 오른쪽 자식노드 인덱스: a[i * 2 + 2] ■ 힙 정렬 과정 Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거 Step 2. 다시 힙을 .. 2023. 4. 8.
[JAVA] 유클리드 호제법(GCD / LCD) GCD (최대 공약수) ■ 정의 1. 22 x 8 크기의 직사각형을 짧은 변(8)을 한 변으로 하는 정사각형으로 분할 2. 정사각형을 제외한 8 x 6 직사각형을 짧은 변(6)을 한변으로 하는 정사각형으로 분할 3. 남은 6 x 2 직사각형을 2 x 2 크기의 정사각형 3개로 분할 ☞ 마지막까지 나누어 떨어진 정사각형의 한 변의 길이가 최대 공약수가 됨 ■ Code import java.util.Scanner; public class EuclidGCD { static int gcd(int x, int y){ if(y == 0) return x; else return gcd(y, x % y); } public static void main(String[] args){ Scanner sc = new Scan.. 2023. 3. 15.
[Algorithm] 버블 정렬(Bubble Sort) 버블 정렬 (Bubble Sort) ■ 정의 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)이라고도 함 ■ 사용 예 - 총 3번의 Pass를 통해 [1, 3, 4, 6, 7]로 오름차순 정렬을 만들 수 있음 - 사진에서는 모든 비교과정을 표시하였지만, 이미 정렬된 수와의 비교는 굳이 진행하지 않아도 됨 ■ 장점 - 구현이 매우 간단하고, 소스코드가 직관적 - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting) - 안정 정렬(Stable Sort) ■ 단점 - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장.. 2023. 3. 9.
[자료구조] 스택(Stack) / 큐(Queue) 스택(Stack) ■ 정의 - 데이터를 일시적으로 쌓아 놓는 자료구조 - 데이터의 입력과 출력 순서는 후입선출 (LIFO: Last In First Out) ■ 메소드 Stack s = new Stack(); Stack s = new Stack(int capacity); // 스택의 capacity 결정 메소드 의미 push(int item) 스택에 데이터를 저장 pop() 스택의 꼭대기에 있는 데이터를 제거하고, 그 값을 반환 isFull() 스택이 empty 상태인지 확인 isEmpty() 스택이 full 상태인지 확인 clear() 스택의 모든 요소를 삭제 peek() 스택의 가장 최상위(마지막)에 위치한 데이터 출력 capacity() 스택의 용량 확인 (스택 전체 크기) size() 스택의 크기.. 2023. 2. 22.
[Algorithm] 이진검색 (Binary search) 이진검색 (Binary search) ■ 정의 - 이진검색은 요소가 오름차순으로 정렬된 배열인 상태에서 검색하는 알고리즘 - 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색 - 리스트의 중간 부분에 찾는 원소가 있는지 확인, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색 하거나 중간부터 검색 ■ 사용 예 - 39를 찾는 과정 1. index 0과 10을 기준으로 2로 나눈 값 index 5를 살펴본다. 2. index 5의 값이 찾으려는 39보다 작으므로 index 5 이하는 더 이상 살피지 않는다. 3. index 6과 10을 기준으로 2로 나눈 값 index 8을 살펴본다. 4. index 8의 값이 찾으려는 39보다 크므로 index .. 2023. 2. 14.
[Algorithm] 선형검색(Linear search) / 보초법(Sentinel method) 선형 검색 (Linear search) ■ 정의 - 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 기법 ■ 사용 예 - 찾으려는 값이 2일 경우 - 찾으려는 값이 7일 경우 - 찾는 값이 3으로 존재하는 경우 앞에서부터 순차적으로 검색 후 index 값이 3에서 탐색을 종료 함 - 찾는 값이 7로 존재하지 않는 경우 마지막까지 검색 후 -1을 return 후 종료 함 ■ Code - while문으로 작성한 선형검색 public class SeqSearch { static int seqSearch(int[] a, int n, int key){ int i = 0; while(true){ if(i == n) return -1; if(a.. 2023. 2. 13.

티스토리툴바